3

A スター アルゴリズムを使用して、最初の 100 個の最短パスを見つけるにはどうすればよいですか?

4

4 に答える 4

8

k 番目の最短パスを見つける問題はNP-Hardであるため、A-Star を変更すると、入力のサイズが指数関数的に増加します。

証明:
(注:単純なパスについて説明します) 多項式時間で実行され、最短パス
の長さを返す多項式アルゴリズムがあると仮定します。アルゴリズムを次のようにします。kA(G,k)

パスの最大数はn!であり、その範囲にバイナリ検索を適用して[1,n!]長さ の最短パスを見つけるには、 の呼び出しnが必要O(log(n!)) = O(nlogn)ですA。
長さのパスがあることがわかった場合、nそれはハミルトニアン パスです。
グラフ内のソースとターゲットごとにプロセスを繰り返すことにより、ハミルトニアン経路問題を多項式でO(n^2)解くことができます。 QEDA

このことから、 P=NPでない限り(ほとんどの CS 研究者によると、その可能性は非常に低い)、問題は多項式で解決できないと結論付けることができます。

代替手段は、維持/設定せずに均一コスト検索のバリエーションを使用することです。閉じたノードを無効にし、それらを返して終了する代わりに、一度遭遇したソリューションを生成/生成することで、A * も変更できるかもしれませんが、現時点では A * に対してそれを証明する方法は考えられません。visitedclosed

于 2012-12-30T07:11:07.397 に答える
0

この問題が困難であることに加えて、大幅な変更の有無にかかわらず、NPこれを行うことは不可能です。主な理由は次のとおりです。A*dijkstra

まず第一に、アルゴリズムはすべてのステップでこれまでの最良のパスのみを保持します。次のグラフを検討してください。

  A
 / \
S   C-E
 \ /
  B

距離を仮定しますd(S,A)=1, d(S,B)=2, d(A,C)=d(B,C)=d(C,E)=10。

C にアクセスするときは、 を介してパスを選択しますが、 を介しAてパスを保存する場所はありませんB。したがって、この情報を保持する必要があります。

しかし、第二に、可能なすべてのパスを考慮していません。次のグラフを想定してください。

S------A--E
 \    /
  B--C

距離を仮定しますd(S,A)=1, d(S,B)=2, d(B,C)=1, d(A,E)=3。ご来店順は になります{S,A,B,C,E}。そのため、訪問するときAに迂回を保存することさえできませBんC。未訪問のすべてのネイバーに「C 経由の潜在的なパス」のようなものを追加する必要があります。

第三に、ループと袋小路を組み込む必要があります。そうです、ループを含むパスが最終的に 100 の最短パスの 1 つになる可能性は十分にあるからです。もちろん、これを制限したいかもしれませんが、それは一般的な可能性です。たとえば、次のようなグラフを考えてみましょう。

S-A--D--E
  |  |
  B--C

「戻る」ことを禁止しない限り、ここで簡単にループを開始できることは明らかです (たとえば、既にパスにD->Aある場合は禁止します)。A->D実際、これは明らかなグラフィカル ループがなくても問題です。なぜなら、一般的なケースでは、2 つの隣人 (パス) の間でいつでもピンポンできるからですA-B-A-B-A-...。

そして今、私はおそらくいくつかの問題を忘れています。

これらのほとんどは、一般的なアルゴリズムを開発することも非常に困難にすることに注意してください。確かに最後の部分は、ループを使用すると、可能なパスの数を制限するのが難しいためです (「エンドレス ループ」)。

于 2013-01-02T10:56:58.830 に答える
-1

宛先が k 回目のキューへのプッシュである場合は、* 検索を使用します。これは k 番目の最短パスになります。

于 2012-12-30T06:57:42.943 に答える