問題タブ [path-finding]

A* パスファインディング アルゴリズムのシンプルで最適化された実装のコードをすべての言語で投稿してもらうことはできますか?

これは主に楽しみのためであり、stackoverflow 自体ができることを試すためのものです...ただし、実際にはこれの ActionScript 3 バージョンを取得することに興味があります。

しかし、この「質問」は、さまざまなプログラミング言語が作成されたとしても、将来にわたって永遠に更新され続けるという考えです!

疑似コードが多くの (ましてやすべての) 異なる言語に "翻訳" されているオンラインの場所を私は知りません。これは価値のあるリソースのように思えます。必ずしもこのサイトが設計された目的ではありませんが、試してみて、stackoverflow を使用できる価値があるかどうかを確認することに害はありません!

Garmin や TomTom のようなナビゲーション システムは、常に私を魅了してきました。小さなマップ/ナビゲーション アプリケーションを実装して、さまざまなパス アルゴリズムを試し、それらに関する知識を広げたいと考えていました。

これは 2 つの部分からなる質問です。

1.) 地図データはどのように保存されますか? - 道路のネットワークがある場合、このデータは通常どのように保存されますか? 後で地図を再現するために、データのどの部分が保持されますか? 各道路は、方向を変える一連のポイントとして保存されていますか? このデータはどのようなファイル形式で保存されますか? これらのファイルを簡単に解析するために公開されているライブラリはありますか? 地図/道路データがどのように保存/表現されるかについての詳細を誰かが持っていますか?それは非常に役に立ちます.

2.) ナビゲーション/パス- このマップ データ (ガーミン風) で基本的なパスを実行する場合、有向グラフに変換されるという私の仮定は正しいですか? 各道路交差点は、頂点間の距離を重み付けするエッジを持つ頂点ですか? これは私がやろうと思っていたことなので、基本的なよく知られているパスアルゴリズムを試してみて、何が得られるかを確認してください。

米国で公開されているこの地図データを見たことがありますが、それがどのように表されているか、また有向グラフを作成できるほど詳細であるかどうかはわかりません。

誰かが情報を持っていれば、私はそれを感謝します。詳しい知識があればあるほど有利です。

ノードのクラスターをリンクするエッジを持つ重み付けされたノードの海があります。このグラフは、典型的なスモール ワールド レイアウトに従います。

ノードが最も有利に重み付けされ、最速のルートが最も重要な要素ではない、可能な限り最良のパスに沿ったパスを見つけるために、プロセッサの電力にコストがかからないパス検索アルゴリズムを見つけたいと思います。このアルゴリズムでは、ロード ベアリングとトラフィックの再ルーティングも考慮されます。

(補足: ここでニューラル ネットワークを使用できますか?)

ありがとう

私はACOを見ています。この種の問題に対して ACO より優れたものはありますか?

A*アルゴリズムは、ロードバランシングなしで、最小コストまたは最速のルートを見つけます。

最速または最短のルートが最も重要なルートではないとしましょう。より重要なのは、重み付けされたノードが特定の値を持つパスをたどることです。いいえ1。

no2. A* を使用すると、そのルートのトラフィックが過負荷になり、突然そのパスが冗長になります。A* と同じくらいクールですが、ACO に固有の負荷分散などの特定の機能はありません。

-- 私が間違ってA*を誤解していない限り

では、ACOに勝るものは何ですか？

本当に ACO と A* の対決のように見えます。A* について非常に多くの肯定的な話がありました。

まず、デビッドに応えて。バックグラウンドで ACO シミュレーションを実行し、最適なパスを見つけることができるので、初期のスタートアップ コストはかかりますが、幸運にもスタートアップは必須ではありません。そのため、シミュレーションを複数回実行する余裕があります。本当の問題の 1 つは、接続されたソース ノードと宛先ノードを見つけることです。A* はこれを非常に簡単に実行できるようです。このネットワークが何百万ものノードのように非常に大きくなるとどうなるでしょうか。A* は簡単にスケーリングできますか?

A*をさらに研究します。しかし、最後に質問をさせてください！

A* は Antnet (ACO) と同様にスケーリングできますか?

私が扱いたい大規模なネットワーク（小さな世界のグラフタイプ）は本質的に動的であり、新しいノードが頻繁に追加および削除されます。おそらく、A*ではなくD*を使用する方が、この動的な環境でパスを検出するためのより良い方法でしょうか？

D *はどれくらいしっかりしていますか？実世界での経験はありますか？暗号化アルゴリズムのように-D*は多くのピアレビューとテストによって強化されていますか？この問題にD*を使用しますか？

以前、煙（一般的な流体）を含むシミュレーションによる経路探索に関する論文を見つけました。誰かがこのようなものを読んだことがありますか? 論文名も著者名も思い出せません。このような紙をご存知でしたら教えてください

A* パス検索アルゴリズムの定義を調べていますが、場所によって定義が多少異なっているようです。

違いは、ノードのサクセサーを通過するときに実行されるアクションと、サクセサーがクローズド リストにあることを見つけることです。

• 1 つのアプローチ (ウィキペディアとこの記事で提案) は、次のように述べています。
• 別のアプローチ (たとえば、こことここで推奨) は次のように述べています。現在計算されているスコアよりも高い場合は、今後の調​​査のためにクローズド リストからアイテムを削除します。

私は混乱しています - どの方法が正しいですか? 直感的には前者の方が分かりやすいのですが、定義の違いが気になります。定義の 1 つが間違っていますか、それとも何らかの形で同形ですか?

私の数学の授業ははるかに遅れており、現在、私が抱えている問題の適切な解決策を見つけるのに苦労しています。ノードがアクションであり、複数の基準に従って「重み付け」されているツリーがあります。言った行動、それがかかる時間、必要な資源、妨害など...

そして、このツリーで、たとえばコストと時間の両方、または外乱とコストと時間などの両方を最小化するパスを見つけたいと思います。私の問題は、立ち上がる以外に、それを行う方法がわからないことです。グローバルコスト関数F（cost、time、resources、...）を使用し、F（...）の結果を唯一の重みとして使用して、通常のツリートラバーサルアルゴリズムを適用します。では、どうすればFを思い付くことができますか？「F（コスト、時間、リソース）=a*コスト+b*時間+c*リソース」のようなものは非常に「専門的ではない」と感じます...

編集：

「合計」という言葉を避けたかったのは、それが実際に進むべき道かどうかわからなかったためですが、本質的には、それが私が行っていることです。そのトップノードをリーフの1つに移動し、コストを最小限に抑える「パス」または「ブランチ」を選択します。問題は、各ノードが必要な時間、財務コスト、リソース使用量などに基づいて重みを持っていることです。

したがって、Stephanが言うように、これらすべてのパラメータをノードごとに1つのグローバルコストに削減する式を考え出す必要があるように思われます。これにより、ツリーを下るときにノード間で合計し、次のパスを選択できます。総コストを最小限に抑えます。

だから私の質問は本当にそうだと思います、それはその機能を選択する方法論がありますか？

あなたの答えとコメントをありがとう、それは今私の頭の中でもう少し明確になり始めています。

マップ プロバイダー (Google や Yahoo! マップなど) はどのように道順を提案しますか?

つまり、彼らはおそらく距離を含む何らかの形で実世界のデータを持っているでしょうが、おそらく運転速度、歩道の存在、電車のスケジュールなども含まれています。しかし、データがより単純な形式であったとします。距離を反映するエッジ ウェイトを使用します。ある任意の点から別の点への方向をすばやく計算できるようにしたいと考えています。これらのポイントは、(1 つの都市内で) 近くにある場合もあれば、遠く離れている場合もあります (クロスカントリー)。

ダイクストラのアルゴリズムのようなグラフ アルゴリズムは、グラフが巨大であるため機能しません。幸いなことに、A* のようなヒューリスティック アルゴリズムはおそらく機能します。しかし、私たちのデータは非常に構造化されており、おそらく何らかの階層化されたアプローチが機能するのではないでしょうか? (たとえば、遠く離れた特定の「キー」ポイント間の事前計算された方向と、いくつかのローカル方向を保存します。この場合、2 つの遠く離れたポイントの方向には、キー ポイントへのローカル方向、別のキー ポイントへのグローバル方向、ローカル方向が含まれます。再度ご案内します。）

実際に実際に使用されているアルゴリズムは何ですか?

PS。この質問は、オンライン マッピングのルート案内で癖を見つけたことがきっかけでした。三角形の不等式とは反対に、 XYZのように中間点を使用するよりも、 XZの方が時間がかかり、遠いとGoogle マップが判断する場合があります。しかし、彼らの歩行経路も別のパラメータで最適化されているのではないでしょうか?

PPS。XZ対XYZという、ある種の階層化されたアプローチを使用していることを (私に) 示唆する三角形の不等式の別の違反を次に示します。前者は少し外れていますが、有名なセバストポール大通りを利用しているようです。

編集：これらの例はどちらも機能していないようですが、元の投稿の時点では両方とも機能していました。

レーシングゲームで使用するアルゴリズムを探しています。マップ/レベル/トラックはランダムに生成されるため、マップを最大限に活用する 2 つの場所 (スタートとゴール) を見つける必要があります。

• アルゴリズムは二次元空間内で動作することです
• 各ポイントから次のポイントまでは 4 方向にしか移動できません。上下左右
• ポイントはブロックされているかブロックされていないかのいずれかのみであり、ブロックされていないポイントのみを通過できます

距離の計算に関しては、適切な言葉がないため、「鳥の道」であってはなりません。A と B の間に壁 (または他の遮断領域) がある場合、A と B の間のパスは長くなります。

どこから始めればよいかわかりません。コメントは大歓迎です。提案されたソリューションは疑似コードで優先されます。

編集：そうですね。gs のコードを調べた後、もう一度試してみました。Pythonではなく、今回はC++で書きました。それでも、Dijkstras アルゴリズム、フラッドフィル、およびHosam Alys ソリューションを読んだ後でも、重要な違いを見つけることができません。私のコードはまだ動作しますが、あなたが実行しているように見えるほど速くはありません。完全なソースはパスティにあります。唯一の興味深い行 (推測) は、78 ～ 118 行の Dijkstra バリアント自体です。

しかし、ここでの主な問題は速度ではありません。誰かがアルゴリズムの違いを指摘するのに十分親切であれば、私は本当に助けていただければ幸いです.

• Hosam Alys アルゴリズムでは、すべてのノードではなく境界からスキャンする唯一の違いは?
• ダイクストラスでは、歩いた距離を追跡して上書きしますが、フラッドフィルではそうではありませんが、それだけですか?

球体、ピラミッド、メッシュで表されるその他のさまざまなオブジェクトなど、サーフェスが 3D で非長方形のさまざまなオブジェクトがあります。メッシュは、オブジェクトの表面全体に同じサイズと分布のポリゴンで構成されているわけではなく、円柱、球、円錐の理想的な形状のようなすべての半対称オブジェクトでもありません。

したがって、任意のメッシュを取り、さまざまな方法で自分自身をラップできるノードを生成する経路探索アルゴリズムを設計または改造するにはどうすればよいでしょうか?