スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




Traveling by Stagecoach

2006.06.29 15:18  ACM/ICPC

問題: ACM/ICPC Japan Domestic 2005: Problem D

[解説]
グラフの最短経路を解くためのダイクストラのアルゴリズムによって解くことができます。ただし、与えれた地図情報(グラフ)にそのままダイクストラを施すのではなく、一工夫必要です。

探索するグラフのスペースを、手持ちの馬車券の状態を考慮して拡張します。
ダイクストラのアルゴリズムでは、dist[ノード i] は、スタート地点 s からノード i までの最短コストを示しますが、ここでは、

dist[ノード i][ノード i における馬車券の状態]

と拡張します。ポイントは、どのように"ノード i における馬車券の状態"を配列のインデックスとして表現するかですが、ここでの解答では、10 進数の 2 進数表現を応用します。

例えば、馬車券の最大枚数を 5 とすれば、馬車券の全ての状態は以下のように表現できます。
2進数 10進数
00000 0
00001 1
00010 2
00011 3
00100 4
00101 5
. .
11111 31

例えば、00000 → 全ての馬車券がない、11111 → 全ての馬車券を持っている、00101 → 1 番目の馬車券と 3 番目の馬車券を持っている、、と表現することができます。従って、例えば

dist[3][10] = dist[3][010102] = スタート地点 s から、2 番目と 4 番目の馬車券を持っている状態でのノード 3 までの最短コスト

となります。

プログラム例(C++)

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<climits>
#include<queue>

using namespace std;

#define INFTY 1 << 21
#define TMAX 8
#define MAX 30
#define VMAX 256

class Node{
    public:
    int id, state;
    double cost;
    Node(){}
    Node( int id, int state, double cost ): id(id), state(state), cost(cost){}
    
    bool operator < ( const Node &n ) const {
        return cost > n.cost;
    }
};

int nticket, nnode, p, source, target;
int T[TMAX +1], M[MAX+1][MAX+1];

double dijkstra(){
    bool visited[MAX+1][VMAX];
    double d[MAX+1][VMAX];
    int p = 1; p = p << nticket;
    
    for ( int i = 1; i <= nnode; i++ ){
        for ( int j = 0; j < p; j++ ){
            d[i][j] = INFTY;
            visited[i][j] = false;
        }
    }
    
    d[source][0] = 0;
    priority_queue<Node> PQ;
    PQ.push( Node( source, 0, 0.0) );
    
    while ( !PQ.empty()) {
        int u, k;
        Node curr = PQ.top(); PQ.pop();
        u = curr.id;
        k = curr.state;
        
        if ( u == target ) return d[u][k];
        if ( d[u][k] < curr.cost ) continue;
        d[u][k] = curr.cost;
        
        if ( visited[u][k] ) continue;
        
        visited[u][k] = true;
        
        for ( int v = 1; v <= nnode; v++ ){
            if ( M[u][v] == INFTY ) continue;
            
            int l = 1;
            for ( int use = 1; use <= nticket; use++, l = l << 1 ){
                int next = k | l;
                if ( k == next ) continue; // already used
                if ( visited[v][next] ) continue;
                
                double cost = curr.cost + 1.0 * M[curr.id][v] / T[use];
                
                if ( cost < d[v][next] ){
                    d[v][next] = cost;
                    PQ.push( Node( v, next, cost ) );
                }
            }
        }
    }
    
    return INFTY;
}

void compute(){
    double cost = dijkstra();
    if ( cost == INFTY ) cout << "Impossible" << endl;
    else printf("%.3lf\n", cost);
}

void init(){
    for ( int i = 1; i <= nnode; i++ ){
        for ( int j = 1; j <= nnode; j++ ){
            M[i][j] = INFTY;
        }
    }
}

