Cleaning Robot 解説

問題名：Cleaning Robot (PKU)
出典：Problem F, ACM/ICPC Japan Domestic, 2005-07-01
難易度：☆☆☆
問題の種類：グラフ
解法：距離行列作成＋TSP
解答ソースコード：
- 2688-deq.cpp

アルゴリズムの概略

「最大10個の汚れたタイルを全て掃除するための最小移動回数を求めよ」という問題。実装能力が多少問われますが，問題自体はよく読めば単純です。汚れたタイルの数が最大10個というのがミソ。

問題から，「汚れたタイル」を全て訪問するために必要な最短距離を求めればいいことがわかります。これはいわゆる巡回セールスマン問題 (TSP) と呼ばれている有名な問題です（唯一違う点は，今回は出発地点に戻ってくる必要がないことですね）。

そのためには，まずは各「汚れたタイル」間の距離を全て求めておく必要があります。これは表の形に書いておけるので，距離行列と呼ばれています。距離行列が求まれば，後は最大10地点のTSPを解くだけです。

結局，「汚れたタイル」をノードとみなし，

ノード間の距離行列を作成し，
距離行列をもとにTSPを解く

ことでこの問題は解けます。

距離行列の作成

ノード間の距離行列を作成するには，2点間の距離を全て求めていく必要があります。これにはいくつか方法がありますが，ここでは単純な幅優先探索の方法を説明します（他には最短経路問題のダイクストラ法でもOKです）。

例として，次のデータセットにおいて，スタート地点から各ノードへの距離を求めてみます。

.......
.o...*.
.......
.*...*.
.......

まず，各ノードの (x, y) 座標を別に記録しておきます。さらに探索時にフィールドを上書きするので，元のフィールド（上の図）をコピーしておいて，そちらで探索作業を行います。コピーされた作業フィールドの初期値は次のような感じになります：

.......
.0.....
.......
.......
.......

ここでは，未到達の場所を元データと同じように . としていますが，実際は -1 などの数字です。また，障害物などの壁があれば記入しておく必要があります。

さて，まずは距離 0 の地点から移動できる場所に 1 を記入していきます：

.1.....
101....
.1.....
.......
.......

これらは最適解です。つまり，1 と記入された地点にはこれ以上早く到達することはできません（当然ですね）。さらに，これらの距離 1 の最適解から最短で移動できる場所を順次調べていけば，それらも最適解となります。つまり，次のステップは

212....
1012...
212....
.2.....
.......

となります。同様に，次は距離 2 を展開し，順次 3, 4, 5, ... としていけば，各地点への最短距離が求まっていきます：

2123...   21234..   212345.   2123456   2123456   2123456
10123..   101234.   1012345   1012345   1012345   1012345
2123...   21234..   212345.   2123456   2123456   2123456
323....   3234...   32345..   323456.   3234567   3234567
.3.....   434....   4345...   43456..   434567.   4345678

このように求めていって，変化がなくなれば，そこで終了です。

ノードが存在する地点だけを見てみると，

.......
.0...4.
.......
.2...6.
.......

という感じで，スタート地点から各ノードへの距離が求まります。以上のアルゴリズムを使って，同じようにノード1から，ノード2から…と求めていけば，最終的な距離行列が得られます。

アルゴリズムの実装と計算量

具体的な実装としては，毎回全ての地点を調べる素朴な方法と，次に展開する地点を待ち行列で保持しておく方法があります。

素朴な方法の場合，毎回全ての地点（フィールドの大きさ＝W×H回）を調べる，それが最大距離 W×H まで行われるので，計算量は最悪 W²×H² = 20⁴ = 160,000 程度で済みます（実際は距離はそこまで大きくならないのでもっと少なくなりますが）。これを各ノードを開始地点として行うので，ノード数 11 を掛けて最大 1,760,000 程度の計算量となります。

待ち行列を使う場合は，各地点を1回ずつ調べるだけでよいので，フィールドの大きさ = W×H = 20² = 400 程度で一回の探索が終了します。各ノードを開始地点としてノード数分行うと，全体として 4,400 程度の計算量で済みます。

待ち行列を使った方が圧倒的に計算量は少なく済みますが，この問題ではどちらの方法でも解けてしまいます。

TSP

一般的にTSPはNP困難に属する「最適解が実用時間内には求められない」難しい問題とされています。しかしながら，この問題のようにノード数が非常に少ない場合，力ずく（＝全探索）でも解けてしまいます。

各ノードを1回だけ通るパスは，n ノードの場合全部で n! だけあるので，全探索の計算量は n! になります（これは指数関数的に爆発します）。この値を実際に計算してみると，

 1! =                 1
 2! =                 2
 3! =                 6
 4! =                24
 5! =               120
 6! =               720
 7! =             5,040
 8! =            40,320
 9! =           362,880
10! =         3,628,800 =   4M
11! =        39,916,800 =  40M
12! =       479,001,600 = 500M
13! =     6,227,020,800 =   6G
14! =    87,178,291,200 =  90G
15! = 1,307,674,368,000 =   1T

というように増えていきます。 n = 10 であれば 4M ですので，全探索でも実用時間内に解けてしまいます。しかし，「汚れたタイル」の数が3つ増えて n = 13 になるともう全探索では解けなくなりますので注意が必要です。

ここでは本当に全探索を行っても数秒以内でプログラムが終了する^*1ので，実行に制限時間が存在しない国内予選では全探索でOKです。 PKUではそのままだとTLEになりますが，探索の途中で「今までの最短距離をすでに上回っていることが分かれば打ち切ってしまう」という自明の枝刈り条件を入れれば通ります。

補足1: 全探索の順列生成として， C++で #include <algorithm> を宣言すると next_permutation が使えますが，実際に使ってみたところ非常に遅かったです。工夫をすると速く動くのかもしれませんが，計算時間がシビアな状況で使うには注意が必要でしょう。

$Id: index.shtml 1444 2007-04-19 13:05:50Z SYSTEM $

deq notes