2

デカルト平面上のグラフの最適なツアーを毎回解決する分枝限定アルゴリズムを設計する必要があります。ランタイムの早い段階で絶望的な分岐を特定すると、「100 倍速く」実行されるプログラムに統合されるというヒントが与えられました。開始/終了ノードに接続された最短のエッジがツアーの最初または最後のエッジになると仮定するという考えがありましたが、薄いひし形のグラフはそうではないことを証明しています。これらの絶望的なブランチを排除する方法や、これについて言及しているリファレンスを持っている人はいますか?

基本的に、辞書順だけでなく、ソリューションのサブセットに分岐するためのより良い方法はありますか? 最初の分岐はエッジ ab を含めて除外し、2 番目の分岐は分岐 ac を含めて除外します

4

2 に答える 2

1

最近傍は単純なアルゴリズムです。分枝限定法は単なる最適化ループであり、さらにサブ問題ソルバーが必要です。最近傍も分枝限定アルゴリズムだと思います。代わりに、シンプレックスアルゴリズムを調べます。これは線形計画法アルゴリズムです。また、tspを解くための切断面アルゴリズム。

于 2012-12-03T00:48:44.767 に答える
1

したがって、分枝限定アルゴリズムのどこかで、可能な場所を調べてから、何らかの方法でそれらを追跡して後で実行します。

これをより効率的にするために、いくつかのことを行うことができます。

  1. より適切な境界計算機を作成します。つまり、境界をより正確に決定するアルゴリズムを考え出します。これにより、貧弱であることが判明したパスに費やされる時間が短縮されます。
  2. スタックを使用してタスクを追跡する代わりに、キューを使用します。キューを使用する代わりに、優先度の高いキュー (ヒープ) を使用します。たとえば、最適と思われるものはヒープの一番上に配置され、悪いと思われるものは一番下に配置されます。
于 2012-12-03T00:57:23.487 に答える