Euclidean TSPをやって、100頂点程度までなら最適解を出せた、という研究

この先行研究は1990年代とかでかなり古いっぽい。

入力は、2次元平面上の $n$ 点の座標で、出力は ${1, 2, \ldots, n}$ のpermutation.

RLで、policy $p(\pi | s)$ を学習するっぽい。

条件付き確率で分解する。

f:id:xuzijian629:20191222161236p:plain

ただし $\pi ( \lt i)$ は先頭 $i - 1$ 個のpermutationを指す。

グラフの頂点数 $n$ が違う場合にでも対応できるように、pointer networkというものを使っているっぽい。

とりあえずQiitaの記事があったけど、入力サイズが可変なときに対応できるらしい。

意味不明なのでとりあえずここで終了

感想

policy based RLであることは我々の手法と同じだがさすがに時代が違いすぎてやっていることが違いすぎるのであんまり関係なさそう

結果も100頂点なのは小さすぎる

Joeの精進記録