ここから本文です

A*アルゴリズムの疑問

mou********さん

2012/6/303:34:04

A*アルゴリズムの疑問

今A*アルゴリズムの勉強をしていて少しわからないところがあります。
Wikipedia(http://ja.wikipedia.org/wiki/A*)に、アルゴリズムの流れのところで
「mがcloseリストにあって、f'(m)<f*(m)であるなら、f*(m) = f'(m)とし、closeリストからopenリストに移動する。」
と書いてあります。closeリストに入っているf*の値が更新されることなんてありえるのでしょうか?
自分の中では「closeリスト=f*の値が最小だと確定したリスト」というイメージがあります。
もし間違っているなら、簡単なグラフでcloseリストからopenリストにmが移動される具体例を挙げてもらえるとありがたいです。
例えば、下図でh*(n)の値が<>内の数字でコストが辺の間にある数字として、リストの中身の移り変わりを考えると、
1、ノード1openリストに追加
2、openリストにノード1しかない。ノード1closeリストに移動
3、ノード1の隣接ノード2、3はopenにもcloseにもないのでopenリストに追加また、f*(2)=f'(2),f*(3)=f'(3)
4、f*(2)<f*(3)よりノード2closeリストに移動
5、ノード2の隣接ノード1はcloseリストにあり、f*(1)<f'(1) なので何もしない。3はopenリストにあり、f*(3)>f'(3) なのでf*(3)=f'(3)
6、openリストにノード3しかない。ノード3closeリストに移動
7、ノード3の隣接ノード1、2、4のうち、1、2はcloseリストにありf*(1)<f'(1),f*(2)<f'(2) なので何もしない。4はf*(4)=f'(4)、openリストに追加。
8、openリストに4しかなく、4がゴールなので、終わり。
となると思います。
間違えていたらすみません。この探索ではcloseリストからopenリストに移動することはないはずです。そうなるのはどんな時でしょうか。

ノド,アルゴリズム,closeリスト,隣接ノード,openリスト,ヒューリスティック関数,H2

閲覧数:
790
回答数:
2
お礼:
100枚

違反報告

ベストアンサーに選ばれた回答

pz_********さん

2012/6/311:57:57

A*のポイントは、ヒューリスティック関数h*(n)の存在だと思うのですね。
しかし、h*(n)の与え方は、このアルゴリズムの範囲外です。
条件は、0<=h*(n)<=h(n) で、
h1*(n)<h2*(n)のとき、h2*(n)のほうが「計算量が少ない」とあるので、
h1*(n)<h2*(n)<h3*(n) ・・と時系列で段々と大きくして計算量を減らそうと
いう方向性ですね。

質問の例で言ったら、h*(n)を固定していますが、
例えば、ノード3がcloseに行った時点で、ノード1のh*(n)が7に跳ね上がる・・・
そういうパターンを考察してみたらどうでしょうか?
※質問の例はノード1がスタートなのでアレですが、h*(n)が途中で大きくなるケースって事です。

質問した人からのコメント

2012/6/3 14:46:06

降参 h*(n)が単調ならこういったことは起こらないのですね。ありがとうございました。
もう一人の回答者様の回答もわかりやすかったです。また何かあればよろしくお願いします。

ベストアンサー以外の回答

1〜1件/1件中

lis********さん

編集あり2012/6/313:04:42

日本語版WikipediaのA*にはヒューリスティック関数が単調(monotone)かどうか関して記述がないのですが,
h*(n)をどういう関数と定めるかに依ります.
h*(n) が単調であれば close リストから open リストに移動することがないのですが,
そうでなければ close リストから open リストに移動することもありえるのでcloseリストを毎回チェックする必要があります.
ヒューリスティック関数の単調性に関しては
http://www.ueda.info.waseda.ac.jp/oess/CI2007/Html/class_rsc/materi...
http://en.wikipedia.org/wiki/A*_search_algorithm
あたりを読むといいと思います.

質問者様の例の場合は
h*(1) = 6
h*(2) = 4
h*(3) = 0
h*(4) = 0
とすれば2より先に3のノードが訪問されて close リストに入ってしまうので
2を訪問した時に3のノードをcloseリストからopenリストに移す必要があるのが分かると思います.

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる