2

A* のロジックを変更して、最短パス (つまり、コストが最小のパス) を見つけるのではなく、最も有用なパス (つまり、ゲインが最大のパス) を見つけようとしているとします。

私の場合、ゴールは一意の終了ノードとして固定されていません。Bノードは、開始点からの距離を持つ任意のノードとして定義されます。

通常のバージョン (「最短経路の検索」) では、コストを過大評価しないようにする必要があります (つまり、実際のコスト以下のヒューリスティックを見つける)。

代わりに私の修正版 (「最も有用なパスを見つける」) では、エッジはコストではなくユーティリティでタグ付けされており、最大の B エッジを通過するという制約を考慮して、最終的なゲインを最大化したいと考えています。A* を機能させるには、効用を過大評価する (つまり、実際の効用以上のヒューリスティックを見つける) 必要がありますか?

編集：より形式化された、みましょう

f(n) = g(n) + h(n)

ノードのユーティリティであり、以下によって構成されます。

  • g(n): 開始ノードから移動するときに得られるものn
  • h(n): ヒューリスティック、つまり、nゴール (ゴールとは、開始点からの距離が であるノード)Bに到達するときに得られるものの推定値

最適なパスを特定するには、h(n)過大評価して最大化する必要がありますか?f(n)

これは予算であり、完全に使用できることに注意してください。つまり、歩数Bよりも短い経路を見つける必要はありません。B

4

1 に答える 1

1

あなたの問題は、強力な NP-Hardである最長経路問題です。これは、(ほぼ確実に)高速で正確なアルゴリズムが存在しないだけでなく、 (ほぼ確実に)適切な近似アルゴリズムも存在しないことを意味します。

残念ながら、力ずくで行うか、アニーリングや遺伝的プログラミングなどのさまざまなグローバル最適化手法に頼る必要があります。

@Charlesが示唆するように、エッジの重みの符号を否定しても、A*は負のエッジの重みを処理できないため、機能しません。また、負のエッジの重みを処理できる他のアルゴリズムでも、負のサイクルを処理できません。

于 2013-06-06T14:48:26.993 に答える