heuristic cost問題の決定方法cities connected with roads。グラフには負ではない加重の一方向エッジがあり、頂点をそれ自体に接続するエッジはありません。このグラフでは、任意の 2 つの頂点間にエッジが 1 つしかありません。single source私の目的は、との間の最短距離を取得することですsingle destination。
2250 次
3 に答える
1
エッジがユークリッド平面にあり、頂点が道路に対応し、頂点コストが道路の長さである場合、ユークリッド距離またはL2ノルムがヒューリスティックコストに適しています。
これが理由です。しかし、最初に、いくつかの簡単な用語：
パスコストf(x)、開始ノードからノードまでの計算された最短距離とします。x
ヒューリスティックコストh(x)、ノードからゴールまでの距離の推定値とします。x
A*は有向最良優先探索アルゴリズムであるためです。各ステップで、最小化するノードに移動します h(x) + f(x)（計算h(x)には、ゴールノードを念頭に置く必要があります）。
このアプローチで開始ノードと終了ノード間の正しい最短パッチ距離を確実に見つけるには、許容できるヒューリスティックh(x)である必要があります。これは本質的に、ゴールノードまでの距離を過大評価してはならないことを意味します。
したがって、ノードがユークリッド平面上に編成されており、コストがノード間のL2ノルム距離に対応している場合、現在のノードとゴールノード間のユークリッド距離またはL2ノルムは、許容可能なヒューリスティックであることが保証されます（ 2つのノード間の最短パスであるため、グラフ内の一連の頂点に沿った実際のパスは長くする必要があります）。x
ボーナスとして、ダイクストラのアルゴリズムは単にA*の特殊なケースであることに注意してくださいh(x) = 0。どのノードでも、目標へのパスはであると想定します。これは0、可能な限り最小のステップを実行することを意味します。任意の2つのノード間の距離は（非負のエッジコストを想定している場合）より小さくすることはできないため、これは確かに許容できるヒューリスティックです。0
于 2012-04-07T20:22:28.687 に答える
0
重み付きグラフが与えられている場合は、セグメントの長さであるかのようにエッジの重みを使用します。重み付きグラフの最短パスは、結合されたエッジの重みが最も低いパスです。
于 2012-04-07T15:42:33.210 に答える
0
移動距離を最適化しようとしている場合、ユークリッド距離は優れたベースライン ヒューリスティックです。
于 2012-04-07T15:28:19.553 に答える