MST を使用して TSP の最も最適な (または最適に近い) 上限を見つけるための最も効果的な方法について知りたいです。速度のためにアルゴリズムを最適化しようとしていますが、MST を見つけた後、「適切な」境界をアルゴリズムで計算するのに問題があります。ベースバウンドが であることは知っています2 x MST lengthが、これは私たちができる最善のことではないようです. 参考文献や洞察をいただければ幸いです。
1933 次
1 に答える
0
おそらく、MST をツアーに変換する必要があります。これにより、線形時間で 2 * MST の長さ未満の境界が得られます。Christofide's Algorithm と呼ばれる MST の拡張もあり、これも検討する価値があります。
TSP ヒューリスティックについては、ウィキペディアのページを参照することをお勧めします。
于 2013-04-23T02:59:40.510 に答える