Ⅴ．グラフ上の探索

  1. 横型探索と縦型探索

    1. 横型探索

      　　ここでは，グラフの探索について考えてみます．最も基本的な探索方法は，横型探索（幅優先探索）と縦型探索（深さ優先探索）です．例えば，右図に示すようなグラフについて考えてみます．横型探索では，深さが浅いものから順に探索していきます．右図においては，S -> (A, B, C) -> (D, E, F, G) の順で探索していきます（括弧内の順序は任意）．最も簡単な方法は，キューを利用する方法です．キューの先頭要素（グラフのノード）を取り出し，それが目的とするノードでなければ，そのノードから到達できるノードをキューに追加する，といった操作を繰り返すだけです．以下に示すプログラムでは，C++ 標準ライブラリ内の queue クラスを利用して書かれています． 
      01	/****************************/
02	/* 横型探索（幅優先探索）   */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <stdio.h>
06	#include <queue>
07	
08	using namespace std;
09	
10	void print(queue<char> &q) {
11		printf("   queue の状態： ");
12		if (q.empty())
13			printf("空です\n");
14		else
15			printf("先頭及び最後尾： %c %c，　要素数： %d\n", q.front(), q.back(), q.size());
16	}
17	
18	int main()
19	{
20		queue<char> q;
21	
22		printf("S の追加\n");
23		q.push('S');
24		print(q);
25	
26		printf("先頭 S を削除し，A, B, C を追加\n");
27		q.pop();
28		q.push('A');
29		q.push('B');
30		q.push('C');
31		print(q);
32	
33		printf("先頭 A を削除し，D, E を追加\n");
34		q.pop();
35		q.push('D');
36		q.push('E');
37		print(q);
38	
39		printf("先頭 B を削除\n");
40		q.pop();
41		print(q);
42	
43		printf("先頭 C を削除し，F, G を追加\n");
44		q.pop();
45		q.push('F');
46		q.push('G');
47		print(q);
48	
49		printf("先頭 D を削除\n");
50		q.pop();
51		print(q);
52	
53		printf("先頭 E を削除\n");
54		q.pop();
55		print(q);
56	
57		printf("先頭 F を削除\n");
58		q.pop();
59		print(q);
60	
61		printf("先頭 G を削除\n");
62		q.pop();
63		print(q);
64	
65		return 0;
66	}
      （出力） 
      S の追加
   queue の状態： 先頭及び最後尾： S S，　要素数： 1
先頭 S を削除し，A, B, C を追加
   queue の状態： 先頭及び最後尾： A C，　要素数： 3
先頭 A を削除し，D, E を追加
   queue の状態： 先頭及び最後尾： B E，　要素数： 4
先頭 B を削除
   queue の状態： 先頭及び最後尾： C E，　要素数： 3
先頭 C を削除し，F, G を追加
   queue の状態： 先頭及び最後尾： D G，　要素数： 4
先頭 D を削除
   queue の状態： 先頭及び最後尾： E G，　要素数： 3
先頭 E を削除
   queue の状態： 先頭及び最後尾： F G，　要素数： 2
先頭 F を削除
   queue の状態： 先頭及び最後尾： G G，　要素数： 1
先頭 G を削除
   queue の状態： 空です

    2. 縦型探索

      　　縦型探索では，深さが深いものから順に探索していきます．先の図においては，S -> C -> (F, G) -> B -> A -> (D, E) の順で探索していきます（括弧内の順序は任意）．S の次に，A または B を選択しても構いません．最も簡単な方法は，スタックを利用する方法です．スタックの先頭要素（グラフのノード）を取り出し，それが目的とするノードでなければ，そのノードから到達できるノードをスタックに追加する，といった操作を繰り返すだけです．横型探索と基本的な流れは同じですが，キューとは異なり，スタックでは最も最近追加したノードが先頭に来るため縦型探索になります．以下に示すプログラムでは，C++ 標準ライブラリ内の stack クラスを利用して書かれています．

      　　この例では，深さが 3 までですが，さらに深いノードがあった場合，例えば，G，（深さ 4 のノード），（深さ 5 のノード），・・・ のように，ひたすら深いノードに向かって探索を行ってしまいます．そこで，縦型探索においては，一般に，深さ制限を設けます．そのような意味から，この例は深さ制限が 3 である場合と見なせます．例えば，G までくると，深さ制限となりますので，上のノードまで戻り（バックトラックし），次に F をチェックします．再び深さ制限になりますので，ノード S までバックトラックし，次にノード B をチェックすることになります． 
      01	/****************************/
02	/* 縦型探索（深さ優先探索） */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <stdio.h>
06	#include <stack>
07	
08	using namespace std;
09	
10	void print(stack<char> &q) {
11		printf("   stack の状態： ");
12		if (q.empty())
13			printf("空です\n");
14		else
15			printf("先頭： %c，　要素数： %d\n", q.top(), q.size());
16	}
17	
18	int main()
19	{
20		stack<char> q;
21	
22		printf("S の追加\n");
23		q.push('S');
24		print(q);
25	
26		printf("先頭 S を削除し，A, B, C を追加\n");
27		q.pop();
28		q.push('A');
29		q.push('B');
30		q.push('C');
31		print(q);
32	
33		printf("先頭 C を削除し，F, G を追加\n");
34		q.pop();
35		q.push('F');
36		q.push('G');
37		print(q);
38	
39		printf("先頭 G を削除\n");
40		q.pop();
41		print(q);
42	
43		printf("先頭 F を削除\n");
44		q.pop();
45		print(q);
46	
47		printf("先頭 B を削除\n");
48		q.pop();
49		print(q);
50	
51		printf("先頭 A を削除し，D, E を追加\n");
52		q.pop();
53		q.push('D');
54		q.push('E');
55		print(q);
56	
57		printf("先頭 E を削除\n");
58		q.pop();
59		print(q);
60	
61		printf("先頭 D を削除\n");
62		q.pop();
63		print(q);
64	
65		return 0;
66	}
      （出力） 
      S の追加
   stack の状態： 先頭： S，　要素数： 1
先頭 S を削除し，A, B, C を追加
   stack の状態： 先頭： C，　要素数： 3
先頭 C を削除し，F, G を追加
   stack の状態： 先頭： G，　要素数： 4
先頭 G を削除
   stack の状態： 先頭： F，　要素数： 3
先頭 F を削除
   stack の状態： 先頭： B，　要素数： 2
先頭 B を削除
   stack の状態： 先頭： A，　要素数： 1
