分岐限定探索アルゴリズムを用いて最適経路を求める問題について質問です。
下の結果が答えになるようですが、4)のOL=[B(4),E(4),L(7)],CL=[F,A,S]はOL=[B(4),E(4),H(4),L(7)],CL=[F,A,S]
6)のOL=[H(4),K(5),L(7),D(8)],CL=[E,B,F,A,S]はOL=[H(4),K(5),L(7),D(8)J(9)],CL=[E,B,F,A,S]
7)のOL=[K(5),L(7),D(8),G(8)],CL=[H,E,B,F,A,S]はOL=[K(5),L(7),D(8),G(8),J(9)],CL=[H,E,B,F,A,S]
では間違いなのでしょうか?回答お願いします。
----------------------------------------------------
OL=OPEN LIST,CL=CLOSE LIST の略です
()内の数値はコストの数値です
SからスタートしてGで終了です
親子ポインタリストは訪問した要素を追加するためのものです
-----------------------------------------------------
1)OL=,CL=[/url]
2)OL=[A(1),E(5)],CL=
3)OL=[F(3),B(4),E(5)],CL=[A,S]
4)OL=[B(4),E(4),L(7)],CL=[F,A,S]
5)OL=[E(4),H(4),L(7),D(8)],CL=[B,F,A,S]
6)OL=[H(4),K(5),L(7),D(8)],CL=[E,B,F,A,S]
7)OL=[K(5),L(7),D(8),G(8)],CL=[H,E,B,F,A,S]
8)OL=[L(6),D(8),G(8)],CL=[K,H,E,B,F,A,S]
9)OL=[G(7),F(8),J(9)],CL=[L,K,H,E,B,F,A,S]
10)Gは目標接点となる(成功)
親子ポインタリスト={(S,A),(A,F),(A,B),(F,E),(F,H),(B,D),(E,J),(E,K),(H,G),(K,L),(L,G)}
解は親子ポインタリストから{(L,G),(K,L),(E,K),(F,E),(A,F),(S,A)}
これを逆にたどってS→A→F→E→K→L→G
コストは7
再・分岐限定探索について
Re:再・分岐限定探索について
分岐限定探索そのものについてはググればたぶんわかると思うのですが、
OL, CL, 親子ポインタリストというような用語の意味やくだんの表記法について
ここを見ている人全員が理解できるわけではないと思います。
まずはそのあたりの説明から入っていただけますか?
OL, CL, 親子ポインタリストというような用語の意味やくだんの表記法について
ここを見ている人全員が理解できるわけではないと思います。
まずはそのあたりの説明から入っていただけますか?