Algorithm Short Course 「探索」

これは2008年11月頃に某所で内輪向けに発行した冊子に掲載したものを転載したものです。

あるとき、スーパー、郵便局、駅、etc.をまわる用事ができた。まわるべきところは高々20にすぎない。手元に住宅地図があるので、そこから最短ルートを求めようと思う。この問題は、目的地群および寮の2点間の最短距離をすべて求めてしまえば、巡回セールスマン問題になる。

とりあえず2点間距離を求める。住宅地図があるので、交差点間の接続状況とその間の距離をグラフにして、最短経路を探索することで求めることができる。個人的には”Warshall-Floyd法”が隣接行列を作る部分を除くと4行で書けるので気に入っているが、O(n³)なので、今回のようにグラフの頂点を大量生産する場合には向いていない。始点となりうる頂点が少ない場合は”Dijkstra法”が、始点1個あたりO(n²)でかなり高速化できる。この方法では近い頂点から順に同心円上に探索をすすめるが、直線距離が遠ざかる方向にも探索を進めるのは少々気になる人もいるかもしれない。このような場合には ”A*”を使う。この方法では、目的地から遠そうな頂点の距離が遠くなるように補正項を加える。今回は、直線距離を用いれば十分である。

2点間の距離は求まったので、これらの点間を最短でまわるルートを探索する。素朴に20!通りを試す必要はなく、DP（動的計画法）を用いれば、2²⁰*log20程度の計算ですませることができる。この方法の限界は、メモリ使用量とビット数である。最後に通過した頂点の番号と通過した頂点をビットで表現したものを添え字に用いた2次元配列を表に用いる。この表を順次埋めていけば、最短巡回路を求めることができる。

プログラムはある程度分かっていれば簡単に書くことできるが、実のところこの問題で一番手間がかかるのは、住宅地図の交差点のつながりをグラフとして端末に入力していく作業である。