先頭 A を削除し，D, E を追加
   stack の状態： 先頭： E，　要素数： 2
先頭 E を削除
   stack の状態： 先頭： D，　要素数： 1
先頭 D を削除
   stack の状態： 空です

    3. 8 パズルへの応用

      　　もう少し複雑な問題を解いてみます．8 パズルでは，9 個のコマを置く場所（ 3 行 3 列の配列）が用意してあり，その中に 1 から 8 の 8 つのコマが置かれています．1 箇所だけコマが置かれていない場所がありますので，その上下左右にあるコマをそこに移動することが可能です．例えば，下の図に示すように（以下，左側を例１，右側を例２と呼ぶ），初期状態（各図の左側）から，できるだけ少ない回数のコマの移動によって，目標状態（各図の右側）に持って行くことになります．

      例えば，例１では，以下に示すのが最適解になります．

      　　プログラムは，横型探索によって上記の問題を解いた例です．8 パズルの場合，コマの移動によっては，以前と同じ状態になってしまいます．そのまま放置すれば，無限ループに陥ってしまいますので，C++ 標準ライブラリ内の map クラスを使用して，同じ状態か否かのチェックを行っています．出力結果に示すのが，このプログラムを実行した結果です．「展開とチェック」の後ろの数字の内，最初の数字が展開したノードの数（キューに入れられたノードの数），後ろの数字がそれらの内，解か否かをチェックしたノードの数です．右側の問題に対しては，かなり多くのノードを展開していることが分かると思います．なお，以下のプログラムにおいても同様ですが，このプログラムは最適解を得るためのものではありません．解が得られた時点でプログラムを終了しています．ただし，この問題の場合は，横型探索によって最適解が得られますので，得られた結果は最適解になっています． 
      001	/*********************************/
002	/* 横型探索（８パズル）          */
003	/*           coded by Y.Suganuma */
004	/*********************************/
005	#include <stdio.h>
006	#include <queue>
007	#include <map>
008	#include <string>
009	
010	using namespace std;
011	
012	class Depth
013	{
014		public:
015			int dep;
016			string prev;
017			Depth (string str, int dep1)
018			{
019				prev = str;   // 前の状態
020				dep  = dep1;   // 深さ
021			}
022	};
023	
024	/********************************/
025	/* コマの移動                   */
026	/*      str : 現在の状態        */
027	/*      res : 移動後の状態      */
028	/*      return : 移動後の状態数 */
029	/********************************/
030	int move(string str, string *res)
031	{
032		int k, n = 0;
033		string str1;
034	
035		k = str.find("0");
036		switch(k) {
037			case 0:
038				str1   = str.replace(k, 1, str, k+3, 1);
039				str1   = str1.replace(k+3, 1, 1, '0');
040				res[n] = str1;
041				n++;
042				str1   = str.replace(k, 1, str, k+1, 1);
043				str1   = str1.replace(k+1, 1, 1, '0');
044				res[n] = str1;
045				n++;
046				break;
047			case 1:
048				str1   = str.replace(k, 1, str, k+3, 1);
049				str1   = str1.replace(k+3, 1, 1, '0');
050				res[n] = str1;
051				n++;
052				str1   = str.replace(k, 1, str, k-1, 1);
053				str1   = str1.replace(k-1, 1, 1, '0');
054				res[n] = str1;
055				n++;
056				str1   = str.replace(k, 1, str, k+1, 1);
057				str1   = str1.replace(k+1, 1, 1, '0');
058				res[n] = str1;
059				n++;
060				break;
061			case 2:
062				str1   = str.replace(k, 1, str, k+3, 1);
063				str1   = str1.replace(k+3, 1, 1, '0');
064				res[n] = str1;
065				n++;
066				str1   = str.replace(k, 1, str, k-1, 1);
067				str1   = str1.replace(k-1, 1, 1, '0');
068				res[n] = str1;
069				n++;
070				break;
071			case 3:
072				str1   = str.replace(k, 1, str, k-3, 1);
073				str1   = str1.replace(k-3, 1, 1, '0');
074				res[n] = str1;
075				n++;
076				str1   = str.replace(k, 1, str, k+3, 1);
077				str1   = str1.replace(k+3, 1, 1, '0');
078				res[n] = str1;
079				n++;
080				str1   = str.replace(k, 1, str, k+1, 1);
081				str1   = str1.replace(k+1, 1, 1, '0');
082				res[n] = str1;
083				n++;
084				break;
085			case 4:
086				str1   = str.replace(k, 1, str, k-3, 1);
087				str1   = str1.replace(k-3, 1, 1, '0');
088				res[n] = str1;
089				n++;
090				str1   = str.replace(k, 1, str, k+3, 1);
091				str1   = str1.replace(k+3, 1, 1, '0');
092				res[n] = str1;
093				n++;
094				str1   = str.replace(k, 1, str, k-1, 1);
095				str1   = str1.replace(k-1, 1, 1, '0');
096				res[n] = str1;
097				n++;
098				str1   = str.replace(k, 1, str, k+1, 1);
099				str1   = str1.replace(k+1, 1, 1, '0');
100				res[n] = str1;
101				n++;
102				break;
103			case 5:
104				str1   = str.replace(k, 1, str, k-3, 1);
105				str1   = str1.replace(k-3, 1, 1, '0');
106				res[n] = str1;
107				n++;
108				str1   = str.replace(k, 1, str, k+3, 1);
109				str1   = str1.replace(k+3, 1, 1, '0');
110				res[n] = str1;
111				n++;
112				str1   = str.replace(k, 1, str, k-1, 1);
113				str1   = str1.replace(k-1, 1, 1, '0');
114				res[n] = str1;
115				n++;
116				break;
117			case 6:
118				str1   = str.replace(k, 1, str, k-3, 1);
119				str1   = str1.replace(k-3, 1, 1, '0');
120				res[n] = str1;
121				n++;
122				str1   = str.replace(k, 1, str, k+1, 1);
123				str1   = str1.replace(k+1, 1, 1, '0');
124				res[n] = str1;
125				n++;
126				break;
127			case 7:
128				str1   = str.replace(k, 1, str, k-3, 1);
129				str1   = str1.replace(k-3, 1, 1, '0');
130				res[n] = str1;
131				n++;
132				str1   = str.replace(k, 1, str, k-1, 1);
133				str1   = str1.replace(k-1, 1, 1, '0');
134				res[n] = str1;
135				n++;
136				str1   = str.replace(k, 1, str, k+1, 1);
137				str1   = str1.replace(k+1, 1, 1, '0');
138				res[n] = str1;
139				n++;
140				break;
141			case 8:
142				str1   = str.replace(k, 1, str, k-3, 1);
143				str1   = str1.replace(k-3, 1, 1, '0');
144				res[n] = str1;
145				n++;
146				str1   = str.replace(k, 1, str, k-1, 1);
147				str1   = str1.replace(k-1, 1, 1, '0');
148				res[n] = str1;
149				n++;
150				break;
151		}
152	
153		return n;
154	}
155	
156	/*************************/
157	/* 横型探索（８パズル）  */
158	/*      start : 初期状態 */
159	/*      goal : 目標状態  */
160	/*************************/
161	void width(string start, string goal)
162	{
163		int i1, n, node1 = 1, node2 = 0, dep = 1, ct = 1;
164		string str, res[4];
165		queue<pair<string, int> > q;
166		map<string, Depth> m;
167		map<string, Depth>::iterator it;
168	
169		m.insert(pair<string, Depth>(start, Depth("",dep)));
170		q.push(pair<string, int>(start, dep));
171		while (!q.empty()) {
172			str = q.front().first;
173			dep = q.front().second;
174			node2++;
175						// ゴール
176			if (str == goal) {
177				ct = dep;
178				break;
179			}
180						// ゴールでない
181						// コマを移動し，同じ状態のものがなければキューに追加
182			else {
183				q.pop();
184				n = move(str, res);
185				for (i1 = 0; i1 < n; i1++) {
186					it = m.find(res[i1]);   // 同じ状態か？
187					if (it == m.end()) {
188						m.insert(pair<string, Depth>(res[i1], Depth(str,dep+1)));
189						q.push(pair<string, int>(res[i1], dep+1));
190						node1++;
191					}
192				}
193			}
194		}
195						// 結果の出力
196		printf("   展開とチェック： %d %d，　最短距離： %d\n", node1, node2, ct);
197		while (str.length() > 0) {
198			printf("\n      %c %c %c\n", str.at(0), str.at(1), str.at(2));
199			printf("      %c %c %c\n", str.at(3), str.at(4), str.at(5));
200			printf("      %c %c %c\n", str.at(6), str.at(7), str.at(8));
201			it  = m.find(str);
202			str = ((*it).second).prev;
203		}
204	}
205	
206	int main()
207	{
208		string goal = "123804765";
209	
210		printf("例１\n");
211		string start = "283164705";
212		width(start, goal);
213	
214		printf("例２\n");
215		start = "216408753";
216		width(start, goal);
217	
218		return 0;
219	}
      208 行目

      　　目標状態を設定しています．状態は，ゲームの状態を 3 行 3 列の配列として見たとき，コマが置かれた配列の各要素の値を，[0][0]，[0][1]，[0][2]，[1][0]，･･･，[2][2] の順に，文字として並べた文字列として表現されます．なお，0 は空白を意味します．

      211 行目～ 212 行目，215 行目～ 216 行目

      　　例１，及び，例２の初期状態を設定し，初期状態と目標状態を引数として，解を求めるための関数 width（ 161 行目～ 204 行目）を呼んでいます．

      163 行目

      　　node1 は queue に入れたノード（状態）の数，node2 は解か否かをチェックしたノード（状態）の数，また，dep は現在の深さです．

      169 行目

      　　状態（ここでは，初期状態）をキーとして，クラス Depth のオブジェクトを対応する値として，map クラスのオブジェクト m に追加しています．クラス Depth （ 012 行目～ 022 行目）は，現在の状態の深さを表すメンバー変数 dep，及び，現在の状態になる前の状態を表すメンバー変数 prev から構成されています．ここでは，前の状態として空の文字列，また，深さとして 1 が設定されます．

      170 行目

      　　状態（ここでは，初期状態）と現在の深さ（ 1 ）のペアを，queue クラスのオブジェクト q に追加しています．

      171 行目

      　　この while 文によって，q が空になるまで，172 行目～ 193 行目が繰り返されます．

      172 行目～ 173 行目

      　　q の先頭ノードに対するデータを取得しています．

      176 行目～ 179 行目

      　　取得したデータが目標状態と一致した場合は，繰り返しから抜け出します．

      182 行目～ 193 行目

      　　目標状態と一致しなかった場合の処理です．q の先頭ノードを削除し（ 183 行目），そのノードから移動可能な状態を関数 move（ 030 行目～ 154 行目）によって調べます（ 184 行目）．その結果，移動可能な状態の数（ n ）とその状態（ res ）が得られます．得られた各状態に対して，既にチェックしたことがある状態か否かを調べ（ 186 行目），そうでなかったら，その状態を m 及び q に追加します（ 188 行目～ 189 行目）．

      030 行目～ 154 行目

      　　移動可能な状態を調べるための関数です．まず，状態の中の 0 の位置を探し（ 035 行目），その値によって，移動可能な状態を調べます．例えば，k の値が 0 の場合は，配列で言えば [0][0] の位置にありますので，0 を下（ 038，039 行目），または，右（ 042，043 行目）に移動可能です．

      196 行目～ 203 行目

      　　初期状態から目標状態への移動方法を，目標状態から逆に出力しています．

      （出力）　このプログラムによって，以下に示すような出力が得られます． 
      例１
   展開とチェック： 62 35，　最短距離： 6

      1 2 3
      8 0 4
      7 6 5

      1 2 3
      0 8 4
      7 6 5

      0 2 3
      1 8 4
      7 6 5

      2 0 3
      1 8 4
      7 6 5

      2 8 3
      1 0 4
      7 6 5

      2 8 3
      1 6 4
      7 0 5
例２
   展開とチェック： 34299 22912，　最短距離： 19

      1 2 3
      8 0 4
      7 6 5

      1 2 3
      8 4 0
      7 6 5

      1 2 0
      8 4 3
      7 6 5

      1 0 2
      8 4 3
      7 6 5

      1 4 2
      8 0 3
      7 6 5

      1 4 2
      8 6 3
      7 0 5

      1 4 2
      8 6 3
      7 5 0

      1 4 2
      8 6 0
      7 5 3

      1 4 2
      8 0 6
      7 5 3

      1 4 2
      0 8 6
      7 5 3

      0 4 2
      1 8 6
      7 5 3

      4 0 2
      1 8 6
      7 5 3

      4 2 0
      1 8 6
      7 5 3

      4 2 6
      1 8 0
      7 5 3

      4 2 6
      1 0 8
      7 5 3

      4 2 6
      0 1 8
      7 5 3

      0 2 6
      4 1 8
      7 5 3

      2 0 6
      4 1 8
      7 5 3

      2 1 6
      4 0 8
      7 5 3
      　　一般に，どのノードを最初に展開すべきか（チェックすべきか）を何らかの知識を使用して決めることにより，横型探索や縦型探索のような機械的な探索方法より，探索時間を短くすることが可能です．ここでは，各ノード（状態）に対して，以下に示す評価値を計算し，この値の小さいノードから順に探索していきます． 

      f(n) = g(n) + h(n) 