bool input(){
    cin >> nticket >> nnode >> p >> source >> target;
    if ( nticket == 0 ) return false;
    for ( int i = 1; i <= nticket; i++ ) cin >> T[i];
    int x, y, z;
    
    init();
    
    for ( int i = 0; i < p; i++ ){
        cin >> x >> y >> z;
        M[x][y] = M[y][x] = z;
    }
    return true;
}

main(){
    while ( input() ) compute();
}
スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Hanafuda Shuffle

2006.06.29 14:09  ACM/ICPC

問題: ACM/ICPC 2004 Problem A

[考察]
プログラミング入門の問題に適し、ACM/ICPCの肝を突いている問題です。初心者にとってはやや難しく、中級者にとっても、しっかり設計して挑まないとうっかりミスをしやすい問題ではないでしょうか。

[解説]
、をするまでもないのですが、いくつかポイントを。
まず、分かりやすいように配列のインデックスは1baseとし、以下のように初期化すると良いと思います。
hanafuda1.gif

cut( p, c ) という関数(操作)を、例えば以下のようにしっかり設計することが重要です。
hanafuda2.gif


[プログラム例 (C)]

#include<stdio.h>
#define MAX 50

int n, r;
int D[MAX+1], tmp[MAX+1];

void cut( int p, int c ){
    int i;
    for ( i = p; i < p + c; i++ ) tmp[i-p+1] = D[i];
    for ( i = 1; i < p; i++ ) tmp[i+c] = D[i];
    for ( i = 1; i < p + c; i++ ) D[i] = tmp[i];
}

void simulate(){
    int p, c, i, rest;
    
    for ( i = 1; i <= n; i++ ) { D[i] = n-i+1; }
    for ( i = 0; i < r; i++ ){
        scanf("%d %d", &p, &c);
        cut( p, c );
    }
    
    printf("%d\n", D[1]);
}

int input(){
    scanf("%d %d", &n, &r);
    if ( n == 0 && r == 0 ) return 0;
    return 1;
}

int main(){
    while ( input() ) simulate();
    return 0;
}

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




動的計画法 Dynamic Programming

2006.06.27 19:33  動的計画法

問題を解く有効な手法の1つが、最終的な解を求めるために、その問題の小さな部分問題の解を用いることです。一般的に小さな問題はより容易に分析・解決できるものです。この手法の代表的なものに、分割統治法(Divide and Conquer)と動的計画法 (Dynamic Programming: DP)があります。

分割統治法では問題を2つ(またはそれ以上)に分け、それらをそれぞれ解き、元の問題を解くためにそれらの分割して解かれた問題を統合して利用する、という処理を再帰的に行います。マージソートが分割統治法のよい例です。

一方動的計画法は、小さな部分問題を計算して得られた解をメモリに記録し、さらに大きい問題を解くためにそれら記録された結果を有効に使うことによって問題を解きます。

どちらも重要なプログラミング手法ですが、動的計画法は多くの問題の最適な解(最大値や最小値)を求めることができ、様々な問題に応用できる実用的なアルゴリズムです。




DP は、システムエンジニアやプログラマの方にとっては、必ず習得すべきプログラミングテクニックの1つだと思います。しかし、与えられた問題に DP が適用できるか否かの判断は難しいので、ある程度の経験が必要です。つまり、小さな問題の解を利用することによって、大きな問題の解が正しく求めることができるか否かの判断が難しいのです。

DP のスキルを伸ばすためには、DP が適用できる典型的な問題を解いてみるのが良いと思います。以下に応用問題をあげます(解法バレ注意してください)。











テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




連鎖行列積 Matrix Chain Multiplication

2006.06.26 01:36  動的計画法

l × m の行列 A と、m × n の行列 B が与えられた時、AB の積 C

C[i, j] = Σmk=1A[i, k] * B[k, j] ( 1 ≦ il, 1 ≦ jn)

を満たす l × n の行列になります。

matrixChain1.gif

この計算では、 l × m × n 回の掛け算が必要です。では複数の行列の積(連鎖行列積)について考えてみましょう。

