5

A*を使用して始点と終点の間の最適なルートを計算することができます。現在、ポイントのすべての順列のペアにA *を適用することにより、開始ポイントと終了ポイントの間にウェイポイントを含めています。

例：

ポイント1からポイント4に行きたい。さらに、ポイント2と3を通過したい。

（1、2、3、4）の順列を計算します。

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

次に、順列ごとに、最初から2番目までのA *ルートを計算し、それを2番目から3番目、次に3番目から4番目までのルートに追加します。

順列ごとにこれを計算したら、ルートを距離で並べ替えて、最短を返します。

明らかに、これは機能しますが、多くの計算が必要であり、6つのウェイポイントがあると完全に崩壊します（8つのアイテムの順列は40320です:-)）

これを行うためのより良い方法はありますか？

4

2 に答える 2

2

まず、すべての中間計算を保存する必要があります。1 から 2 までのルートを計算したら、二度と再計算してはいけません。表を参照するだけです。次に、グラフが無向の場合、2 から 1 へのルートは 1 から 2 へのルートとまったく同じ距離になるため、再計算しないでください。

そして最後に、いずれにしても、通過する必要があるポイント数に対して指数関数的なアルゴリズムが得られます。これは巡回セールスマンの問題とよく似ており、利用可能なすべての点を含めると、まさにこの問題になります。問題は NP 完全です。つまり、中間点の数に対して指数関数的な複雑さがあります。

したがって、通過しなければならないポイントがたくさんある場合、指数関数的な崩壊は避けられません。

于 2010-06-18T20:30:23.673 に答える
1

前の回答で述べたように、この問題は NP 完全巡回セールスマン問題です。

あなたが使っている方法よりも良い方法があります。最先端の TSP ソルバーは、ジョージア工科大学の Concorde ソルバーによるものです。無料で入手できるプログラムを独自に使用したり、API を使用したりすることができない場合は、彼らが使用する基本的な手法について説明できます。

TSP を解決するために、Lin-Kernighan ヒューリスティックと呼ばれる貪欲なヒューリスティックから始めて、上限を生成します。次に、TSP の混合整数計画定式化で分岐と切断を使用します。これは、一連の線形および整数の制約を記述し、解決すると TSP の最適なパスが得られることを意味します。それらの内部ループは、Qsopt や Cplex などの線形計画法ソルバーを呼び出して下限を取得します。

前述したように、これは最新技術であるため、TSP を解決するためのより良い方法を探している場合は、ここが最適です。特に対称的な平面 TSP では、数秒で 10,000 を超える都市を処理できます (これは、あなたが取り組んでいるバリアントだと思います)。

最終的に処理する必要があるウェイポイントの数が少ない場合 (たとえば 10 ～ 15 程度)、最小スパニング ツリー ヒューリスティックを使用して分枝限定検索を実行できる場合があります。これは、多くの AI 入門コースのテキスト演習です。それよりも多くのウェイポイントは、おそらくアルゴリズムの実際の実行時間よりも長く存続するため、代わりに Concorde を使用する必要があります。

于 2010-06-23T08:52:00.040 に答える