巡回セールスマン問題の解法のアルゴリズム
１． 初めに
・2019/03/30 巡回セールスマン問題と凸図形の関係
・2019/04/06 巡回セールスマン問題をモンテカルロ木探索で解く
上の2つの記事を元にして平面ＴＳＰのアルゴリズムを組みたいと思います。
２． 入力データ
#define NN nnxx
ｌｏｎｇ ｎｎ・・・ノードの点数
ｄｏｕｂｌｅ pp（NN，NN）・・・ノードの座標
ノードのＩＤは、配列の添え数と同じにします。
筆者の流儀として、変数名は2文字以上としています。
なお、ノード間の移動コストは、直線距離として求めます。
３． 初期処理
すべての線分の情報を取得します。
３．１ 線分情報
LINEAR line(NN*NN/2)・・・線分の情報（実際の線分数はｎｎ*（ｎｎ－１）/2になります。）
struct LINEAR{
long ltype・・・通常０：ｘ軸と並行１：ｙ軸と並行２
double apara・・・ｙ＝ａｘ＋ｂのときのａ
double bpara・・・ｙ＝ａｘ＋ｂのときのｂ
double dist・・・・・距離
}
ノードＩＤp1とp2からなる線分のLINEAR line(）の添え数を(p1-1)*nn+p2-1とします。
３．２ 交点情報
long pcross(NN*NN/2,NN*NN/2)・・・交点が存在しない０：両線分内で交点を持つ１：パス候補（wpath）線分外で交点を持ち、もう一方の線分内で交点を持つ２：その他０
① 実装メモリに余裕のあるとき＆実行速度を速くしたとき、交点情報を初期段階で処理します。
② 実装メモリに余裕がないときは、必要なとき随時交点情報を計算します。
③ 必要な交点情報だけを保持する方法もあります（凸図形内に交点が存在しない０を情報として持たない）が、アルゴリズムが複雑になるので割愛します。
３．３ Ｌ集合とＲ集合
long lrset(NN*NN/2,NN*NN/2)・・・Ｌ集合またはＲ集合が０の時⇒０：Ｌ集合とＲ集合の両方が１以上⇒１
４． 核となるアルゴリズム
① 任意のノードを木構造の頂点とします。例えば、プログラム実装時は添え数０＝pp(0,0)です。
そして、このノードＩＤを始点として作業用パス変数long wpath(NN)に投入します。
つまり、wpath(0)=頂点（始点）ノードＩＤです。
さらに、層ポインタを1つ増やします。long lvpos=0⇒lvpos++
② 第2層のノードを配列に保持します。
long p2(NN)・・・第2層のノードＩＤ
層ポインタを１つ増やします。lvpos++
第2層では、nn-2回ループ処理する必要があります。
③ 続行の可否を判断する①
①と②で１つの線分（ループの一部）ができました。
ここで、この線分が最短パスの一部となる可能性があるか否かを判断します。
・ pcross（）がタイプ２のとき・・・有効
・ pcross（）がタイプ０のとき
lrset（）がタイプ０のとき・・・有効
lrset（）がタイプ１のとき・・・無効（このパスは後続の計算が不必要）
④ 端から順に計算する
このまま、第2層を処理していくと保持するメモリの量が膨大になります。
そこで端から順に層を深くして処理を行います。
アルゴリズムは、いくつの点数を処理するのかあらかじめわかっていないものとすると、底層が第何層になるかわかりません。
そこで、この核となるアルゴリズムを関数として、その関数の呼び出し側でループを制御します。
重要なのは、現在処理している部分がどこなのか知っていることです。
つまり、層ポインタと層の中の位置です。
もちろん、構成してきたパス情報（wpath）も保持していなければなりません。
⑤ 続行の可否を判断する②
層が深くなっていくと、パスを構成するノード数と共に線分数も増えていきます。
続行の可否を判断する条件は、線分群が凸図形を2分割しているか否かです（Ｌ集合かＲ集合が空集合以外のとき）。
ところが、アルゴリズムは与えられた入力が凸図形か否かを知りません。しかし、与えられたノード集合から凸図形を描くことをアルゴリズムの作成者は知っています。
そこで、次の条件のとき凸図形が2分割されたと判断します。
パスを構成する線分のpcross（）がタイプ２のＡＮＤが、空集合にならないとき・・・有効
それ以外の時、
lrset（）がタイプ０のとき・・・有効
lrset（）がタイプ１のとき・・・無効（このパスは後続の計算が不必要）
（ lrsetは随時計算が必要かわからなくなってきました）
⑥ メモリの保持
long p2(nnxx)・・・第2層のノードＩＤと同じように各層に配列が必要になってきますが、実装メモリに余裕がない場合、malloc()関数などで、節約する方法もあります。
５． 最後に
「４． 核となるアルゴリズム」で核関数と関数の呼び出し側の処理がごっちゃになりましたが、ご容赦ください。
筆者がＳＥとして現役時代は上のようなざっくりとしたアルゴリズムからコーディングやテストを行っていました（筆者はチームプレーがあまり得意でなかったのですいません）。
2019年4月27日～2019年5月6日まで休暇なので上のアルゴリズムからプログラムを作ってテストを行い、どの程度の計算量になるか測ってみたいと思います。
なお、どのような結果になっても報告はしたいと思います。そして、ソースも公開したいと思いますが、言語はＶＢになるかもしれません。ＶＢの方が手っ取り早いので。
また、線分上にノードが乗っかるケースなど、不具合があることは承知していますが、随時修正していきたいと思います。
閉路となるパスが複数存在しますが、その中の最短のパスを解とします。
