- 172 名前：デフォルトの名無しさん [2012/02/10(金) 15:56:11.47 ]
- どこに質問すべきか悩むのですが、人が多そうなのでここでさせて頂きます。
焼きなまし法で巡回セールスマン問題を解いているのですが、近傍の選択方法について悩んでいます。
1. ランダムにある1つの都市を選び、そこからの訪問先の都市と順序を入れ替えた場合
2. ランダムにある2つの都市を選び、訪問順序を入れ替えた場合
と2つの近傍を考えました。
ランダムに訪問順序を決めた時に総距離が30000程度である時、
1の近傍だと総距離が13000程度、2の近傍だと8500程度まで短くなりました。
なお最適解が既に知られており、最小総距離が7542だそうです。
一般にヒューリスティックな方法を採用した場合に、13000や8500というのはおよそ良い近似解と見なせるのでしょうか？