(M1M2M3...Mn) のように、1 ≦ i ≦ n について、行列 Miri の行と ri+1 の列をもつ(下図参照) n 個の行列の掛け算を考えます。

matrixChain2.gif

この条件の下では、これらの行列の積は様々な順番で計算することができます。例えば、左から右へ向かって計算すると

(...((M1M2)M3)...Mn)

と表すことができ、右から左に向かって計算すると

(M1...(Mn-2(Mn-1Mn))...)

と表すことができます。さらに

(M1..(M2(M3M4)M5)...Mn)

などの、様々な順番が可能です。

ここで注目すべきことは、勿論掛け算の計算結果(連鎖行列積)は同じですが、行列の掛け算の順番によって、"掛け算の総回数"が異なってきます。例えば、上記の連鎖行列積に必要とする掛け算の総回数を、いくつかのケースについて考えてみましょう(2つの行列の掛け算には上記式の標準的な方法を用いることとします)。

Case 1. 左から右へ向かって: 86 回

matrixChainCase1.gif

Case 2. 右から左に向かって: 69 回

matrixChainCase2.gif

Case 3. 最適な順番: 36 回

matrixChainCase3.gif

連鎖行列積では、隣り合う2つの行列の掛け算にどのような方法を用いたとしても、「どのような順番で」掛け算を行うかが、総演算回数に大きく影響します。Matrix Chain Multiplication (連鎖行列積) は、掛け算の総回数を最小にする最適な連鎖行列の掛け算の順番を求める問題です。

連鎖行列積を計算する最適な順番を直接求めるために、全ての可能な順番を調べてみるアルゴリズムは現実的ではありません。行列の個数が大きくなれば、計算量が指数的に膨大になることは明らかです。以下に示すように、この問題には Dynamic Programming (DP) (動的計画法) が適用できます。

まず、(M1M2) を計算するための方法(順番)はただ 1 通りであり、r1 × r2 × r3 回の掛け算が必要です。同様に、(M2M3) を計算するための方法もただ 1 通りであり、r2 × r3 × r4 回の掛け算が必要です。つまり、(Mn-1Mn) を計算するための方法はただ 1 通りであり、rn-1 × rn × rn+1 回の掛け算が必要です。そして、これらの掛け算の回数をコストとして表に記録しておきます。

次に、(M1M2M3)、(M2M3M4)、...(Mn-2Mn-1Mn) を計算するための最適な方法を求めます。

例えば、(M1M2M3) を計算するための最適な方法を求めるためには、(M1(M2M3)) と ((M1M2)M3)のコストを計算し、小さい方のコストを (M1M2M3) のコストとして表に記録します。この時、

(M1(M2M3)) のコスト = (M1) のコスト + (M2M3) のコスト + r1 × r2 × r4
((M1M2)M3) のコスト = (M1M2) のコスト + (M3) のコスト + r1 × r3 × r4

となります。ここで注目すべきことは、これらの計算に用いた (M1M2) 及び (M2M3) は再計算する必要がなく、表から参照することができるということです。また、1 ≦ in について、(Mi) のコストは 0 であることに注意します。

一般的な形式では、(MiMi+1...Mi+j) を計算するための最適な方法は、 i + 1 ≦ ki + j における (MiMi+1...Mk-1)(Mk...Mi+j) の中から最小のコストを見つけることによって決定します。

例えば、、(M1M2M3M4M5) (つまり、i = 1、j = 4 の場合)のコストは、

k = 2 (M1)(M2M3M4M5) のコスト = (M1) のコスト + (M2M3M4M5) のコスト + r1×r2×r6
k = 3 (M1M2)(M3M4M5) のコスト = (M1M2) のコスト + (M3M4M5) のコスト + r1×r3×r6
k = 4 (M1M2M3)(M4M5) のコスト = (M1M2M3) のコスト + (M4M5) のコスト + r1×r4×r6
k = 5 (M1M2M3M4)(M5) のコスト = (M1M2M3M4) のコスト + (M5) のコスト + r1×r5×r6

