[algorithm] 最適化されたTSPアルゴリズム


Answers

あなたのグラフが三角不等式を満たしていて、最適範囲内で3/2の保証を望むなら、私はchristofidesアルゴリズムを提案します。 私はphpclasses.orgでphpの実装を書いています。

Question

私は、約n = 100 to 200都市のトラベリングセールスマン問題を解決できるアルゴリズムを改善する方法を考えています。

私が与えたwikipediaリンクにはさまざまな最適化が掲載されていますが、それは非常に高いレベルであり、実際にコードで実装する方法はわかりません。

Concordeのような工業的な強みのソルバーがありますが、それらは私が望むものにはあまりにも複雑です。そして、TSPの検索を氾濫させる古典的なソリューションはすべて、無作為アルゴリズムまたは古典的なバックトラッキングアルゴリズムやダイナミックプログラミングアルゴリズムを提示します。 20都市。

だから、誰も簡単な実装方法を知っていますか?実装が100〜200行以上かかることはありません。TSPソルバーは100以上の都市で合理的な時間(数秒)で動作しますか? 私は正確なソリューションにのみ興味があります。

入力は無作為に生成されると仮定することができます。したがって、特定のアルゴリズムを破ることを特に目的とした入力は気にしません。




愚かな答えを与える:私も。 誰もがそのようなアルゴリズムでは黙っているが、既に述べたように、私は(まだ)存在していない。 Espでは、正確なノード、200ノード、数秒のランタイム、わずか200行のコードの組み合わせは不可能です。 あなたはすでにそれがNPであることを知っています。もしあなたが漸近的行動のわずかな印象を持っていれば、これを達成する方法がないことを知るべきです(NP = Pであることを証明し、 正確な商用ソルバーでさえも、数秒をはるかに超えるインスタンスが必要であり、想像するように(たとえカーネルだけを考慮したとしても)200行を超えるコード行を持っていることが想像できます。

編集:wikiのアルゴリズムは、フィールドの "通常の疑い"です:線形プログラミングとブランチとバインド。 何千ものノードを持つインスタンスのソリューションは、解決するために数年を要しました(非常に多くのCPUを並列していたので、より速く実行できます)。 いくつかは、境界と境界問題の境界に固有の知識のためにも使用されるので、一般的なアプローチはありません。

ブランチとバウンドはすべての可能なパスを列挙し(例:バックトラッキング)、結果が既に見つかったソリューションよりも優れていないことを証明できるときに開始再帰を停止するソリューションがある場合に適用します。あなたの都市と道はすでに200都市ツアーよりも長くなっています。その2都市の組み合わせから始まるすべてのツアーを破棄することができます)。 ここでは、非常に多くの問題に固有の知識を関数に追加して、パスが既に見つかっている解決策より優れているとは言えません。 それが良いほど、あなたが見なければならない経路が少ないほど、あなたのアルゴリズムはより速くなります。

線形計画法は線形不等式問題を解くための最適化方法です。 それは多項式時間(実際にはシンプレックスですが、ここでは問題ありません)で動作しますが、その解決策は本当です。 解が整数でなければならないという追加の制約があるとき、それはNP完全を得る。 小さなインスタンスの場合は、それを解決する1つの方法など、可能性があります。次に、整数部分に違反する解の変数を見て、それを変更する追加不等式を追加します(これは切断面と呼ばれます。 (高次元)平面では、解空間はポリトープであり、追加の不等式を追加することで、ポリトープから平面を持つものを切り取ることができます)。 話題は非常に複雑で、一般的なシンプルシンプルでさえ、数学を深く掘り下げたくないときには分かりません。 いくつかの良い本がありますが、ベターの1つはChvatal、Linear Programmingですが、さらにいくつかあります。




コンコルド・ライブラリーからHeld-Karpアルゴリズムを採用し、25都市を0.15秒で解決しました。 このパフォーマンスは私にとって完璧です! concordeライブラリ( http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm)からhold-karpのコード(ANSI Cで記述)を抽出することができます 。 ダウンロードの拡張子がgzの場合は、tgzにする必要があります。 名前を変更する必要があるかもしれません。 次に、VC ++で移植するための少しの調整を行う必要があります。 最初にファイルholdkarp hとc(名前をcppに変更)と他の約5つのファイルをとり、調整を行い、edgelen:euclid_ceiling_edgelenでCCheldkarp_small(...)を呼び出す必要があります。




Related