分岐限定探索について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アルゴ

分岐限定探索について

#1

投稿記事 by アルゴ » 16年前

分岐限定探索アルゴリズムを用いて最適経路を求める問題について質問です。

下の結果が答えになるようですが、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]
では間違いなのでしょうか?回答お願いします。

( )←はコスト値 S:出発地点 G:ゴール地点 ***アンダーバーは無線としてください***

S---(1)A---(3)B------(4)D
|_________|___________________________|
(5)_____(2)_________________________(2)
E---(1)F---(1)H______________I
|\(1)___\(4)____\(4)
(5)J_(1)K--(1)L--(1)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

box

Re:分岐限定探索について

#2

投稿記事 by box » 16年前

<pre>と</pre>タグとで前後を挟んで、もう一度投稿してくださいますか?(<と>は半角)
図のレイアウトが崩れてしまっていて、何を説明したいのかわからなくなっているためです。

閉鎖

“C言語何でも質問掲示板” へ戻る