　　g(n)： 節点 n の深さ 
　　h(n) = p(n) + 3s(n) 
　　　　p(n)： 各コマの正しい位置からの距離を加えた値
　　　　s(n)： 中心以外のコマに対し，その次のコマが正しい順序になっていなければ 2，
　　　　　　　　そうでなければ 0，中心の駒には 1 を与える事によって得られる得点
      　　下に示すプログラムは，この方法によって上記の問題を解いた例です．その下に示すのが，このプログラムを実行した結果です．プログラム全体のアルゴリズムは，横型探索の場合と同じですが，評価値が小さいものをキューの先頭に置くため，C++ 標準ライブラリ内の priority_queue クラスを使用しています．そのため，クラス Node を新たに定義し（ 012 行目～ 023 行目），クラス Depth にメンバー変数として評価値を表す est を加え，さらに，ノードの評価値を計算するための関数 estimation（ 055 行目～ 105 行目）を追加しています．また，priority_queue クラスにおける比較を行うため，比較演算子のオーバーロードを行っています（ 038 行目～ 046 行目）． 
      001	/*********************************/
002	/* 知識を用いた探索（８パズル）  */
003	/*           coded by Y.Suganuma */
004	/*********************************/
005	#include <stdio.h>
006	#include <queue>
007	#include <map>
008	#include <string>
009	
010	using namespace std;
011	
012	class Node
013	{
014		public:
015			int dep, est;
016			string str;
017			Node (string str1, int dep1, int est1)
018			{
019				str = str1;   // 状態
020				dep = dep1;   // 深さ
021				est = est1;   // 評価値
022			}
023	};
024	
025	class Depth
026	{
027		public:
028			int dep, est;
029			string prev;
030			Depth (string prev1, int dep1, int est1)
031			{
032				prev = prev1;   // 前の状態
033				dep  = dep1;   // 深さ
034				est  = est1;   // 評価値
035			}
036	};
037	
038	bool operator< (Node n1, Node n2)
039	{
040		bool sw = true;
041		if (n1.est == n2.est)
042			sw = (n1.str < n2.str) ? true : false;
043	 	else
044			sw = (n1.est > n2.est) ? true : false;
045		return sw;
046	}
047	
048	/************************/
049	/* ノードの評価         */
050	/*      dep : 深さ      */
051	/*      str : 状態      */
052	/*      goal : 目標状態 */
053	/*      return : 評価値 */
054	/************************/
055	int estimation(int dep, string str, string goal)
056	{
057		int i1, i2, i3, i4, k1, k2, pi = dep, sw;
058		char cg[3][3], cn[3][3];
059	
060		for (i1 = 0; i1 < 9; i1++) {
061			k1 = i1 / 3;
062			k2 = i1 - 3 * k1;
063			cg[k1][k2] = goal.at(i1) - '0';
064		}
065		for (i1 = 0; i1 < 9; i1++) {
066			k1 = i1 / 3;
067			k2 = i1 - 3 * k1;
068			cn[k1][k2] = str.at(i1) - '0';
069		}
070	
071		for (i1 = 0; i1 < 3; i1++) {
072			for (i2 = 0; i2 < 3; i2++) {
073				sw = 1;
074				for (i3 = 0; i3 < 3 && sw > 0; i3++) {
075					for (i4 = 0; i4 < 3 && sw > 0; i4++) {
076						if (cg[i3][i4] == cn[i1][i2]) {
077							sw  = 0;
078							pi += (abs(i3-i1) + abs(i4-i2));
079						}
080					}
081				}
082			}
083		}
084	
085		if (cn[1][1] != '0')
086			pi++;
087		if (cn[0][1] != (cn[0][0]+1)%9)
088			pi += 2;
089		if (cn[0][2] != (cn[0][1]+1)%9)
090			pi += 2;
091		if (cn[1][2] != (cn[0][2]+1)%9)
092			pi += 2;
093		if (cn[2][2] != (cn[1][2]+1)%9)
094			pi += 2;
095		if (cn[2][1] != (cn[2][2]+1)%9)
096			pi += 2;
097		if (cn[2][0] != (cn[2][1]+1)%9)
098			pi += 2;
099		if (cn[1][0] != (cn[2][0]+1)%9)
100			pi += 2;
101		if (cn[0][0] != (cn[1][0]+1)%9)
102			pi += 2;
103	
104		return pi;
105	}
106	
107	/********************************/
108	/* コマの移動                   */
109	/*      str : 現在の状態        */
110	/*      res : 移動後の状態      */
111	/*      return : 移動後の状態数 */
112	/********************************/
113	int move(string str, string *res)
114	{
115		int k, n = 0;
116		string str1;
117	
118		k = str.find("0");
119		switch(k) {
120			case 0:
121				str1   = str.replace(k, 1, str, k+3, 1);
122				str1   = str1.replace(k+3, 1, 1, '0');
123				res[n] = str1;
124				n++;
125				str1   = str.replace(k, 1, str, k+1, 1);
126				str1   = str1.replace(k+1, 1, 1, '0');
127				res[n] = str1;
128				n++;
129				break;
130			case 1:
131				str1   = str.replace(k, 1, str, k+3, 1);
132				str1   = str1.replace(k+3, 1, 1, '0');
133				res[n] = str1;
134				n++;
135				str1   = str.replace(k, 1, str, k-1, 1);
136				str1   = str1.replace(k-1, 1, 1, '0');
137				res[n] = str1;
138				n++;
139				str1   = str.replace(k, 1, str, k+1, 1);
140				str1   = str1.replace(k+1, 1, 1, '0');
141				res[n] = str1;
142				n++;
143				break;
144			case 2:
145				str1   = str.replace(k, 1, str, k+3, 1);
146				str1   = str1.replace(k+3, 1, 1, '0');
147				res[n] = str1;
148				n++;
149				str1   = str.replace(k, 1, str, k-1, 1);
150				str1   = str1.replace(k-1, 1, 1, '0');
151				res[n] = str1;
152				n++;
153				break;
154			case 3:
155				str1   = str.replace(k, 1, str, k-3, 1);
156				str1   = str1.replace(k-3, 1, 1, '0');
157				res[n] = str1;
158				n++;
159				str1   = str.replace(k, 1, str, k+3, 1);
160				str1   = str1.replace(k+3, 1, 1, '0');
161				res[n] = str1;
162				n++;
163				str1   = str.replace(k, 1, str, k+1, 1);
164				str1   = str1.replace(k+1, 1, 1, '0');
165				res[n] = str1;
166				n++;
167				break;
168			case 4:
169				str1   = str.replace(k, 1, str, k-3, 1);
170				str1   = str1.replace(k-3, 1, 1, '0');
171				res[n] = str1;
172				n++;
173				str1   = str.replace(k, 1, str, k+3, 1);
174				str1   = str1.replace(k+3, 1, 1, '0');
175				res[n] = str1;
176				n++;
177				str1   = str.replace(k, 1, str, k-1, 1);
178				str1   = str1.replace(k-1, 1, 1, '0');
179				res[n] = str1;
180				n++;
181				str1   = str.replace(k, 1, str, k+1, 1);
182				str1   = str1.replace(k+1, 1, 1, '0');
183				res[n] = str1;
184				n++;
185				break;
186			case 5:
187				str1   = str.replace(k, 1, str, k-3, 1);
188				str1   = str1.replace(k-3, 1, 1, '0');
189				res[n] = str1;
190				n++;
191				str1   = str.replace(k, 1, str, k+3, 1);
192				str1   = str1.replace(k+3, 1, 1, '0');
193				res[n] = str1;
194				n++;
195				str1   = str.replace(k, 1, str, k-1, 1);
196				str1   = str1.replace(k-1, 1, 1, '0');
197				res[n] = str1;
198				n++;
199				break;
200			case 6:
201				str1   = str.replace(k, 1, str, k-3, 1);
202				str1   = str1.replace(k-3, 1, 1, '0');
203				res[n] = str1;
204				n++;
205				str1   = str.replace(k, 1, str, k+1, 1);
206				str1   = str1.replace(k+1, 1, 1, '0');
207				res[n] = str1;
208				n++;
209				break;
210			case 7:
211				str1   = str.replace(k, 1, str, k-3, 1);
212				str1   = str1.replace(k-3, 1, 1, '0');
213				res[n] = str1;
214				n++;
215				str1   = str.replace(k, 1, str, k-1, 1);
216				str1   = str1.replace(k-1, 1, 1, '0');
217				res[n] = str1;
218				n++;
219				str1   = str.replace(k, 1, str, k+1, 1);
220				str1   = str1.replace(k+1, 1, 1, '0');
221				res[n] = str1;
222				n++;
223				break;
224			case 8:
225				str1   = str.replace(k, 1, str, k-3, 1);
226				str1   = str1.replace(k-3, 1, 1, '0');
227				res[n] = str1;
228				n++;
229				str1   = str.replace(k, 1, str, k-1, 1);
230				str1   = str1.replace(k-1, 1, 1, '0');
231				res[n] = str1;
232				n++;
233				break;
234		}
235	
236		return n;
237	}
238	
239	/********************************/
240	/* 知識を用いた探索（８パズル） */
241	/*      start : 初期状態        */
242	/*      goal : 目標状態         */
243	/********************************/
244	void intel(string start, string goal)
245	{
246		int i1, n, node1 = 1, node2 = 0, dep = 1, ct = 1, est;
247		string str, res[4];
248		priority_queue<Node> p;
249		map<string, Depth> m;
250		map<string, Depth>::iterator it;
251		bool sw;
252	
253		est = estimation(dep, start, goal);
254		m.insert(pair<string, Depth>(start, Depth("",dep,est)));
255		p.push(Node(start,dep,est));
256		while (!p.empty()) {
257			str = p.top().str;
258			dep = p.top().dep;
259			node2++;
260						// ゴール
261			if (str == goal) {
262				ct = dep;
263				break;
264			}
265						// ゴールでない
266						// コマを移動し，同じ状態のものがなければキューに追加
267			else {
268				p.pop();
269				n = move(str, res);
270				for (i1 = 0; i1 < n; i1++) {
271					sw  = true;
272					est = estimation(dep+1, res[i1], goal);
273					it  = m.find(res[i1]);   // 同じ状態か？
274					if (it != m.end()) {
275						if (est < ((*it).second).est)
276							m.erase(it);
277						else
278							sw = false;
279					}
280					if (sw) {
281						m.insert(pair<string, Depth>(res[i1], Depth(str,dep+1,est)));
282						p.push(Node(res[i1], dep+1, est));
283						node1++;
284					}
285				}
286			}
287		}
288						// 結果の出力
289		printf("   展開とチェック： %d %d，　最短距離： %d\n", node1, node2, ct);
290		while (str.length() > 0) {
291			printf("\n      %c %c %c\n", str.at(0), str.at(1), str.at(2));
292			printf("      %c %c %c\n", str.at(3), str.at(4), str.at(5));
293			printf("      %c %c %c\n", str.at(6), str.at(7), str.at(8));
294			it  = m.find(str);
295			str = ((*it).second).prev;
296		}
297	}
298	
299	int main()
300	{
301		string goal = "123804765";
302	
303		printf("例１\n");
304		string start = "283164705";
305		intel(start, goal);
306	
307		printf("例２\n");
308		start = "216408753";
309		intel(start, goal);
310	
311		return 0;
312	}
      （出力） 
      例１
   展開とチェック： 12 6，　最短距離： 6

      1 2 3
      8 0 4
      7 6 5

      1 2 3
      0 8 4
      7 6 5

      0 2 3
      1 8 4
      7 6 5

      2 0 3
      1 8 4
      7 6 5

      2 8 3
      1 0 4
      7 6 5

      2 8 3
      1 6 4
      7 0 5
例２
   展開とチェック： 201 111，　最短距離： 19

      1 2 3
      8 0 4
      7 6 5

      1 0 3
      8 2 4
      7 6 5

      0 1 3
      8 2 4
      7 6 5

      8 1 3
      0 2 4
      7 6 5

      8 1 3
      2 0 4
      7 6 5

      8 1 3
      2 4 0
      7 6 5

      8 1 0
      2 4 3
      7 6 5

      8 0 1
      2 4 3
      7 6 5

      0 8 1
      2 4 3
      7 6 5

      2 8 1
      0 4 3
      7 6 5

      2 8 1
      4 0 3
      7 6 5

      2 8 1
      4 6 3
      7 0 5

      2 8 1
      4 6 3
      7 5 0

      2 8 1
      4 6 0
      7 5 3

      2 8 1
      4 0 6
      7 5 3

      2 0 1
      4 8 6
      7 5 3

      2 1 0
      4 8 6
      7 5 3

      2 1 6
      4 8 0
      7 5 3

      2 1 6
      4 0 8
      7 5 3

  2. 動的計画法（ Dynamic Programming ）

    　　「決定の全系列にわたって最適化を行うためには，初期の状態と最初の決定がどんなものであっても，残りの決定は最初の決定から生じた状態に関して最適な政策を構成していなければならない」ということを，最適性の原理と呼びます．別の表現をすれば，「最適経路中の部分経路もまた最適経路になっている」ということを意味しています．

    　　動的計画法（ DP: Dynamic Programming ）は，この原理を利用して最適化問題を解きます．基本的に，動的システムの最適化に利用される方法ですが，問題を，多段決定問題，つまり，各段（各ステップ）における決定の系列を求めるような問題に変換できれば，動的計画法によって解くことが可能です．例えば，

    目的関数： f(x) = f1(x1) + ･･･ + fn(xn)
    制約条件： x1 + ･･･ + xn = a，　　xi ≧ 0

    のような問題は，最適性の原理に従って，

    φi(ai) = max [fi(xi) + φi-1(ai - xi)]　　　i = 2, ･･･, n　　　0 ≦ xi ≦ a
    φ1(a1) = max [f1(x1)] = f1(a1)　　　0 ≦ x1 ≦ a

    のような再帰方程式に変換し，動的計画法によって解くことが可能です．つまり，上右図に示すように，ステップ (k+1) の状態 j におけるコストは，ステップ k （ k 段目）の各状態におけるコストに，その状態からステップ (k+1) （ (k+1) 段目）の状態 j に移行するためにかかるコストを加えたものの内最小（最大）のものになります．これを，初期状態から目標状態まで繰り返せば解が得られます．ここでは，以下に示すような問題を解いてみます．その結果を図示すると，右図のようになります．

    ［例］ある会社に 4 単位（各段 - 各ステップ - における状態の数が 4 ）の資金があり，3 種類（ 1 ～ 3 段目，1 ～ 3 ステップ）の投資先が候補にあるとします．資金は単位でしか配分できないものとしたとき，利益

    f(x) = f1(x1) + f2(x2) + f3(x3)

    を最大にする投資先をどのようにしたらよいのでしょうか．ただし，3 種類の投資先に対する利益関数は次の通りとします．

    投資額： x 1 2 3 4
    1 番目の投資先へ投資したときの利益： f1(x) 8 18 22 24
    2 番目の投資先へ投資したときの利益： f2(x) 3 6 9 12
    3 番目の投資先へ投資したときの利益： f3(x) 6 7 8 10 

    001	/**********************************/
