TSPを解くための動的計画法を用いたアルゴリズム
学校の講義でこれを使わないと解けない問題が出されました。みんな2-opt, 3-opt, 焼きなましなど近似解で挑戦していました。(もちろん私も)
しかし一向に最適解をとれず先生に聞いたらこのアルゴリズムを教えてもらい、無事解くことができました。割と小さいケースのtspまでしか対応できないのでその点はご注意ください。(JGraphTライブラリにも少し用途が狭いheld karpの実装がいますが、頂点数を31個までに制限しています。)
アルゴリズム解説
頂点の集合を$S$とします。ここで$S = ${ $A, B, C, D, E$ } として$A$から$E$までの最短経路長を求めます。
距離行列を以下のようにおきます。半分は省略します。
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 9 | 9 | 9 |
| B | 1 | 0 | 1 | 9 | 9 |
| C | 9 | 1 | 0 | 1 | 9 |
| D | 9 | 9 | 1 | 0 | 1 |
| E | 9 | 9 | 9 | 1 | 0 |
図に起こすと以下のようになります。頭から時計回りにA, B, C...としてその外周が最短経路です。
AからEまでの最短経路長を
- g(E, {B, C, D})
と表します。第一引数が終点で第二引数が途中に通過しなければならない点の集合です。そしてこれは以下のように表されます。
- g(E, {B, C, D}) = min(EB + g(B, {C, D}), EC + g(C, {B, D}), ED + g(D, {B, C}))
終点Eの手前にどの頂点がいるべきかを調べるわけです。これを再帰的に繰り返します。
- g(B, {C, D}) = min(BC+g(C, {D}), BD+g(D, {C}))
- g(C, {B, D}) = min(CB+g(B, {D}), CD+g(D, {B}))
- g(D, {B, C}) = min(DB+g(B, {C}), DC+g(C, {B}))
第二引数が空集合となるときはAとその頂点の距離を表します。空集合を{}と表します。
- g(C, {D}) = min(CD+g(D, {}))
- g(D, {C}) = min(DC+g(C, {}))
- g(B, {D}) = min(BD+g(D, {}))
- g(D, {B}) = min(DB+g(B, {}))
- g(B, {C}) = min(BC+g(C, {}))
- g(C, {B}) = min(CB+g(B, {}))
以上まで求められたら隣接行列をもとに最短経路長を求めることができます。ちなみにminで選ばれた引数のgの第一引数を集めると最短経路をとることができます。
実際の実装はどうなるか
学校の問題をそのまま晒すと怒られそうなので自分の実装の要所だけ説明します。
このアルゴリズムは以下のような二次配列を埋めることで機能します。行は始点を除く頂点集合のすべての組み合わせです。列は各頂点です。
| A | B | C | D | E | |
|---|---|---|---|---|---|
| {} | |||||
| {B} | |||||
| {C} | |||||
| {D} | |||||
| {B, C} | |||||
| {B, D} | |||||
| {B, E} | |||||
| ... |
ただし使わない要素もあるのでそこは適当な大きい値を代入します。具体的には途中点を指定する集合に終点が含まれていたら世話ないのでその行の集合に終点が含まれていたら処理しません。その要素は下の要素から見られることはないので大丈夫です。
すべての組み合わせを列挙するのでメモリオーダーも計算量もかなり必要です。
単純に最短経路長を欲しいときはintの二次配列で十分ですが、その途中点の訪問順を知りたいときは自分の一つ前の訪問頂点とそこまでの最短経路長をもつクラスを作ります。
組み合わせに関してはこれをコピペするといいです。
集合に関してはbitで管理しました。処理しない要素かどうかは集合のbitとその頂点のbitのみ立てた値でわかるので楽です。
おわりに
これを知るまでtspは簡単に解けないものだと思っていましたが案外きちんと解くことができて嬉しかったです。matlabのほうに頂点数200でもサクサク解ける機能があって驚きました。