5

一連のグラフ座標があり、それらすべてを通る最短の片道パスを見つける必要があります。始点と終点は決まっていませんが、各ポイントは 1 回だけタッチする必要があり、最適な原点に戻る必要はありません。

私はいくつかの TSP アプローチを試しましたが、それらはすべて最後に原点に戻ることに基づいているようで、この場合は非常に非効率的な結果をもたらします。

例

1、13
3、0
3、7
2、21
2、11
3、12
1、19
3、6

に解決します

3, 0
3, 6
3, 7
3, 12
2, 11
1, 13
1, 19
2, 21

ノート：

はい、検索機能を試しました。基本的に同じ質問 アルゴリズムがあります。すべてのポイント間の最短パスです が、唯一の本当の答えは TSP です。

100% 正確である必要はありません。順列メソッドは既に持っていますが、遅すぎます。少なくとも 25 ～ 30 ポイントを処理する必要があります。適切な近似値で解決することでうまくいきます。

前もって感謝します。

明確にするために編集します。TSP は img #1 のように解決する傾向があります。私の望ましい結果は img #2 です
。img 3 は TSP を介して解決された上記のサンプルであり、img #4 が望ましいです (可視性のために x 座標を -.5 後ろにシフト)
ここに画像の説明を入力 ここに画像の説明を入力 ここに画像の説明を入力 ここに画像の説明を入力
カップル#1 = TSP、#2 = 望ましい
ここに画像の説明を入力 ここに画像の説明を入力
基本的には、最も効率的な開始点と終了点を使用して、n 個のポイントを接続する最短のチェーンが必要です。

4

3 に答える 3

3

これは、すべてのエッジの重みが 1 である全ペア最短経路問題のインスタンスです。リンクされたページには、ダイクストラのアルゴリズムや A-star アルゴリズムなどの一般的なソリューションがあります。
単純なアプローチは、ノードを繰り返し処理し、他のすべてのノードへの最短パスを見つけることです。

$paths = array();
foreach ($nodes as $start) {
    foreach ($nodes as $end) {
        if ($start !== $end) {
            $path[$start][$end] = findShortestPath($graph, $start, $end);
        }
    }
}

より洗練されたアプローチfindShortestPathでは、以前の実行 (またはその目的で使用) のサブパスを記憶$pathsして、パフォーマンスを向上させます。

于 2011-01-24T09:07:20.227 に答える
3

閉ループを見つけることは気にしないので (必要なのは単一のパスだけです)、閉ループのコストを回避するために必要なポイントに小さな変更を加えることができます。これを行うには、他のすべての点からの距離が 0 になるように定義する、v と呼ぶ新しい点を追加します。次に、このグラフの TSP ソリューションを見つけます。ある時点で、v に入ってから出ます。サイクルを取り、v に出入りするエッジを削除すると、サイクルなしで各ノードを 1 回だけ訪れるパスができます。

これでも TSP を解くか概算する必要がありますが、開始点に戻るための大きなオーバーヘッドがなくなります。

于 2011-01-24T09:10:35.453 に答える
0

グラフ内の最短の閉じたパスを検索するアルゴリズムは多数あります。その問題（巡回セールスマン問題としても知られる）を解決するアルゴリズムの1つをニーズに適合させることはそれほど難しくないと思います（パスはハミルトニアンサイクルではなくハミルトニアンウェイでなければなりません）。セールスマン問題のよく知られた解決策として、ダイクストラのアルゴリズムとプリムのアルゴリズムがあります。

于 2011-01-24T09:11:16.820 に答える