巡回セールスマン問題をモンテカルロ木探索で解く
１． 初めに
筆者がモンテカルロ木探索を知ったのはごく最近です。巡回セールマン問題の解法を25年間求めていた筆者が辿り着いた解法がモンテカルロ木探索によく似ていたので、このモンテカルロ木探索の有効性を数値によって測ってみたいと思いました。
なお、筆者による巡回セールスマン問題の解法は、遅くとも今年（2019年）の夏くらいまでには記事にしたいと思っています（Ｃ言語によるソース公開を予定しています）が、筆者の解法は次の２つの問題を抱えていました。
① 速度・・・解法と呼べるほど有効な解法であるか？
② 解法に論理的な破綻を含んでいないか？
①の問題は、この記事（または後続記事）によってある程度解決できることを期待しています。
②の問題は、筆者の解法を検証してくれる人がいないので今年（2019年）の5月くらいに実行可能なプログラムを作成して、公開したいと思っています。（理論は後からついてくるという乱暴な実力行使みたいなものですね（笑い））
②は①の期待速度がそれほどでもなければ、また何かを考え直さなければならないので、まず本記事などで①の問題を解決したいと思います。
２． モンテカルロ木探索
以下の記述は「モンテカルロ木探索」をある程度理解しているものとして書いていますのでご容赦ください。とはいっても、そもそも「モンテカルロ木探索」の詳細を筆者もよく知りません。
モンテカルロ木探索は主にゲームなどの場面で用いられる手法（アルゴリズム）であると認識しています。そして、その手法（アルゴリズム）は確率的なものだと認識しています。
確率的な部分は、下位の枝ノードを生成するか否かの判断に用いられるものと思っていますが、筆者の巡回セールスマン問題の解法は、確率的ではなく厳密に下位の枝ノードを生成するか否かを判断します。
結論として、「モンテカルロ木探索」は下位の枝ノードを生成するか否かの判断によって膨大な計算不可能な計算量を計算可能な計算量にするものとみなします（確率的か厳密的かを問わず）。
３． 凸図形を描く点（座標）配置を解く
巡回セールスマン問題を解くときの１つのケースをモンテカルロ木探索を使って考えてみます。それはノードの座標配置が凸図形となるケースです。
ただし、巡回セールスマン問題を直接解くわけではありません。まず、複数の閉路（パス）を作成します。その複数の閉路（パス）から最短の閉路（パス）を選択します。
なお、一般的に木（ツリー）の階層を何と呼ぶか筆者はよく知らないので、頂点ノードを第1層、次の枝ノードを第2層、深さが増すごとに第3．．．第ｎ層と呼ぶことにします。また、木構造の最深層を底層と呼ぶことにします。
３．１ 任意の１つのノード
凸図形から任意の1点（ノード）を選択します。
巡回セールスマン問題では、与えられた点（ノード）のすべてを必ず1回だけ通過しなければなりません。従って、選択するのは１つのノードが必要十分条件であると考えます。
このノードが第1層となり、このノードがパスの始点となります。
３．２ １つのノードから作られるすべての線分
第1層のノードから作られるすべての線分を考えます。
ノード数がＮ点数であるとき、この線分の数はＮ－１となります。”－１”は頂点（自分自身）のノードを意味し、除外されるからです。
そして頂点ノードから枝ノードを派生させます（第2層）。
３．３ 排除するノード
図3
図3において第1層のノード（Ａ）からつながるノード（第2層）は両隣のノード（ＢＣ）を除いてすべて対角線となります（例えば線分ＡＤ）。この対角線は凸図形を描くノード群を完全に2分割します。この2分割されたノードの集合をＬ（左）集合とＲ（右）集合とします。
ここで、対角線（例えば線分ＡＤ）と交差しないでＬ集合とＲ集合をつなぐ線分は存在しません。つまり、対角線となる線分はモンテカルロ木から排除されることになります。
巡回セールスマン問題と凸図形の関係（２． 最短パスは交差する線分を含まない）から
結果として、ノードＡとつながるノードはＢかＣだけが許されることになります。そして、ＢとＣのいずれを選択しても結果として逆回りの閉路（パス）を生成するので、Ｂだけについて述べたいと思います。
３．４ 第3層以降
Ｂ（第2層）につながるノード（第3層）は、凸図形の外周の両隣のノードしか存在しません。「３．３ 排除するノード」と同じ理由からです。さらに片方のノードは１つ前の層のノード（Ｂの場合はＡ）と同じなので選択できるノードは１つしか存在しないことになります。
以下、底層が第1層と一致するまで同じことの繰り返しになります。
３．５ 計算量
上述のように凸図形を描く点（座標）配置を巡回セールスマン問題に与えた場合、Ｎ！通りの計算量が、（第1層は1通り）、第2層はＮ－1通り、第3層はＮ－2通り、底層はＮ－Ｎ＋1通りとなります。
すなわち、（Ｎ－1）＋（Ｎ－2）＋．．．（Ｎ－Ｎ＋１）の2倍≒Ｎの2乗通りとなります。
４． 凸図形が内包するノードのケース
図４
図4のように凸図形の内部にノードＥを加えてみます。
４．１ 第1層
第1層は同じくＡとします。
４．２ 第2層
第2層はＢＣにＥが加わりますが、ＥのケースとＢのケースだけを考えます。
４．３ Ｅのケース
第1層Ａ、第2層Ｅのとき、第3層に許されるのは、ＢかＣだけです。
なぜならば、それ以外のノードは対角線と同じく凸図形を描くノード群を完全に2分割します（例えば線分ＡＥとＥＤ）。
Ｂ（ＡＥＢ）とＣ（ＡＣＥ）も凸図形を描くノード群を完全に2分割しますが、ＬかＲ集合のどちらかが空集合となります。つまりＬとＲ集合をつなぐ線分は必要なくなります。
４．４ ＢＣのケース
第1層Ａ、第2層ＢかＣのとき、第3層に許されるのは、ＥかＢＣに隣接するノードだけです。
第3層がＥのとき、「４．３ Ｅのケース」と同じとなり、ＢＣのとき、「３． 凸図形を描く点（座標）配置を解く」と同じになります。
４．５ 計算量
凸図形が1点のノードだけを内包するとき、Ｎ！通りと比較にならないくらい計算量が小さくなることがわかりますが、凸図形に相当数のノードが内包されるとき、どのくらいの計算量になるか残念ながらよくわかっていません（う～ん、結論としては弱いですね）。
ただ、計算量を求める法則があるような気だけはしています。興味のある方は探してみてはいかがでしょうか？
４．６ 特異なケース
ノードＥがどれかの対角線上に存在するとき、どのような処理をすればいいのかわかっていません。
もしかすれば、このケースが大きな意味を持っているかもしれませんし、簡単に処理できる問題かもしれません。
ただ、筆者はこのケースは巡回セールスマン問題の解法にとって全体から考えれば小さな問題と考えているので、当面このケースを考えるつもりはありません。
５． 最後に
５．１ 厳密解のアルゴリズム
次の記事から厳密解のアルゴリズムを掲載したいと思います（ソースの公開はまだ先になりそうです）。もっともアルゴリズムに欠陥があるかもしれませんし、予想しているような点数を予想しているような現実的な時間で解けるかわかりません。
５．２ 座標配置と計算時間
上述したことに疎漏がなければ、与えられたノード群を解くときノードの座標配置と計算時間に関係があることがわかりました。つまり、「凸図形に内包するノードの数が多いほど計算量は多くなる可能性が高い」ということです。
感覚的にですが、内包するノードの座標配置によっても計算量は作用されるのではないかと考えています。
５．３ 拡張性に難点あり
上述したことの前提は、ユークリッドの2次元空間上での解法の考え方であるということです。
例えば、ユークリッドの3次元空間では、巡回セールスマン問題と凸図形の関係（２． 最短パスは交差する線分を含まない）は成立しません。それ以外の条件を考え出さなければなりません。
５．４ 領域を作る座標配置
薄々感じていたことですが、このブログの記事によって考えを整理しているうちに1つの僅かな光明を得ました。
それは、「同じ点数のノードであっても座標配置によって異なる情報を持つ」ということです。
例えば、上述の手法を用いれば、巡回セールマン問題を解く過程で、解く過程が座標配置から領域を作って（あるいは切り取って）いきます。これは2次元上のことですが、解法を3次元に拡張できれば、ある科学的問題を解明できるのではないかと期待しています。
なお、領域はＬまたはＲ集合が空集合になったとき構成されます。
