3

私は、いくつかの制約（オリエンテーリングの問題）を条件として、OpenStreetMapデータ上の循環ルートを提案するアプリケーションを作成中です。私が試しているアルゴリズムの最も内側のループでは、2つの与えられたポイント間の最低コストのパスを見つけるための要件です。グラフのレイアウト（基本的にはユークリッド）を考えると、Aスターアルゴリズムはグラフを考えると最も速い時間で結果を生成する可能性が高いようです。ただし、エッジの距離（マップ上の実際の距離を表す）だけでなく、特定のエッジ（道路/パスなど）がどれほど望ましいかを示す一連の重み（現在、0.0、最も望ましくないものから1.0、最も望ましいものにスケーリング）もあります。 ）は、アプリケーション用に考案したいくつかのメトリックに従って計算されます。

これらの重みに基づいて距離を変更したいと思います。標準のAスターヒューリスティックは、パスの実際のコストが少なくとも推定値と同じであることに依存していることを認識しています（ポイント間のユークリッド距離に基づく）。したがって、私の最初の考えは、最小エッジ距離が実際の距離（重み1.0の場合）であり、重みが減少するにつれて距離が増加する（たとえば、重み0.0の場合の距離が4倍になる）スキームを考え出すことでした。これは賢明なアプローチのように思われますか、それともこれらの状況下で高速ルーティングを行うためのより優れた標準的な手法がありますか？

4

3 に答える 3

2

私はあなたのアプローチが最も正気だと信じています。どうやら私は同様の問題に取り組んでおり、まったく同じ戦略を使用することにしました。

A *アルゴリズムは、必ずしも「真の距離」に依存しているわけではありません。それは距離についてでさえありません、あなたは実際に他の物理量を最小にするかもしれません-ヒューリスティック関数は同じ物理単位を持つべきです。

たとえば、私の問題はパス時間を最小化することですが、任意のポイントでの速度は場所、時間、および選択した方向に依存します。私のヒューリスティック関数は、大まかな距離（私の問題は地球の表面にあり、大円距離の計算はやや高価です）を最大許容速度で割ったものです。つまり、時間の単位があり、指定された場所から終点に到達するための最も楽観的な時間として解釈されます。

于 2012-07-02T20:07:38.210 に答える
1

関連する質問は、「実際に何を最小化したいですか？」です。パスファインディングアルゴリズムが最小のものを選択できるように、最終的に単一の「変更された距離」を取得する必要があります。

A *アルゴリズムの継続的な有用性は、「望ましさ」をルーティング距離にどのように統合するかによって異なります。A *には、楽観的である「許容可能なヒューリスティック」が必要です。「変更された距離」のヒューリスティックな推定値は、実際の「変更された距離」を超えてはなりません（そうでない場合、検出されたパスは実際には最適ではない可能性があります...）。これを確実にする1つの方法は、変更された距離が、任意のステップで元のユークリッド距離よりも常に大きいことを確認することです。次に、ユークリッド距離を最小化するために許容されるA *ヒューリスティックは、修正された距離を最小化するためにも許容されます。

たとえば、modified_distance = euclidean_distance / desirability_rating（for 0<desirability_rating<=1）を計算する場合、加重されていmodified_distanceないeuclidean_distanceパスに使用していたA *ヒューリスティックは引き続き楽観的であるため、A*に使用できます。（ただし、すべてのパスが望ましくない地域では、非常に楽観的すぎるA *ヒューリスティックでは、パフォーマンスが期待どおりに向上しない場合があります...）

于 2012-07-02T22:38:16.360 に答える
0

Fast（er）ルーティングはA*で実行できます。私自身のプロジェクトでは、約のブーストが見られます。ダイクストラと比較して4倍高速です。つまり、双方向ダイクストラよりもさらに高速です。

しかし、クエリ速度を向上させるための技術はもっとたくさんあります。たとえば、ショートカットを導入したり、そのグラフでA*を実行したりします。これがより詳細な答えです。

于 2012-09-02T21:24:12.933 に答える