問題タブ [a-star]

2D の 2 点間の (最短)/(最適) 距離を取得する必要があります。互いにつながっている可能性のある線である形状は避けなければなりません。移動できるノードを表す方法について何か提案はありますか? グリッドを作成することを考えましたが、これはあまり正確でもエレガントでもありません。線のいずれかの点が正方形の内側にある場合、ノードは歩行不能であると見なします (ノードが正方形の中心です)。

例として、ポイント A から B に移動します。

グリッドはこれを解決するための推奨される方法ですか? 事前にたくさんありがとう！

私はアルゴリズムとソフトウェア開発の研究を開始し、小規模な自己評価プロジェクトとして、C++ で A* 検索アルゴリズムを作成することにしました。視覚的な部分に Qt と OpenGL を使用します (ただし、それは重要ではありません)。

主にこのソースを使用: A* 初心者向けパスファインディング

小さなアプリを作成しましたが、修正できないバグが見つかりました。なんらかの理由で、壁に近いノードの親が壁に設定されているようです(?)そして、情報を保存する方法のために、壁の親が開始点(?)に設定されています。

私はstateMatrix [] []を使用しました

また、openNodes と closedNode を表すためにマトリックスを使用しました。closedNodes マトリックスは bool マトリックスで、openNode マトリックスにもいくつかの情報が格納されます。

openNodes の手順は次のとおりです。

これをコーディングするためのより良い方法があることは知っていますが、まだこのレッスンに到達していません ;)

astar ファイルのコードは次のとおりです。

私が間違っていることを誰かが知っていますか？

ありがとう。編集：ここにいくつかの写真があります：

Java で A* アルゴリズムを作成しようとしましたが、この奇妙なバグがあります。A* が常に最適なパスを見つけるとは限らないことはわかっていますが、ここでは理にかなっていないようで、より悪いパスを選択しているようです。これを引き起こしているコードのバグを見つけることができません。私が作成した他のマップで最適解を見つけたようです。これはバグの写真とノードのプリントアウトです

http://i.imgur.com/IudT7.png

これが私が使用したコード（の一部）です。

A-starの実装に問題があります。ポイントAからBへのパスは検出されますが、地形がより「複雑」な場合は検出されないため、Find（）関数は終了していないようです。たとえば、ここでは20 x 20の配列で機能しますが、一番右の障害物/壁の下部に正方形（'＃'）を追加すると、失敗します。

私がしている間違いを誰かが指摘してくれることを願っています。これが私のコードです：

A*アルゴリズムの実装についてサポートが必要です。アルゴリズムを実行すると、目標は見つかりますが、パスは間違いなく最短ではありません:-P

これが私のコードです。バグを見つけるのを手伝ってください！私の問題は再構築パスかもしれないと思いますが、よくわかりません。

}

すべての素晴らしい答えをありがとう！私のA*アルゴリズムは、皆さんのおかげで完全に機能するようになりました。:-)

これは私の最初の投稿であり、このフォーラムは本当に素晴らしいです！

私の AS3 A* パスファインディングの実装は、次のように、最も効率的なルートを返さないことがあります。

(ここで、. は歩いたノード、X は壁です。S = 開始、E = 終了、i = 想像上のマーカー)

問題: i の合計スコアは (終了までの距離) 30 + (開始からの距離) 10 = 40 になるはずですが、上のタイルの合計スコアは (終了までの距離) 40 + (開始からの距離) 14 になります。 = 54. なぜ 40 ではなく 54 が選ばれるのか、私にはわかりません - これを使用して、オープン リストで合計スコアが最も低いノードを見つけます。

（私は何の問題も見られません。）

たぶん、最後までの距離を計算するのにエラーがあるのではないかと思いました。だから私はそれのために私のコードをチェックしました:

（これも問題はありません。）

私はこれに本当に困惑しています。

Main.as: http://pastebin.com/ZKQJwY4S PathSearcher:as: http://pastebin.com/KnmWGbQw

(問題のコードを直接投稿した方が良いことは理解していますが、問題のコードがどこにあるのかわかりません:(ごめんなさい)

助けてくれてありがとう！

Javaを使用して実行しようとしている割り当てがありますが、次のグラフの設定方法/ノードは何かについて混乱しています。基本的に、これはペンプロッター問題、またはより一般的には巡回セールスマン問題として知られています。私の次の入力は次のとおりです。

そして私の出力は次のようになります：

一枚の紙の左下隅があなたの出発点（0,0）であり、それが座標で上昇し、それぞれの座標がノードであると仮定すると、いつ移動して線を引くかをどのように決定しますか。A *で無向グラフを使用する必要があることはわかっていますが、ノード（頂点）がノード（頂点）であるか、いつ移動するか、いつ線を引くかをどのように決定するかについて、まだかなり混乱しています。誰かがアドバイスをくれますか？

編集：は、検索全体で探索されたノードの量/数を指すことに注意してください。

A *検索アルゴリズムを実装していますが、優先キューで問題が発生し続けています。この記事に従って、優先キューのカスタムコンパレータを実装しました

これは関連するコードです：

コールスタック：

このアルゴリズムには最小ヒープが必要だったため、Greaterを使用しました。実装は正常に機能しているようで、リリースモードで実行すると問題は解決しますが、優先キューがpop（）されると、デバッグモードで優先キューが「無効なヒープ」アサーションエラーをスローすることがあります。

stlのbinary_functionに精通していませんが、問題はコンパレータにあるようです。コンパレータを削除するか、符号をlessに変更すると、エラーが削除されますが、最大ヒープが得られます。足りないものはありますか？

Python で A* アルゴリズムを実装しようとしていますが、このマップのパスを見つけようとすると問題が発生します。

マンハッタン方式を採用しています。私の実装はパスを見つけますが、最短のものではありません。エラーは、2 番目の移動 (右に移動した後) で始まります。この時点で上に移動でき、ヒューリスティック コストは 4 (右に 3 つ、下に 1 つ) または下に (右に 3 つ、上に 1 つ) なります。最短経路を取得するためにダウンを選択する方法はありますか?

コード：