6

現在、約 800 ポイントの X 座標と Y 座標を含むベクトルを持つプロジェクトに取り組んでいます。これらのポイントは、ラインの電気ネットワークを表します。私の目標は、電線の XY 座標を含むベクトルによって与えられるパスに沿って配置できる、または配置できないポイント A とポイント B の間の最短距離パスを計算することです。

ダイクストラアルゴリズムについて読んだことがありますが、あまり詳しくないので、その方向に進むべきかどうかわかりません。この問題を解決するためのフィードバックやコメントをいただければ幸いです。

4

3 に答える 3

1

経路探索アルゴリズムは経路に依存し、ポイントは無意味です。あなたが今持っているのは「ウェイポイント」のリストです。ただし、それらのポイントがどのように接続されるかについては説明していません。たとえば、すべての点が他の点に接続されている場合、最短距離は単純に A と B の間のピタゴラス距離になります。開始位置と終了位置はありますか?

したがって、最初のステップは、x、y 座標だけでなく、接続可能なポイントのリストも各ポイントに追加することです。

これを行ったら、経路探索アルゴリズムの使用を開始できます (この場合、A* は Dijkstra のものよりも優れているように見えます)。それは単に、ポイント間の実際の距離を「コスト」する標準的な実装です。(そして A* の場合、ヒューリスティックは終点までのピタゴラス距離になります)。

A* (およびその他のアルゴリズム) に関する優れたチュートリアルについては、Amit のページを確認してください。

編集、コメントへの返信。

最初のステップは、一連の線分を「点」に変換することです。私がこれを通過する方法は次のとおりです。

collection AllPoints {containing Location & LinksToOtherPoints}
for each Segment
    get start/end Point of Segment
    if Point.Location is not in allPoints
        add Point to AllPoints
    add the other Point of Segment to LinksToOtherPoints

次に、すべてのポイントとそれらの間の接続を含むリストを作成します。allPoints コレクションを常に検索する必要があるため、バイナリ ツリー構造 (セット?) に格納することをお勧めします。

于 2013-01-05T16:01:28.570 に答える
0

最短経路を計算するには Dijakstra で十分です。

A*を使用すると、より速い結果が得られる場合があります。これは、検索を正しい方向に集中させるために距離の最良の推測を使用するため、より迅速に到達できます。

同じデータセットを繰り返しクエリする場合は、メモ化で問題ありません。

力ずくのアルゴリズムを推奨する人は愚か者です。効率的なソリューションをプログラムする方法を学ぶために少し時間を割く価値があります。しかし、 Floyd-Warshall アルゴリズムを使用して、すべてのポイント間の最短経路を計算できます。残念ながら、これは最短経路がどれだけの長さであるかを教えてくれません。

于 2013-01-06T10:46:47.663 に答える
-2

考えられるすべてのパスの距離を計算し、最短のパスを選択するだけです。800 パスは、最新の PC にとっては何の意味もありません。あなたもそれに気付かないでしょう。

于 2013-01-05T16:08:31.427 に答える