問題タブ [a-star]

AIMA ( Artificial Intelligence: A Modern Approach ) のアルゴリズムの説明はまったく正しくありません。「必要」とはどういう意味ですか? メモリ制限とは何ですか? キューのサイズまたは処理されたノード? 現在のノードに子がまったくない場合はどうなりますか?

このアルゴリズム自体が正しいかどうか疑問に思っています。私はインターネットを検索しましたが、まだ誰も実装していません。

ありがとう。

15マスのパズル用のA*ソルバーを作成しようとしています。

目標は、タイルが自然な位置に表示されるようにタイルを再配置することです。一度にスライドできるタイルは1つだけです。パズルの各可能な状態は、検索グラフのノードです。

h（x）関数では、すべてのタイルにわたって、目標状態からのタイルの転位の合計を使用しています。上の画像では、5は位置0,0にあり、位置1,0に属しているため、h（x）関数に1を与えます。次のタイルは11で、0,1にあり、2,2に属しているため、h（x）に3を寄与します。等々。編集：私は今、これが彼らが「マンハッタン距離」または「タクシー距離」と呼んでいるものであることを理解しています。

私はg（x）のステップカウントを使用しています。私の実装では、状態グラフ内の任意のノードについて、gは前のノードのgからちょうど+1です。

連続するノードを見つけるために、パズルの「穴」をどこに移動できるかを調べます。表示されるパズルの状態（別名ノード）には3つの隣接点があります。穴は北、西、または東に移動できます。

私のA*検索は、20秒、180秒でソリューションに収束する場合もあれば、まったく収束しない場合もあります（10分以上待機）。hは妥当だと思います。gを適切にモデル化したかどうか疑問に思います。言い換えると、私のA *関数が最短経路ではない経路を経由してグラフ内のノードに到達している可能性はありますか？

たぶん私は十分長く待っていませんでしたか？たぶん10分では十分ではありませんか？

完全にランダムな配置の場合（パリティの問題がないと仮定）、A *ソリューションが調べる順列の平均数はいくつですか？（数学を見せてください）

コード内の論理エラーを探しますが、それまでの間、ヒントはありますか？

（ps：それはJavascriptで行われます）。

また、いいえ、これはCompSciの宿題ではありません。それは単なる個人的な探求です。私はJavascriptを学ぼうとしています。

編集：実行時間はヒューリスティックに大きく依存していることがわかりました。誰かが言及した記事からヒューリスティックに適用される10倍の係数を見たのですが、なぜ10倍なのか疑問に思いました。なぜ線形なのですか？これはjavascriptで行われるため、コードを変更して、現在検討中のノードでhtmlテーブルを動的に更新できます。これにより、アルゴリズムの進行中にアルゴリズムを確認することができました。通常のタクシー距離ヒューリスティックで、収束に失敗するのを観察しました。

一番上の列には5と12があり、彼らはぶらぶらし続けました。1、2、3、4が一番上の行に忍び寄るのが見えますが、その後はドロップアウトし、他の数字はそこに移動します。私が見たかったのは、1、2、3、4のようなものが上に忍び寄り、そこにとどまっていることでした。

私は自分自身に思いました-これは私がこれを個人的に解決する方法ではありません。これを手動で行うことで、一番上の行、次に2番目の行、次に3番目と4番目の行を同時に解決します。

そこで、h（x）関数を微調整して、上位の行と「左側の」列にさらに大きな重みを付けました。その結果、A*ははるかに速く収束しました。「無期限」ではなく、3分で実行されるようになりました。私が話した「覗き見」で、小さい数字が高い列に忍び寄り、そこにとどまるのを見ることができます。これは正しいことのように見えるだけでなく、はるかに高速に実行されます。

私はたくさんのバリエーションを試しているところです。A*ランタイムがヒューリスティックに非常に敏感であることはかなり明らかなようです。現在、私が見つけた最高のヒューリスティックは dislocation * ((4-i) + (4-j))、iとjが行と列であり、転位がタクシーの距離である場所の合計を使用しています。

私が得た結果の興味深い部分の1つは、特定のヒューリスティックを使用すると、パスを非常にすばやく見つけることができますが、それは明らかに最短パスではありません。これは、ヒューリスティックに重み付けしているためだと思います。あるケースでは、10秒で178ステップのパスを取得しました。私自身の手作業は87回の動きで解決策を生み出します。（10秒以上）。さらなる調査が必要です。

その結果、収束が速くなる必要があり、パスは間違いなく最短ではありません。これについてもっと考えなければなりません。

コード：

グラフ/ツリーでの検索についていくつか質問があります。

空のチェス盤があり、ポーンを点 A から点 B に動かしたいとします。

A. 深さ優先検索または幅優先検索を使用する場合、開いたリストと閉じたリストを使用する必要がありますか? これは、チェックするすべての要素を含むリストと、すでにチェックされている他のすべての要素を含むリストですか? それらのリストがなくてもそれを行うことさえ可能ですか? A* はどうですか?

B. リストを使用する場合、解を見つけた後、A から B への状態のシーケンスをどのように取得できますか? オープンリストとクローズリストにアイテムがある場合、 (x, y) 状態だけでなく、 (x, y, parent_of_this_node) で形成された「拡張状態」があると思いますか?

C. 状態 A には 4 つの移動 (右、左、上、下) があります。先手左としたら、次の状態で元の状態に戻せばいいのでしょうか？これは、つまり、「正しい」動きをしますか？そうでない場合は、検索ツリーを毎回横断して、どの州に行ったことがあるかを確認する必要がありますか?

D. ツリーの状態が行き止まりになっていることを知っているので、それを無視する必要がありますか? これを行うには、訪問した州のリストを常に保持する必要があると思いますよね?

E. 検索ツリーとグラフに違いはありますか? それらは同じものを見る別の方法ですか？

非常に多くの実装が利用可能ですが、最小のグリッドを使用した C++ のクロスプラットフォーム (Linux、Mac、Windows、iPhone) で最も高速に実行される (最小の CPU 集約型、最小のバイナリ) 実装は何ですか?

実装

Google は次を返します。

• http://www.heyes-jones.com/astar.html (このサイトのほとんどのリンクは無効になっています。)
• http://www.grinninglizard.com/MicroPather (Heyes-Jones より遅いと言われています。)
• http://www.ceng.metu.edu.tr/~cuneyt/codes.html (汎用 C++ コード)
• http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/ (A* ではなく、ゲームに興味深いものです。)
• Dijkstra のアルゴリズムのスタック オーバーフロー

他のもの？

ホイール

尋ねられたように、質問は再利用 (ゲームにプラグインする) に関するものであり、再発明ではありません (少なくともパフォーマンスが問題であることが示されるまでは)。ダイクストラ実装 (または一般的な経路探索アルゴリズム) の方が適しているか、最速の実装が十分に高速ではないことが判明する可能性があります。代替アルゴリズムの提案には感謝しますが、問題は「自分で A* をロールする必要があるか」ではありません。

• Joel on Software - Not Invented Here 症候群
• コーディングの恐怖: 車輪を再発明するな
• 「Not Invented Here 症候群」の克服

C# で A* (A スター) アルゴリズムを簡単に実装する方法はどれですか?

私はロボットの動作計画に時間を費やしており、「ポテンシャル フィールド」メソッドが提供する機会を改善する可能性を探りたいと思っていました。私の課題は、「ポテンシャル フィールド」メソッドを使用するときに、ロボットが「ローカル ミニマム」に陥らないようにすることです。ロボットが閉じ込められるのを回避するために「ランダム ウォーク」アプローチを使用する代わりに、ロボットが「ローカルミニマム」。

この種の経験のいくつかはありますか、または「ランダムウォーク」アプローチで使用される方法よりも効果的な方法で局所最小値を回避する文献を参照できます。

インターンシップでは、次の場合に A* アルゴリズムを使用しました。

• 単位形状は高さと幅が 1 の正方形であり、
• 長方形で表されるゾーンから別のゾーンに移動することはできますが、これらの事前定義された領域の外に移動することはできません。
• 対応する正方形のエッジ上のセグメントによって表されるドアを介して、長方形から別の長方形に移動できます。

私がすでに行ったが、上司を満足させなかった2つのことは次のとおりです。

1 : 次のクラスを作成しました: - 2 つの分離された正方形の位置とドアの向き (上、左、下、右) を含む Door クラス、 - ドアのリスト、ドアを表す長方形のリストを含む Map クラス歩行可能エリアと地面の正方形を表す 2D 配列 (列挙による追加情報用) - A* アルゴリズムのクラス (ノード、AStar)

2 : - 列挙によるケース効果とドアに関する情報を含む MapCase クラス ([FLAGS] 属性をオンにして、各ケースに関するいくつかの情報を累積できるようにする) - の 2D 配列のみを含む Map クラスMapCase クラス - A* アルゴリズムのクラス (ノードは AStar のまま)。

バージョン 2 はバージョン 1 よりも優れているため (無駄な計算が減り、マップ クラス アーキテクチャが改善されている)、私の上司はまだ私のマッピング クラス アーキテクチャに満足していません。

