迷路最短経路問題
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほかの話
僕が受験者で、こういう問題を出されとしたら、まず確認することがひとつある。
「迷路のサイズの上限が設定されていませんが、4TBのテキストファイルで迷路が与えられる可能性を考慮すべきですか？」考慮しなくていいと書いていない以上、デフォルトでは考慮すべきであり、で考慮するととてもめんどくさいので後で「あ、そこまで要求してなかったのに」とか言われないために出題者が自覚しているか確認する必要がある。
で、「yes」って言われたら…なかなか歯ごたえのある問題だな！
迷路が正方形とはどこにも書いていない以上、縦4マス横1テラマスの迷路でもvalid。だから「迷路のデータファイルを1行読んで」なんて書いてたらその時点でアウト。最初にすべきことは安全な文字数ずつ頭から読んでいって最初に現れる改行の位置を調べること。改行の文字コードがなんであるかは指定されていないのでCRが見つかった場合はLFが続くかどうか確認する必要があるだろう。
そうやって1行の長さLINE_WIDTHと改行コードの長さNLがわかれば、あとは任意の座標(x, y)の値が読みたければx + y * (LINE_WIDTH + NL)の位置にシークすればいいので、メモリに迷路データを持たずに処理ができる。
次に考慮すべきは「探索の縁のサイズが最大どれくらいになるか」だろう。探索の縁ってのは幅優先探索の「次に探索すべきものリスト」と同じ意味にとってもいい。どちらにせよ、これは障害物が全くないときに1ステップに4ずつ増える。縦横2メガマスずつの正方形の真ん中にスタートがある時の1メガステップ目が一番大きくなり、そのサイズは4メガマス。ということは探索の縁1マスあたり500KBくらいまではメモリに乗せても大丈夫そう。当たり前だけども「そこまでの最短経路」全体をメモリに乗せてはいけない(最悪の場合4テラマスの一本道があり得る)
ここらでそろそろ擬似コードを考え始める。まず最初の改行コードサーチの時に最悪の場合データ全体を舐めるはめになるので、スタートを探すのも同時にしておこう。
LINE_WIDTH, NL, START_POS = initial_search()
でもって、3つのリストを作る。prevとcurとnext。
prev = [] cur = [(START_POS, None)]
繰り返しスタート: curの各要素posについての4方向の隣の座標を計算する。そのそれぞれにつき、それpがprevに含まれていないかを確認する。含まれていなかったものについて、データファイルを見に行ってそれが障害物やゴールでないかを確認する。どちらでもなければnextに(p, pos)を追加する。ゴールだった場合の処理は後で書く。
curの全要素の探索が終わったら、
prevをファイルに書き出し prev = cur cur = next next = []
する。prevのファイルへの書き出しは、後で戻しやすいように連番整数などを振っていく。ここでメモリ使用量を念のため確認するけど、xやyの値が最大4テラになりうると言うことはまあ6バイトあれば足りるので、2メガマス * 3 * 4 * 6バイトで28MB。十分十分。たぶんPythonで書いても大丈夫なレベルだ。
さて、ここで繰り返しスタートへ戻る。こうやって「スタート」「スタートから1ステップで到達できるマス(とその1歩前のマス)」「2ステップで到達出来るマス(とその1歩前のマス)」というファイルが順に出力されていく。ループを抜けるのは先ほど説明を省いた「ファイルの指定座標を読んだらゴールだった」の場合。その時には書き出して行ったファイルを逆の順番に読みながら1歩ずつ遡っていけば最短経路がわかる。
とここまでを自然言語で説明した上で、最後にもうひとつ確認する。「で、これを実際にコードに落とす必要がありますか？」…だってここまで考え終わった時点でもう飽きちゃったもん。書かないでいいなら書かない(笑)
id:showyou 2010/04/03 11:50 4テラバイトとかいうともはやファイルシステムの仕様すら気にした方が良いレベルだなぁ。
とりあえずNTFSのMax file sizeは16 エクサバイト弱なので余裕かと思った。だけど迷路サイズが16エクサバイトだと探索の縁はいくらになるのかな。8ギガマスくらいになっちゃうのかな。だとすると「メモリに乗せていい」という判断は間違いってことになるか。nextとcurに関してはファイルに追記で書き出したり、ファイルの頭からシーケンシャルに読んで行くので構わないからメモリに持つ必要はないけど、prevをファイルに置いてcurの1マスごとに全探索したのではかなり遅くなるだろうなぁ。
