巡回セールスマン問題(TSP)の解法 その1

0. 参考文献

[1]http://www.msi.co.jp/nuopt/glossary/term_7f64c2f2bb1c2d3b292564b789b90e0d7193c8ec.html Numerical Optimizer 数理計画用語集　巡回セールスマン問題

[2]シリーズ[現代人の数理]12 巡回セールスマン問題への招待　山本芳嗣・久保幹雄　朝倉書店　初版　1997年2月20日

1. 巡回セールスマン問題(TSP)とは

都市の集合及び2都市間の移動コストが与えられた時の、全ての都市を1度ずつ通って最初の都市に戻ってくる巡回路のうち、もっとも移動コストの総量を抑える方法を求める問題を、巡回セールスマン問題(TSP, Traveling Salesman Problem)と言います。[1]今の時代であれば、例えば友人や恋人と旅行する際に、どのコースで行くかを決める際などで応用できるでしょう。

このような問題を、組み合わせ最適化問題と呼びます。詳しく知りたい方はぜひ、参考文献[2]をご覧ください。

2 移動が地上に制限された時

平面グラフの塗り分け問題と見做して解けるだろう→その2へ

3 移動が地下、航空など立体化された場合

立体グラフの塗り分け問題と見做して解けるだろう→その3へ