A* クラスとノード クラスは優れており、簡単に保守できるので、今のところ詳しく説明する必要はないと思います。

だからここに私の質問があります：誰かが問題の仕様でA *を実装する良い考えを持っていますか（四角形は歩行可能ですが、正方形の単位面積で、ドアを通って移動します）？

彼は、問題のグリッド ビジョン (つまり 2D 配列) は、問題を解決するための正しい方法であってはならないと言いました。

私の問題を明らかにしている間、私は明確であったことを望みます..

ありがとう

凧

パズルを解決し、その解決策へのステップを返すメソッド (*A** アルゴリズムを使用) を作成しようとしています。解決策は簡単です..しかし、そのパスに戻ることはできません。

ノードのリストを使用し、新しいノードをプッシュバックするたびに、新しく来たノードを指す親を設定しました。

クラスノードはこれだけです

しかし、パズルを解くためのパスを構築することはできないことに気付きました...

親板が一枚も見えない…

私はインターネット全体を検索しましたが、何が間違っているのかわかりません:(

私もこれを試しましたが、VS2005 がクラッシュします。

// 目標は Solve メソッドが返した開かれたリストです....

私はより明確で客観的になろうとしています。だから... この部分を見てください

メソッド getLowestCostPath によって返される値は、次のものから取得されました。

その後... Solveメソッドで..コードのこの部分があります

ERROR はこの部分にあると思います、newPathを開いたリストの node を指しているはずなのにtを指しています

本当ですか？もしそうなら..どうすればこれを修正できますか?

独自の A* 実装を使用して、16x16 の迷路を横断します。

すべては順調です。ただし、トラバーサルの後、どの壁が最善の代替パスを提供してくれるかを調べたいと思います。すべてのブロックを削除し、迷路で A* を再実行する以外に、より賢く洗練されたソリューションは何ですか?

node *tentative_parentすべての壁ノード (A* によって無視される) に仮の F 値を与え、ノード構造を変更して、nが迷路内の壁の数である nサイズのリストも持つように考えていました。これは実行可能でしょうか？

ゲームマップがサブグラフに分割されている場合、サブグラフ間のエッジを最小限に抑える方法は?

問題があります。パックマンや倉庫番などのグリッド ベースのゲームで A* 検索を実行しようとしていますが、「囲い」を見つける必要があります。エンクロージャーとはどういう意味ですか? ソフト制約として機能する各サブグラフの頂点数の最大サイズと最小サイズが与えられた場合、カット エッジができるだけ少ないサブグラフ。
あるいは、サブグラフ間のブリッジを探していると言うことができますが、一般的には同じ問題です。

例

グリッドベースのゲームマップの例 http://dl.dropbox.com/u/1029671/map1.jpg

このようなゲームが与えられた場合、私がやりたいことは、エンクロージャーへの入り口を適切に見つけて、これらのエンクロージャー内の頂点に到達するための優れたヒューリスティックを取得できるようにすることです。

代替テキスト http://dl.dropbox.com/u/1029671/map.jpg

だから私が望むのは、特定の地図上でこれらの色付きの領域を見つけることです。

私のモチベーション

単純なマンハッタン距離ヒューリスティックのパフォーマンスに満足するだけでなく、わざわざこれを行う理由は、エンクロージャーヒューリスティックがより最適な結果を与える可能性があり、適切な距離計算を取得するために実際に A* を実行する必要がないためです。また、後で倉庫番タイプのゲームをプレイするときに、これらのエンクロージャー内で対戦相手の競争力のあるブロックを追加することもできます。また、エンクロージャー ヒューリスティックは、ゴール頂点をより適切に見つけるためのミニマックス アプローチにも使用できます。

考えられる解決策

この問題の可能な解決策は、Kernighan Lin アルゴリズムです。

このアルゴリズムの私の問題は、O(n^2 * lg(n)) でのランタイムです。A1 と B1 のノードを各サブグラフの境界に制限して、実行される作業量を減らすことを考えています。

また、アルゴリズムの c[a][b] コストも理解していません。a と b の間にエッジがない場合、コストは 0 または無限大であると想定されます。または、ヒューリスティックに基づいてエッジを作成する必要があります。

a と b の間にエッジがない場合、c[a][b] がどうあるべきか知っていますか? 私の問題はマルチレベル法を使用するのに適していると思いますか? なぜですか、そうでないのですか？私の問題に対して kernighan-lin アルゴリズムで行われる作業を減らす方法について良いアイデアはありますか?