のうちの最小値となります。


実装に向けて、さらに具体的に見てみましょう。

まず、cost[][] を cost[i][i + j]> が (MiMi+1...Mi+j) を計算するための最適なコストを記録する配列とします。

さらに、best[][] を best[i][i + j] が (MiMi+1...Mi+j) を (MiMi+1...Mk-1)(Mk...Mi+j) によって与えるような k を記録する配列とします。

以下に、プログラム例を示します。

#include<iostream>
#include<stdio.h>
#include<algorithm>

using namespace std;

void output( int, int, int, int);

#define MAX 100
#define INFTY (1 << 21)

int SIZE;
int R[MAX + 2];
int C[MAX+1][MAX+1]; // cost table
int B[MAX+1][MAX+1]; // best table

void compute(){
    for ( int i = 1; i <= SIZE; i++ )
    for ( int j = 1; j <= SIZE; j++ ) C[i][j] = INFTY;
    
    for ( int i = 1; i <= SIZE; i++ ) C[i][i] = 0;
    
    for ( int j = 1; j <= SIZE - 1; j++ ){
        for ( int i = 1; i <= SIZE - j; i++ ){
            for ( int k = i + 1; k <= i + j; k++ ){
                // C[i][i+j] = min( C[i][i+j], 
                //                  C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1]);
                int cost = C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1];
                if ( cost < C[i][i+j] ){
                    C[i][i+j] =  cost;
                    B[i][i+j] = k;
                }
                
            }
        }
    }
}

void order( int i, int j ){
    if ( i == j ) cout << "M" << i;
    else{
        cout << "(";
        order( i, B[i][j]-1 ); order(B[i][j], j);
        cout << ")";
    }
}

void input(){
    cin >> SIZE;
    for ( int i = 1; i <= SIZE + 1; i++ ) cin >> R[i];
}

void output(){
    cout << "minimum cost = " << C[1][SIZE] << endl;
    order(1, SIZE);
    cout << endl;
}

main(){
    input();
    compute();
    output();
}




Sample Input

6
40 20 30 10 20 20 30

Sample Output

minimum cost = 36000
((M1(M2M3))((M4M5)M6))


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(1) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 国内予選 2001

2006.06.21 00:14  ACM/ICPC

ID 問題 難易度 考察
A Get a Rectangular Field ★☆ -
B Multi-column List ★★☆ -
C Jigsaw Puzzles for Computers ★★★ -
D Missing Numbers ★★☆ -
E Nets of Dice ★★★★? -

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 国内予選 2002

2006.06.21 00:12  ACM/ICPC

ID 問題 難易度 考察
A Exploring Caves -
B Pile Up! ★★☆ -
C Kanglish:Analysis on Artificial Language ★★☆ -
D What is the Number in my Mind ? ??? -
E Enclosing Circles ??? -

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 国内予選 2003

2006.06.21 00:04  ACM/ICPC

ID 問題 難易度 考察
A When Can We Meet? -
B Get Many Persimmon Trees -
C The Secret Number ★★★ -
D Building a Space Station ★★☆ -
E Square Carpets ★★★★☆ -

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 国内予選 2004

2006.06.21 00:01  ACM/ICPC

ID 問題 難易度 考察
A Hanafuda Shuffle
B Red and Black -
C Unit Fraction Partition ★★☆ -
D Circle and Points ★★☆ -
E Water Tank ★★★★★ -
F Name the Crossing ★★★☆ -

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 国内予選 2005

2006.06.20 23:56  ACM/ICPC

ID 問題 難易度 考察
A Ohgas' Fortune -
B Polygonal Line Search ★★ -
C Numeral System ★★ -
D Traveling by Stagecoach ★★★☆
E Earth Observation with a Mobile Robot Team ★★★★★ -
F Cleaning Robot ★★★

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 国内予選模擬コンテスト 2006

2006.06.20 23:44  ACM/ICPC

ID 問題 難易度 考察
A Misterious Gems -
B Amida, the City of Miracle -
C X-Ray Screening System ★★★ -
D Railroad Conflict ★★ -
E Data Center on Fire ★★★★★ -
F Water Pipe Construction ★★★ -

| コメント(0) | トラックバック(0) | ↑ページトップ |




ハフマン符号化 Huffman encoding

2006.06.11 21:58  貪欲法

ファイル圧縮 File compression
これから紹介する Greedy algorithm は、コミュニケーションシステムなどで扱われるデータの "情報量" を圧縮するために考案された符号化法 (encoding method) に関するものです。

一般的に、コンピュータで扱うファイルは冗長性を持っています。符号化は、ファイルは比較的少ない情報量しか持っていないという事実を利用し、ファイルを圧縮します。これらのテクニックは、主にテキストファイル、画像(ラスターイメージ)、サウンドのデジタルデータ、などに適用されます。

ランレングス符号化 Run-length encoding
テキストファイルにおける最も簡単な冗長性の1つが、同じ文字の(長い)繰り返しです。例えば、

AAAAAABBBCCAADDDDABCBBBCCCCCC

という文字列(アルファベットのみ)は、同じ文字の繰り返しからなる部分文字列を、[文字の出現回数、該当する文字] に置き換えることで、よりコンパクトに符号化することができます。

6A3B2C2A4DABC3B6C

これを、ランレングス符号化 (Run-length encoding) といいます。この符号化は、文字の繰り返しが多い2値のファイルに対しては効率的ですが、通常のテキストファイルに対しては効率的ではありません。なぜなら、繰り返し文字がある箇所でしか圧縮されないからです。

可変長符号化 Variable-length encoding
素朴な符号化を考えてみましょう。以下のように各アルファベットに 5 bits のバイナリコードが割り当てられていると仮定すると、

A 00000 (0)
B 00001 (1)
C 00010 (2)
. . . .
. . . .
Z 11001 (25)

文字列 "SARASARAHAIR" は

100100000010001000001001000000100010000000111000000100010001

と符号化されます(計 60 bits)。この符号を復号化することはとても簡単で、5 bits づつ読み取り、上記のテーブルに従って各文字を変換します。

ここで注目すべきことが、この文字列 "SARASARAHAIR" は、H は 1 回のみ、A は 5 回も出現しているにもかかわらず、どちらも 5 bits づつ割り当てられているということです。この符号をより短くするためのアイデアの1つが、最も多く出現する文字に最も短いビット列を割り当てることです。

可変長符号化 (Variable-length encoding) では、各文字に一定のビット列を割り当てる代わりに、テキスト内でより多く出現する文字により短いビット列を、より稀に出現する文字により長いビット列を割り当てます。

試しに、"SARASARAHAIR" では、A が 5 回、H が 1 回、I が 1 回、R が 3 回、S が 2 回、それぞれ出現するので、上記のアイデアから以下のようにビット列を割り当ててみましょう。

A → 0 H → 10 I → 11 R → 1 S → 01

このコードを用いて、"SARASARAHAIR" は

0101001010100111

と符号化することができます。これは、16 bits しか必要とせず、前の素朴な方法(60 bits)に比べるとかなり圧縮されていますが、実際のコードには成り得ません。なぜなら、復号化される文字列がビット列の区切りに依存してしまい一意に決まらないからです。例えば、上記の符号 0101001010100111 は、"ARARAAHHHARRR" や "SSASSSASI" など様々な文字列に変換できてしまうのです。しかし、以下のように特別な区切り文字 (delimiter) を用いたとしても、素朴な方法と比べれば符号の長さはコンパクトと言えるでしょう。

01-0-1-0-01-0-1-0-10-0-11-1