002	/* 動的計画法（資源配分問題）     */
003	/*      coded by Y.Suganuma       */
004	/**********************************/
005	#include <stdio.h>
006	
007	/*****************************************/
008	/* 動的計画法による資源配分問題          */
009	/*      p : 現在計算中の投資先           */
010	/*      n_toshi : 投資先の数             */
011	/*      step : 資金の投資単位            */
012	/*      n_case : 資金の投資ケース数      */
013	/*      table : 投資先，投資金額毎の利益 */
014	/*      rieki : 現段階の最大利益（φ）   */
015	/*      next : 最大利益を与える投資先    */
016	/*      coded by Y.Suganuma              */
017	/*****************************************/
018	int dynamic(int p, int n_toshi, int step, int n_case, int **table, int **rieki, int **next)
019	{
020		int m = 0;
021						// 最大利益の計算
022							// １段目
023		if (p == 0) {
024			for (int i1 = 0; i1 < n_case; i1++)
025				rieki[p][i1] = table[p][i1];
026		}
027							// ２段目以降
028		else {
029			for (int i1 = 0; i1 < n_case; i1++) {
030				m       = step * i1;   // 投資額
031				int l1  = -1;   // rieki[p][i1] は，
032				int l2  = -1;   //    table[p][l1] + rieki[p-1][l2] で最大
033				int max = -1;
034				int m1  = 0;
035				int k1  = 0;
036				while (m1 <= m) {
037					int m2 = 0;   // 前段
038					int k2 = 0;   // 前段
039					while (m1+m2 <= m) {
040						int r = table[p][k1] + rieki[p-1][k2];
041						if (r > max) {
042							l1  = k1;
043							l2  = k2;
044							max = r;
045						}
046						m2 += step;
047						k2++;
048					}
049					m1 += step;
050					k1++;
051				}
052				next[p][i1] = l2;
053				if (l2 >= 0)
054					rieki[p][i1] = table[p][l1] + rieki[p-1][l2];
055			}
056		}
057						// 次の投資先
058							// 最終段より前
059		if (p < n_toshi-1)
060			m = dynamic(p+1, n_toshi, step, n_case, table, rieki, next);
061							// 最終段
062		else {
063			int max = -1;
064			int k1  = n_toshi - 1;
065			for (int i1 = 0; i1 < n_case; i1++) {
066				if (next[k1][i1] >= 0 && rieki[k1][i1] > max) {
067					max = rieki[k1][i1];
068					m   = i1;
069				}
070			}
071		}
072	
073		return m;
074	}
075	
076	int main()
077	{
078						// データの入力と領域の確保
079		int n_toshi = 3;   // 投資先
080		int step    = 1;   // 投資単位
081		int n_case  = 5;   // 資金の投資ケース数
082		int **table = new int * [n_toshi];   // 投資先，投資額，そのときの利益
083		int **rieki = new int * [n_toshi];   // 現段階の最大利益
084		int **next  = new int * [n_toshi];   // 最大利益を与える投資先
085		for (int i1 = 0; i1 < n_toshi; i1++) {
086			table[i1] = new int [n_case];
087			rieki[i1] = new int [n_case];
088			next[i1]  = new int [n_case];
089		}
090		table[0][0] = 0;
091		table[0][1] = 8;
092		table[0][2] = 18;
093		table[0][3] = 22;
094		table[0][4] = 24;
095		table[1][0] = 0;
096		table[1][1] = 3;
097		table[1][2] = 6;
098		table[1][3] = 9;
099		table[1][4] = 12;
100		table[2][0] = 0;
101		table[2][1] = 6;
102		table[2][2] = 7;
103		table[2][3] = 8;
104		table[2][4] = 10;
105						// 実行
106		int max = dynamic(0, n_toshi, step, n_case, table, rieki, next);
107						// 結果の出力
108		if (max >= 0) {
109			printf("最大利益 %d\n", rieki[n_toshi-1][max]);
110			for (int i1 = n_toshi-1; i1 >= 0; i1--) {
111				int k = max * step;
112				if (i1 > 0) {
113					max  = next[i1][max];
114					k   -= max * step;
115				}
116				printf("   投資先 %d 投資資金 %d\n", i1+1, k);
117			}
118		}
119		else
120			printf("解が存在しません！\n");
121	
122		return 0;
123	}
    023 行目～ 026 行目

    　　1 段目（ 1 番目の投資先）に対する処理です．全ての投資額に対する利益を代入しているだけです．

    028 行目～ 056 行目

    　　2 段目（ 2 番目の投資先）以降に対する処理です．29 行目の for 文によって，投資額 m = step * i1 に対する最大利益を計算します．ただし，step の値が 1 ですので，m の値は i1 に等しくなります．この段における投資額 m1 は，m 以下である必要があり，その条件の下で，036 行目の while 文によって m1 の値を変化させていきます．さらに，m1 と前段の投資額 m2 を加えた額が m 以下であるという条件の下で，039 行目の while 文によって m2 の値を変化させていきます．この結果，m が 0 の場合は，m1 及び m2 が 0，m が 1 の場合は，m1 が 0，m2 が 1，または，m1 が 1，m2 が 0，m が 2 の場合は，・・・，等の組合せの中から利益が最大の組合せが rieki[p][i1] に記憶されます．next[p][i1] には，利益を最大とした前段の rieki[p-1][i] の i の値が記憶されます．そのような i が存在しない場合は，-1 が記憶されます．

    059 行目～ 060 行目

    　　最終段目より前の場合は，次の段の計算に進みます．

    062 行目～ 071 行目

    　　最終段目の計算であり，最大利益を選択しています．

    （出力）　このプログラムによって，以下に示すような結果が得られます． 
    最大利益 28
   投資先 3 投資資金 1
   投資先 2 投資資金 0
   投資先 1 投資資金 3

  3. 最短経路問題

    　　ここでは，下図に示すグラフのノード 0 から ノード 6 に至る最短経路を求めてみます（赤い線が最短経路，枝上の数値が経路の長さ）．最初は横型探索で，次に，動的計画法の一種であるダイクストラ法（ Dijkstra ）で計算してみます．

    1. 横型探索

      　　このプログラムでは，C++ 標準ライブラリ内の queue クラスを利用して，横型探索を実現しています．ノードの数だけの要素を持つ配列変数 rd に，スタートノードからの経路長を入れておく（まだ経路長が計算されていない場合は -1 ）ことによって，ループに入ることを防いでいます．なお，ここでは，最短経路に対する距離だけを求めています． 
      01	/********************************************/
