0

ユークリッド TSP 問題 (多数のポイント間の最短経路) のインスタンスを、既知の完全解を持つ完全なグラフで探しています。そのような例に遭遇した人はいますか？または、生成されたよりも短いルートが確実に存在しないようなインスタンスを生成する簡単なアルゴリズムはありますか?

4

1 に答える 1

2

これには問題のライブラリがあると確信しています。http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.htmlを見るとわかります

Q: 与えられた解の値は、知られている最良のものだけですか?

A: いいえ、すべての問題について、証明可能な最適解の値、または最もよく知られている下限と上限によって与えられる間隔のいずれかがリストされています。ソリューションの最適性は、分岐アンドカットまたは分岐限定アルゴリズムによって証明されています。

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.htmlも参照してください。

10 年以上前に TSPLIB を公開したとき、少なくとも大規模な問題のインスタンスを解決して最適性を証明することは、今後数年間の課題になるだろうと予想していました。

しかし、アルゴリズムの大幅な進歩により、すべての問題が最適化されて解決されました!!

于 2013-01-19T21:01:27.343 に答える