次は、文字列を区切り文字を用いずにコンパクトに符号化する方法を考えてみましょう。

もし、各文字に対応するビット列が、他のどの文字に対応するビット列の接頭語(prefix)になっていなければ、区切り文字が必要ないことが分かります。例えば、以下のようにビット列を割り当てると、

A → 11 H → 00 I → 010 R → 10 S → 011

"SARASARAHAIR" は

011111011011111011001101010

のように符号化されますが、復号化は一意に決まります(確認してみましょう)。

このような符号を生成するための簡単な方法の1つが、符号をバイナリツリーで表現することです。M 個の葉を持つ任意のバイナリツリーは、M 個(種類)の異なる文字を含む文字列を符号化するために用いることができます。このとき、ツリーの各葉を各文字に対応させます。各文字の符号は、ツリーの根から対応する葉へのパスによって決定します。このとき、左へ向かった場合 0、右へ向かった場合 1 とします。例えば、以下の2つのツリーは、"SARASARAHAIR" の符号を与えます。

ツリー 1 ツリー 2
encode1.gif
encode2.gif
A → 010
H → 10
I → 11
R → 011
S → 00
A → 0
H → 1110
I → 1111
R → 10
S → 110

このバイナリツリー表現は、どの文字に対応するビット列も他の文字に対応するビット列の接頭語にならないことを保障します。従って、生成された符号は、一意的に復号化されます。

ここで問題となるのが、符号化するためにどちらのバイナリツリーを用いるべきか?です。各ツリーを用いて "SARASARAHAIR" を符号化してみましょう。

ツリー 1 → 00010011010000100110101001011011
ツリー 2 → 1100100110010011100111110

ツリー 2 の方が短い符号を与えます。このように、与えられた任意の文字列に対して、最も短い符号を導くバイナリツリーを生成するためのアルゴリズムが D. Huffman が考案した ハフマン符号化(Huffman encoding)です。

ハフマン符号化 Huffman encoding
バイナリツリーを生成するために、ハフマン符号化は貪欲法(Greedy algorithm)を用います。このツリーをハフマン木と呼びます。ハフマン木に含まれるノードの集合を S とすると、ハフマン符号化は以下のように動作します。

1. 与えられた文字列に含まれる各文字の出現頻度を計算します。各文字に対応するノードをつくり、S に追加します。この時、これらのノードに、対応する文字の出現頻度を"重み"として割り当てます。
2. S から重みが最も低い2つのノードを取り出し、それらを子とする新しい親ノード(ルート)を作り S に追加します。この時、親ノードの重みとして、選ばれた2つの子の重みの和を割り当てます。
3. 2. の処理を S のサイズが 1 になるまで繰り返します。

与えられた文字列 "AAABCCXYZ" をハフマン符号化した様子を下図に示します。初期状態は S = {A, B, C, X, Y, Z} です。各ノードの ID を対応する文字の ASCIIコード にします。ただし、追加されるノードは 256 から始まる整数とします。S に含まれるノードは、緑色の背景を持ちます。

huffman.gif

このアルゴリズムによって、より小さい重みをもつ文字がルートから遠ざかり、より大きい重みをもつ文字がルートに近づきます。

実際に各文字に対応するビット列を生成するには、ハフマン木のルートから preorder でツリーを parse します。この時、左の子に向かうとき 0、右の子に向かうとき 1 を記録していきます(以下のプログラムを参照して下さい)。

以下に、ハフマン符号化のプログラム例を示します。バイナリツリーを作る過程で、アルゴリズムは S から重みの最も小さい2つのノードを優先して取り出し、さらに新しいノードを生成し S に追加していきます。従って S のデータ構造として優先順位キュー(Priority queue)を使うことは明白です。優先順位キューを用いた場合のハフマン符号化のオーダーは O(nlonn) となります。

// @author yutaka C++
#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>

using namespace std;

