問題タブ [a-star]

私は頭がおかしくなっているか、A* アルゴリズムを誤って実装しているようです。

以下は私のコードです。入力した値に関係なく、常に 360 が返されるようです。重要な情報が欠落していませんか? また、誰かが「はい」と尋ねる前に、これは私が受けた機械学習の課題に関連しています。

public class A_Star {

}

と

public class SearchNode {

public SearchNode(int cost, int xCoordinate,int yCoordinate){
this.cost=cost;
this.xCoordinate = xCoordinate;
this.yCoordinate = yCoordinate;
}
public int getCost() { コストを返します。}

}

私は最初の少し複雑なアルゴリズム、AStarPathfindingアルゴリズムの実装をコーディングしました。グラフの実装に関するPython.orgのアドバイスに従って、各ノードがリンクされているすべてのノードが辞書に含まれるようにしました。さて、これはすべてゲームのためのものなので、各ノードは実際にはノードのグリッド内の単なるタイルです。したがって、ヒューリスティックとそれらへの時折の参照をどのように作成しているか。

timeitのおかげで、この関数を1秒間に100回強実行できることがわかりました。当然のことながら、これは私を少し不安にさせます。これは、グラフィックスやゲームロジックの計算など、他の「ゲーム関連」が行われていないことです。ですから、誰かが私のアルゴリズムを高速化できるかどうかを確認したいと思います。私はCythonに完全に慣れていないか、それと同類であり、Cの行をコーディングできません。

これ以上とりとめのない、これが私のAStar関数です。

ウィキペディアの擬似コードからA*を実装しようとしていますが、奇妙な結果が得られています。

実装は、最初は適切なパスのように見えるものを見つけますが、さらに詳しく見ると、常に同じパスが生成されます。

誰かが何か間違ったことを見つけることができますか？コードはPython3.1で記述されており、pygameを使用しています。

疑似コードステートメントをステートメントごとに実装したと思うので、実際には手がかりがありません。

スクリーンショットもあります：http： //andhen.mine.nu/uploads/astar.dib

ありがとう！

A* 検索アルゴリズムを実装しようとしています。今のところ、私は壁が散らばっている環境を通る良い道を見つけようとしています. 壁はランダムに生成され、場合によってはパスが「スタック」します。捜索がその前とそのすべての側面 (この混乱にそれを導いたものを除く) に壁に遭遇した場合、停止します。これを防ぐためにできることはありますか？私は、H 値に「カラスが飛ぶように」ポイント システムを使用しています。これは、壁を無視し、目的地までの距離を推定するだけです。これにより、このトラップに陥ることがあります。

ありがとう。

私は、巡回セールスマンの問題を解決する A* アルゴリズム (提供されるヒューリスティック) の実装を作成する任務を負っています。私はアルゴリズムを理解しています。それは十分に単純ですが、それを実装するコードを見ることができません。つまり、わかりました。距離 + ヒューリスティック (ノード) でソートされたノードの優先度キューは、パスに最も近いノードを追加します。問題は、前の最も近いノードから最も近いノードに到達できない場合はどうなるかということです。関数の引数として「グラフ」を実際にどのように取るのですか? アルゴリズムが実際にどのように機能するのか、コードとしてはわかりません。

質問を投稿する前にウィキペディアのページを読みました。繰り返します。それは実際には質問に答えません-グラフを検索することは、TSPを解決することとはまったく異なります。たとえば、同じ長さの 2 つのパスは等しくないため、任意の時点で最短のノードが常にバックトラックになるグラフを作成できますが、A から B に行こうとしているだけの場合は 2 つのパスになります。同じ長さは等しいです。

常に最初に最も近いノードに移動することで、一部のノードに決して到達しないグラフを導き出すことができます。

A* が TSP にどのように適用されるかはよくわかりません。つまり、A から B へのルートを見つけるということです。しかし、TSP？接続がわかりません。

ダイクストラの概念とは異なる、どのようなルーティング アルゴリズムが存在しますか?

ダイクストラ (および A*、D*、ベルマン フォージなど) は、次の概念を使用します。既知のノードから最適なノードを取得し、これを展開して、結果を既知のノードに保存します。

基本的に異なる概念はありますか?

グラフ検索クラスでグラフ/ノードをどのように構成しますか? 私は基本的に NavMesh を作成しており、1 つのポリゴンから別のポリゴンへのノードを生成する必要があります。両方のポリゴンを結合するエッジがノードになります。

次に、これらのノードで A* を実行して、最短経路を計算します。クラスとそのプロパティを構造化する方法を知りたいだけですか?

ノードとエッジを備えた完全な無向グラフを作成する必要がないことは確かです。

私はここでこのアルゴリズムを見つけました。

問題があります。ヒューリスティック関数を設定して渡す方法が理解できないようです。

ご覧のとおり、距離関数と推定関数の2つの関数を受け入れます。

マンハッタンヒューリスティック距離関数を使用して、2つのパラメーターを取得する必要があります。彼のソースを変更して、マンハッタンの見積もりを渡すことができるように、TNodeの2つのパラメーターを受け入れるように変更する必要がありますか？これは、4番目のパラメータが次のようになることを意味します。

推定関数を次のように変更します。

私のマンハッタン関数は次のとおりです。

私は現在、A *パスファインディングアルゴリズムを使用して、無限グリッド上のパスを計算しています（GridworldのUnboundedGridを使用して、AP CSのケーススタディを使用しています）。エンドノードが完全に壁に囲まれているために有効なパスが存在しない場合を除いて、すべてがうまく機能します。予想どおり、アルゴリズムは無限に検索を続け、エンドノードを見つけることはありません。

これに対する可能な解決策は、パスファインディング領域全体の周りに非表示の（ユーザーには表示されないがアルゴリズムには表示される）壁を配置し、開始ノード、終了ノード、およびすべての壁ノードがこれらの範囲内にあることを確認することです。壁、2〜3スペースのパディングなど。何かのようなもの：

...最終的にすべてのノードがクローズドリストに追加され、オープンリストが空になり、その時点で有効なパスが存在しないことがわかります。

これは問題の合理的な解決策のように見えますか？これがうまくいかない可能性がある方法はありますか？別の解決策は、同時にエンドから逆方向にパスファインドすることであることを理解していますが、これは、特にエンドノードがそれほど緊密に囲まれていない場合、潜在的にコストがかかる可能性があるようです。

このデータ構造は、このA* チュートリアルから取得しました。

簡単なグラフを作成する方法がわかりません。

C# を使用して、次の無向グラフのようなものを追加するにはどうすればよいですか。

基本的に、ノードを接続する方法を知りたいです。私は自分のデータ構造を持っているので、すでに近隣と距離を決定できます。それをこの投稿されたデータ構造に変換して、AStar アルゴリズムで実行できるようにしたいと思います。

私はもっ​​と次のようなものを探していました: