巡回サラリーマン問題（TSP）、最大独立集合の問題の解き方

巡回サラリーマン問題（TSP）の解き方

頂点は一兆個程とする。

1. 遺伝的アルゴリズムで近似解を求める
2. 5, 6個の頂点の間の回り方の、総当たりのパターンを求める
3. それを繋げて100個位くっ付けて、そこでまた遺伝的アルゴリズム（以下G）で近似解を求める。
   短い経路なら部分的にワープしてもよく、その場合頂点を追加する。
   ただし、内側の部分はワープできない。
4. それぞれの部分（頂点を適宜追加した一部分）の総当たりで、最短から近似解迄の長さの経路とそれ以外の情報を分けて保存する。（これをRとする。）
5. 1万個くっ付けて、G、R。
6. 通れない経路を作り、計算量を減らしてG、R。
7. 通れない経路を変えて、約1/n経路ずつで総当たりでG、R。
8. 通れない経路があっても常に通る場所はほぼ通る。その経路を通る場所として固定（以下固定した経路もF）する。
9. 7.8.を繰り返す。Fした経路も固定せずFした経路の情報を集める。
10. 殆どの場合Fされている経路を、通る経路として固定する。今度はFは通る経路として固定した侭にしながら9.を繰り返しFを増やす。
11. 部分的な頂点の組の数が現実的に計算可能な個数になる迄、3.～9.を繰り返す。
12. Fの情報を使ってGで解き、部分的に少しランダムに異なる経路を通りR、全ての情報を残す。
13. 極端な遠回りはしない単純なモンテカルロ法（以下SMC）で総当りで情報を残しながら解き、情報を増やす。そして全ての経路を埋めていく。
14. 残った通り方を更にSMC、後は総当りで全て試す。
    こうぼくん「？？？」

かわぐちさん「解説してあげるよ」

かわぐちさんの解説

この方法のキモは、近似解の精度を高め、より高いスコア（短い経路）を見付け出すことにあります。
すると、それより低いスコア（悪い、長い経路）の情報は捨てることができます。探索の途中で、
「この経路はここから最短の経路を通っても近似解より悪い結果になるな」
と判断した所で捨てます。
近似解の精度がよいほど、より多くの情報を捨てることができます。
そうやって情報を絞ることが大切な道のりです。これで、現実的な時間しか用いないで探索できます。

最大独立集合の問題

1. 隣り合った頂点5,6個に分ける。特に$K_2$等のnの小さい$K_n$で分ける。全ての部分の最大、最小までの全てのパターンを求める。（隣り合った頂点にプロットし、個数を求める）
2. 全てが最大になるようにして、ならないなら一ヶ所いじる。
3. 二ヶ所以上いじり、あらかじめ求めたパターンを適用する。
4. それでもダメなら合わない部分の付近をマージする。全てのデータを保持する。
5. 最後に、
   「全ての部分が最大の場合の頂点数」マイナス1、マイナス2……マイナスnを可能かどうか順番に調べる。