巡回セールマン問題の命題そのものを振り返ってみる
1. 初めに
巡回セールスマン問題と凸図形の関係を読み直しているときに、ふと気が付きました。
巡回セールスマン問題の問いはどのような形で出題されるのだろうか?と。
2. 錯覚?
筆者は、都市の座標が羅列されたノード群のみが与えられると思っていました。そして、都市間は直線で結ばれており、その距離(重み)は座標から求められると思っていました。
3. 都市の座標ではなく都市間の距離(重み)が与えられる?
都市間は直線で結ばれるのではなく、曲線も許しているのでしょうか?そして都市間の距離(重み)は座標とは別に与えられるのでしょうか?
そうであれば、 巡回セールスマン問題と凸図形の関係の前提は根底から覆されてしまいます。
4. 拡張性
もし、「3. 都市の座標ではなく都市間の距離(重み)が与えられる?」が正しい命題の一部であったとすると筆者の巡回セールスマン問題の解法は根底から覆されてしまいます。
しかし、巡回セールスマン問題と凸図形の関係を前提とした筆者の巡回セールスマン問題の解法は、拡張性がほとんどないことを筆者自身も認識していて「命題の出し方が不親切である」とごねることはありません。
唯一残るモデル性は、モンテカルロ木のような分枝の消去法だけであり、巡回セールスマン問題以外の命題を解くとき、その命題ごとに消去条件を考え出さなければなりません。
5. 最後に
このブログを書くことによって、筆者の目的は「巡回セールスマン問題の解法」ではなくなってきたように思いますので、上述のような破綻が訪れてもそう大きな落胆とはならないようです。そして、それはおそらく負け惜しみではありません。
この記事を投稿する直前にgoogleで「巡回セールスマン問題」を検索し、Wikipediaを見たところ、筆者の想定してい命題は「平面TSP」に属するようです。
なお、巡回セールスマン問題の命題を読み返してみたところ、都市の位置と都市間の移動コスト(筆者は距離とか重みとしていました)から答えを導きだすものが、真?の命題のようです。つまり、座標(位置)から移動コスト(距離)を決定するものではありませんでした。
座標(位置)から移動コスト(距離)を決定する命題は「平面TSP」と呼ばれるようですが、これもはっきりと断言できません。