2

私はこの問題を解決しようとしていますhttp://coj.uci.cu/24h/problem.xhtml?abb=1368。

多くの調査と多くの時間を費やした後、TSPの分枝限定アルゴリズムを実装することができました。これにより、すべてのポイントを通過して開始に戻るパスが取得されます。

そのパスから最長のエッジを削除すると答えが得られると思っていましたが、アルゴリズムを終了した直後に、この質問を読んで、これがすべての場合に当てはまらないことを発見しました：最小距離ハミルトンパスJavascript

距離がゼロのダミーポイントを1点おきに追加して削除すると問題が解決するという回答をいくつか見つけましたが、その詳細はわかりません。私はすでにそのダミーポイントを追加しましたが、26.01を取得する代わりに、16.23になりました。「ダミーポイント追加の要点」がよくわからないので、まだダミーポイントを削除していません。

これを解決するために私を導いてくれませんか？それとも、TSPの代わりに別のアプローチを取る方が良いですか？

4

1 に答える 1

1

ダミーポイントを使用すると、2つの端を任意の距離で接続できます。TSPでは、合計距離を最小化するために、2つの端も互いに非常に接近している必要があります。パスの問題では、この要件は存在しないため、TSP最適値は、問題に対して無効な制約の主観であり、パスの問題に最適ではない可能性があります。

ダミーポイントを導入すると（またはショートカット、ワームホールと考えると）、距離に影響を与えることなく、両端が遠く離れている可能性があります。

于 2012-11-05T08:10:52.310 に答える