2011-10-19 6 views
3

人はstenfordのai-class.comに登録しており、講義の最初の1週間でアルゴリズムについて学びました。ヒューリスティックよりもA *

また、私は私のクラスメイトは彼がで公開している4×4スライディングブロックパズルにそれを実装の一つを示しています。私は非常に感謝し、*と私たちの娯楽のために結果を公開を実装するためのジョージに感謝しながらhttp://george.mitsuoka.org/StanfordAI/slidingBlocks/ を。

私は(そして彼も)プロセスをより最適化する方法があるのか​​、または「より良いブロック数」のよりも優れた発見的機能のようなより優れたヒューリスティックなA *があるかどうか疑問に思っていました。物事をスピードアップする「目標との距離の合計」? また、より良い仲間があり、そのような問題のためにA *があるならば、私はそれらについても知りたいと思います。

私のプロフィールを格下げする前に、ヘルプや矛盾があった場合は、私のアプローチをアップグレードする機会を与えてください。また、reqで質問を削除しても、まだstackoverflowの方法を学んでいます。

+0

あなたは*の選択肢を探してみましたがありますか? – GolezTrol

+0

私は最初に質問をする前に言ったように試しましたが、満足のいく結果は得られませんでした。そのうちの1つはブロブマップアルゴです。だからここでそれを尋ねる方が良い方法だと思った。 (BDWがGollezTrolに応答してくれてありがとう) –

答えて

4

あなたのheuristic functionによって異なります。たとえば、完全なヒューリスティック[h*]、次にgreedyアルゴリズム(*)を使用すると、A *の方が良い結果が得られますが、ヒューリスティックは完璧ですので最適です。ソリューションに必要なノードだけを開発します。残念ながら、完璧なヒューリスティックを持つことはめったにありません。
(*)貪欲アルゴリズム:常に最低h値を持つノードを開発。

ただし、ヒューリスティックが非常に悪い場合:h=0の場合、A *は実際にはBFSです!この場合のA *はO(B^d)ノードを展開します。ここで、Bは分岐因子であり、dは解くために必要なステップ数です。
この場合、単一のターゲット関数があるため、O(2*B^(d/2))=O(B^(d/2))ノードのみを開発する必要があるため、A *が開発するものよりもはるかに小さいので、bi-directional search(*)が効率的になります。
双方向探索:(*)ターゲットから、スタートノードからBFSを実行し、各反復は、各側から1つのステップで両方の前線における共通の頂点がある場合、アルゴリズムは終了します。

平均的な場合、ヒューリスティックが完全ではないが、完全にはそれほど優れていない場合、A *はおそらく両方のソリューションより優れたパフォーマンスを発揮します。

平均ケースの最適化:開始側からA *:双方向検索を実行し、ヒューリスティックでA *を実行し、ターゲット側から通常BFSを実行することもできます。それはより速く解決策を得るでしょうか?あなたはおそらく2つの可能性をベンチマークし、どちらが良いかを見いだすべきです。しかし、このアルゴリズムで見つかった解もBFSやA *のように最適です。

+0

明確にするため、Amitに感謝します。私は質問を修正し、4x4パズルのためのアプローチが適切であるか、改善のための相当なスペースがある場合、あなたのPTから聞きたいと思います。 –

0

A *のパフォーマンスは、ビデオで学んだように、期待コストヒューリスティックの品質に基づいています。その州の実際のコストとできるだけ近い予測コストヒューリスティックを得ることは、拡大する必要がある州の総数を減らします。たとえば、大規模な状態空間検索でハードウェアの制約に直面した場合など、特定の状況ではさらに優れたバリエーションが多数あります。

関連する問題