02	/* 横型探索（最短経路）                     */
03	/*      n : ノードの数                      */
04	/*          　ノード0:スタート              */
05	/*          　ノード(n-1):ゴール            */
06	/*      r : ノード間の距離                  */
07	/*      rd : 現時点におけるノードまでの距離 */
08	/*           coded by Y.Suganuma            */
09	/********************************************/
10	#include <stdio.h>
11	#include <queue>
12	
13	using namespace std;
14	
15	void width(int n, int **r, int *rd)
16	{
17		int node = 1;
18		queue<pair<int, int> > q;
19	
20		q.push(pair<int, int>(0, 0));
21		while (!q.empty()) {
22			int k = q.front().first;   // ノード番号
23			int v = q.front().second;   // スタートノードからの距離
24			q.pop();
25						// 先頭のノードから到達可能なノードをキューに追加
26						// （既にノードまでの距離が計算済みであり，その
27						//   距離が今回計算した距離よりも短い場合は除く)
28			for (int i1 = 0; i1 < n; i1++) {
29				if (r[k][i1] >= 0) {
30					int r1 = v + r[k][i1];
31					if (rd[i1] < 0 || r1 < rd[i1]) {
32						q.push(pair<int, int>(i1, r1));
33						rd[i1] = r1;
34						node++;
35					}
36				}
37			}
38		}
39	
40		printf("展開したノード数： %d，　最短距離： %d\n", node, rd[n-1]);
41	}
42	
43	int main()
44	{
45		int *rd = new int [7];   // ノードまでの距離
46		int **r = new int * [7];   // ノード間距離
47		for (int i1 = 0; i1 < 7; i1++) {
48			rd[i1] = -1;
49			r[i1]  = new int [7];
50			for (int i2 = 0; i2 < 7; i2++)
51				r[i1][i2] = -1;
52		}
53		rd[0]   = 0;
54		r[0][1] = 2;
55		r[1][0] = 2;
56		r[0][2] = 5;
57		r[2][0] = 5;
58		r[1][2] = 4;
59		r[2][1] = 4;
60		r[1][3] = 6;
61		r[3][1] = 6;
62		r[1][4] = 10;
63		r[4][1] = 10;
64		r[2][3] = 2;
65		r[3][2] = 2;
66		r[3][5] = 1;
67		r[5][3] = 1;
68		r[4][5] = 3;
69		r[5][4] = 3;
70		r[4][6] = 5;
71		r[6][4] = 5;
72		r[5][6] = 9;
73		r[6][5] = 9;
74	
75		width(7, r, rd);
76	
77		return 0;
78	}
      45 行目～ 73 行目

      　　探索を行うための初期設定を行っています．変数 rd には，スタートノードからの距離（初期値は -1 ），変数 r には，ノード間の距離が設定されています．その後，関数 width によって，最短距離の計算と出力を行います（ 75 行目）．

      20 行目

      　　ノード番号とスタートノードからの距離のペアを queue クラスのオブジェクト q に追加しています．

      21 行目

      　　この while 文によって，q が空になるまで，22 行目～ 37 行目が繰り返されます．

      22 行目～ 24 行目

      　　q の先頭要素に関する情報を取り出した後，先頭要素を削除しています．

      28 行目～ 37 行目

      　　先頭要素から到達可能なノードを，そのノードまでの距離を計算（ 30 行目）した後，q に追加しています．ただし，既にそのノードまでの距離が計算済みであり，かつ，その距離が今回計算した距離より短い場合は除きます（ 31 行目）．

      （出力）　このプログラムを実行すると，以下に示すような結果が得られます． 
      展開したノード数： 11，　最短距離： 16

    2. ダイクストラ法（ Dijkstra 法 ）

      　　ダイクストラ法では，まず，スタートノードから直接到達可能なノードまでの距離を計算します．それらのノードの内，最短距離でいけるノードは，他のノードを経由したいかなる経路によってもその距離より短い距離で到達することは不可能です．そこで，スタートノードからそのノードまでの距離は確定したとみなし，以後，検討対象から外します．次に，その最短距離のノードから直接到達可能なノードまでのスタートノードからの距離を計算します．このとき，あるノードまでの距離が，それまでに計算された距離（この場合は，スタートノードからの直接距離）よりも短ければ，そのノードまでの距離を新しい距離で置き換えます．再び，既に距離が計算されたノードの内，スタートノードからの距離が最小のものを選択し，同じ手続きを繰り返します（距離の確定とそのノードから直接到達可能なノードまでの距離の計算）．このようにして，すべてのノードまでの距離が確定した時点で終了となります．

      　　このプログラムでは，距離が最小になるノードが常に先頭に来る C++ 標準ライブラリ内の set クラスを利用して，ダイクストラ法を実現しています．なお，ここでは，最短経路に対する距離だけを求めています． 
      001	/****************************/
002	/* Dijkstra（最短経路）     */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <set>
007	
008	using namespace std;
009	
010	class Net
011	{
012		public :
013			int node;   // ノード番号
014			int r;   // スタートからの距離
015			Net (int n1, int r1)
016			{
017				node = n1;
018				r    = r1;
019			}
020	};
021	
022	bool operator< (Net n1, Net n2)
023	{
024		if (n1.r == n2.r)
025			return  (n1.node < n2.node) ? true : false;
026		else
027			return  (n1.r < n2.r) ? true : false;
028	}
029	
030	/********************************************/
031	/* Dijkstra（最短経路）                     */
032	/*      n : ノードの数                      */
033	/*          　ノード0:スタート              */
034	/*          　ノード(n-1):ゴール            */
035	/*      r : ノード間の距離                  */
036	/*      rd : 現時点におけるノードまでの距離 */
037	/*      used : 距離が確定したか否か         */
038	/********************************************/
039	void Dijkstra(int n, int **r, int *rd, bool *used)
040	{
041		int node = 1;
042		set<Net> s;
043		set<Net>::iterator it;
044	
045		s.insert(Net(0, 0));
046		while (!s.empty()) {
047			it    = s.begin();
048			int k = it->node;   // ノード番号
049			int v = it->r;   // スタートノードからの距離
050			s.erase(it);
051			if (!used[k]) {
052						// 先頭のノードから到達可能なノードをセットに追加
053						//　　・距離が決定しているノードは除く
054						//　　・既にノードまでの距離が計算済みであり，その距離が
055						//　　　今回計算した距離よりも短い場合は距離を修正して追加
056				used[k] = true;
057				for (int i1 = 0; i1 < n; i1++) {
058					if (!used[i1] && r[k][i1] >= 0) {
059						int r1 = v + r[k][i1];
060						if (rd[i1] < 0 || r1 < rd[i1]) {
061							s.insert(Net(i1, r1));
062							rd[i1] = r1;
063							node++;
064						}
065					}
066				}
067			}
068			else
069				node--;
070		}
071	
072		printf("展開したノード数： %d，　最短距離： %d\n", node, rd[n-1]);
073	}
074	
075	int main()
076	{
077		bool *used = new bool [7];
078		int *rd    = new int [7];   // ノードまでの距離
079		int **r    = new int * [7];   // ノード間距離
080		for (int i1 = 0; i1 < 7; i1++) {
081			used[i1] = false;
082			rd[i1]   = -1;
083			r[i1]    = new int [7];
084			for (int i2 = 0; i2 < 7; i2++)
085				r[i1][i2] = -1;
086		}
087		rd[0]   = 0;
088		r[0][1] = 2;
089		r[1][0] = 2;
090		r[0][2] = 5;
091		r[2][0] = 5;
092		r[1][2] = 4;
093		r[2][1] = 4;
094		r[1][3] = 6;
095		r[3][1] = 6;
096		r[1][4] = 10;
097		r[4][1] = 10;
098		r[2][3] = 2;
099		r[3][2] = 2;
100		r[3][5] = 1;
101		r[5][3] = 1;
102		r[4][5] = 3;
103		r[5][4] = 3;
104		r[4][6] = 5;
105		r[6][4] = 5;
106		r[5][6] = 9;
107		r[6][5] = 9;
108	
109		Dijkstra(7, r, rd, used);
110	
111		return 0;
112	}
      077 行目～ 107 行目

      　　探索を行うための初期設定を行っています．変数 used には，距離が確定したか否かの情報（初期値は false ），変数 rd には，スタートノードからの距離（初期値は -1 ），変数 r には，ノード間の距離が設定されています．その後，関数 Dijkstra によって，最短距離の計算と出力を行います（ 109 行目）．

      010 行目～ 020 行目

      　　ノード番号及びスタートノードからの距離をメンバー変数として持つクラス Net の定義です．

      022 行目～ 028 行目

      　　set クラスにおいて，Net クラスのオブジェクトの比較を行うため，比較演算子のオーバーロードを行っています．

      045 行目

      　　スタートノードに対応する Net クラスのオブジェクトを，set クラスのオブジェクト s に追加しています．

      046 行目

      　　この while 文によって，s が空になるまで，047 行目～ 069 行目が繰り返されます．

      047 行目～ 050 行目

      　　s の先頭要素に関する情報を取り出し，その後，その要素を s から削除しています．

      056 行目

      　　先頭要素に対しての距離計算を確定します．

      057 行目～ 066 行目

      　　距離計算が未確定で，かつ，先頭要素から到達可能なノードを，そのノードまでの距離を計算（ 059 行目）した後，s に追加しています．ただし，既にそのノードまでの距離が計算済みであり，かつ，その距離が今回計算した距離より短い場合は除きます（ 060 行目）．

      （出力）　このプログラムを実行すると，以下に示すような結果が得られます． 
      展開したノード数： 7，　最短距離： 16

      ［演習５］先に示したグラフに対して，動的計画法によって最短経路及びその距離を求めるためのプログラムを書け．

講義内容目次 菅沼ホーム 前ページ 次ページ