#define CHAR_SIZE 256
#define NODE_SIZE 512
#define TOLEFT '0'
#define TORIGHT '1'

class Node{
    public:
    int id, weight, left, right;
    Node(){ weight = 0; }
    Node( int id, int w, int l, int r ): id(id), weight(w), left(l), right(r){}
    
    bool operator < ( const Node &n ) const{
        return weight > n.weight;
    }
};

Node nodes[NODE_SIZE];
int newRootId;

void recursive( int id, string code ){
    if ( id < CHAR_SIZE ){
        printf("%c  %s\n", id, code.c_str()); return;
    }
    recursive( nodes[id].left, code + TOLEFT );
    recursive( nodes[id].right, code + TORIGHT );
}

// input the string to be encoded
void encoding( string text ){
    int w[CHAR_SIZE];
    
    // Compute the weight of each character
    for ( int i = 0; i < CHAR_SIZE; i++ ) w[i] = 0;
    for ( int i = 0; i < text.size(); i++ ) w[text[i]]++;
    
    // Output w[]
    for ( int i = 0; i < CHAR_SIZE; i++ ){
        if ( w[i] ) printf("%c : %d times\n", i, w[i]);
    }
    
    // Construct and initialize the priority queue
    priority_queue<Node> PQ;
    for ( int i = 0; i < CHAR_SIZE; i++ ) {
        if ( w[i] > 0 ){
            Node node = Node( i, w[i], -1, -1 );
            PQ.push( node );
            nodes[ node.id ] = node;
        }
    }
    
    // Construct the binary tree
    newRootId = CHAR_SIZE;
    
    while ( PQ.size() > 1 ){
        Node left = PQ.top(); PQ.pop();
        Node right = PQ.top(); PQ.pop();
        int weight = left.weight + right.weight;
        Node newRoot = Node( newRootId, weight, left.id, right.id );
        PQ.push( newRoot );
        nodes[ newRootId++ ] = newRoot;
    }
    
    // Output the binary tree constructed
    for ( int i = newRootId - 1; i >= CHAR_SIZE; i-- ){
        if ( nodes[i].left >= CHAR_SIZE )
        printf("left  son of %4d is %4d\n", i, nodes[i].left );
        else
        printf("left  son of %4d is %4c\n", i, nodes[i].left );
        if ( nodes[i].right >= CHAR_SIZE )
        printf("right son of %4d is %4d\n", i, nodes[i].right );
        else
        printf("right son of %4d is %4c\n", i, nodes[i].right );
    }
}

void decoding(){
    recursive( newRootId - 1, "");
}

main(){
    string text; cin >> text;
    encoding( text );
    decoding();
}

Sample Input

SARASARAHAIR

Sample Output

A : 5 times
H : 1 times
I : 1 times
R : 3 times
S : 2 times
left  son of  259 is    A
right son of  259 is  258
left  son of  258 is    R
right son of  258 is  257
left  son of  257 is    S
right son of  257 is  256
left  son of  256 is    H
right son of  256 is    I
A  0
R  10
S  110
H  1110
I  1111




テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




貪欲法 Greedy algorithms

2006.06.06 17:17  貪欲法

"Greedy" とは、食べ物や飲み物などに対する強い "欲求" や "欲望" を意味しますが、Greedy algorithms (貪欲アルゴリズム、よくばり法)では、この食べ物や飲み物をアルゴリズムで扱うデータと見なすことができます。

一般的に、最適化問題 (optimazation problems) のためのアルゴリズムの多くは、あるデータの "選択" の繰り返しという構造になっています。Greedy algorithms は、各計算ステップで、局所的に最適(その時点で最も最適と思われるもの)な選択を繰り返し、最終的に大域的な最適解を求める方法です。

すでに紹介したものも含めて、以下のように Greedy algorithms は多くの問題に対して、最適解を求めることができます。このセクションでは、これらの問題と対応するアルゴリズムを紹介します。

随時追加予定です。


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。