cyber205の日記： 某社の採用試験は迷路の最短経路探索プログラム 12
日記 by
cyber205
人材獲得作戦・４ 試験問題ほか
う～む。
AAで問題となる迷路を書いたテキストを読んでメモリに展開し、
最短経路を見つけて＄文字で埋めて帰すというモノ。
迷路の探索といえば、とにかく壁に当たるまで右か左に進んで、ダメだったら分岐を
一つ一つ引き返して別の道を行くというLISPで書いたら楽しそうなアルゴリズムが
思い付くけど、これだと問題によってはとてつもなく時間がかかって終わらないので、
見当はずれの間違いってことじゃないものの、正解ではないらしい。
自分は優秀じゃないので解けませんでした。
凄い人は３０分から１時間で解いてしまうのね。
というか、アルゴリズムの考え方がしっかりできる人でないと無理ぽ。
いまどきのプログラミングはどうにかして自前コードを書くよりも、既存のAPIと
便利なライブラリを組み合わせて、徹底的に手間をかけずにゴマかす方法を探す
という部分が重視されてるからね。
# 驚くほどたくさんコメントつけてくれてありがとう（汗
# 自分はきちんと理解して返事書けるようなレベルじゃないので何言っていいやら（大汗
# 恥ずかしながら、アルゴリズム本は途中まで読んで挫折した人です。
メモリいくら使ってもいいんですよね？ (スコア:2)
テキストからメモリに読み込む（unsigned int 2次元配列）。壁はオール0xff、空間は0x0、読み込みの際にSの位置を見つけておいて0x1、Gは0xfffffffe。
（メモリが潤沢ならここで0x2を埋めた座標を保存しておいて次のループで使う。メモリが少ないなら毎回2次元配列をフルスキャンして0x2を見つける）
最短経路が2^32-3ステップ未満ならこれでいけると思います。ゴールが見つかったときに打ち切らず、そのステップが終了するまで探索すれば、複数解がある場合も求められます。
Cで30分くらいで書けるんじゃないかな。
Re:メモリいくら使ってもいいんですよね？ (スコア:2)
おおっと。他のコメント読んでいませんでしたが、okkyさんとほぼ同じでしたか。ちなみにこのやり方なら、迷路が長方形であろうとなかろうと（壁で囲まれているなら）使えます。
最短経路より短い経路は全て調べつくし、それより長い経路は調べないので、直感ですが探索量は最小だと予想します。アルゴリズムも単純なので、バグが少なく短時間で組める点もメリットです。
リンク先の「Lv4の2名」も似たような方法で解いたと思いますが、もしこれ以外の方法で解いたのならどんな方法だか興味があります。
Re:メモリいくら使ってもいいんですよね？ (スコア:1)
それは与えられたダンジョンの周囲に、もう一周、番兵(この場合は壁ですね)を別途張ってあげれば解決すると思います。潤沢にメモリを使って良くて、なおかつアドレス空間も腐るほどあると仮定していいなら、これが簡単。
fjの教祖様
最短経路チェックが思いつかないわ (スコア:1)
マップが小さいなら、水平探索を優先して全マス目を「そのマス目への最短到着経路」で埋め尽くして、Gに到着したらそれが最短、という手がある、Sに隣接するマス目を1、1に隣接するマス目を2…って埋めていく。もちろん、壁は数字でうめちゃダメね。この時に、Gの数字が最短ステップ。もちろん、Gが埋まったらそれ以上升目を埋める必要はない。
あとはSからGまでのパスを見つけるのだけれど、その際には「Gから逆に、マス目の数字が1づつ減るように」手繰っていく。複数候補がある場合は、適当に選ぶので構わない。Step0に到着したら、そこがSでなくちゃおかしい。
.
ただし、この方法が使えるには、地図が全部メモリ上に展開できて、なおかつ各マスに対して十分なメモリが割り当てられなくちゃいけない(たとえばステップ数カウントに4byte。仮の経路マークに1bit…は無理なので、alignment を考えてやはり4byte)。なので、一般解じゃない。
正規表現で言う DFA エンジンと同じなので、「一般解」にする場合は NFA エンジン(再帰探索エンジン)とのハイブリッドにしなくちゃいけない。そんなのが25分はもちろん、3時間で組めるわけがない。
なので、個人的な結論は
「これは出題者側のレベルが低すぎて、問題として熟慮されていない」
だと思うな。
fjの教祖様
難しく考えなくていいんじゃないかな (スコア:1)
何しろ、バリテーションが要らないんだから、一般解を求めているわけではないと思ふ。
スタートとゴールの位置が判っているので、理論的な最短距離は算出できるし、探索方向の優先順位もつけられる。
最短経路探索なので、一旦経路が求まればその距離を超えるものは探索時に無視してしまえばよい。
また、外形のサイズ以上の経路は存在しない。
それでも、最悪、全経路を探索することになるかもしれないが、それは問題の性質上、仕方がないことやね。
確かに、こういうアルゴリズムを考えることは、実務だとほとんどないですね。
Re:難しく考えなくていいんじゃないかな (スコア:2)
文書に書かれていないところを考慮しなきゃダメって生活していると、変に勘ぐるような癖が付いちゃうんですかね。
fj.jokes出身:
プログラミング問題と言うよりは (スコア:1)
アルゴリズム知識問題という気がしました。
経路探索系アルゴリズムを知っているかどうかで、
時間内に回答できるかどうかが決まると思います。
# 幅優先探索あたりを知ってれば解けるなぁ、とは思いましたが、
# 世の中にはもっと良いアルゴリズムがあるのかもしれない。
Re:プログラミング問題と言うよりは (スコア:2)
ダイクストラ法 [google.co.jp] ってことかな？
＃さー、ここでコーディングせよ。とか言われたらお手上げだけど。
Re:プログラミング問題と言うよりは (スコア:2)
元記事のコメントにもあるけど、A* [wikipedia.org]をその場で実装しろと言う問題だと思います。
常日頃からアルゴリズムの研鑚をしているかどうかということが重要と言いたいのでしょう。
その場でアルゴリズム考えろって事だとすると、なかなかの難問じゃないでしょうか。
この問題が採用試験として上質かどうかは、対象業務によりけりでしょうけど…
Re: (スコア:0)
幅優先探索でいけないでしょうか？
Pythonで書いてみました。
board=[list(l.rstrip("\n")) for l in sys.stdin]
h, w=len(board), len(board[0])
cache=[[None for _ in xrange(w)] for _ in xrange(h)]
queue=[]
for y in xrange(h) :
for x in xrange(w) :
if board[y][x]=="S" :
bx, by=x, y
矩形壁迷路限定 (スコア:1)
0pass目でマップ全体を読み込んでS,G,壁をマーク。
1pass目で壁が3方向にある通路(行き止まり)をマーク
2pass目で壁が2方向未満の通路(分岐)をマーク
3pass目で、1pass目でマークした位置から2pass目でマークした位置に当たるまでを壁としてマーク。もし、SやGに当たったら経路なし迷路で終了。
1pass目に戻す。
1pass目の結果が0で2pass目が2以下(SとGのみ)なら、通路として残った経路が最短距離。2pass目が3以上なら残った通路に対してSからの距離をマークしていく。
つまりokky氏やTarZ氏のやりかたです。
経路が一つしかない場合や、経路が存在しない場合はこれが最速だと思います。
Re:矩形壁迷路限定 (スコア:2)
通路単位での処理はしていませんので、アルゴリズムとしては異なるのではないでしょうか？
ところで、okky氏やTarZ氏を含め距離を記録するためにメモリを使おうとされていますが、
ダイクストラ法で各マス（文字）をノードとするとリンクの重みがすべて等しくなるので、
実際には処理したノードを「これまで」、「現在」、「次」の三種類に分類してそれぞれに
最短経路方向を記録できればよく、「未処理」、壁と始終端を合わせて16通りで表現できます。
なので、入力イメージを出力用に保持するなら、その空白部分を使うだけでできてしまいます。
この場合、手順としては全ての「現在」について、隣接する「未処理」を「現在」に向いた
「次」としてマークします。これが終わったら全ての「現在」を「これまで」に、全ての
「次」を「現在」に書き換えます。他はokky氏やTarZ氏と同じです。
なお、途中で「現在」と「次」の全探査が必要です。盤面をすべて捜索すると実装は楽ですが、
処理オーダーはノード数の二乗に比例するため他の処理よりも大きくなってしまいます。
元記事の著者がその前の記事でキューやリストの使用について言及していましたが、リスト等で
「現在」と「次」を保持すると、この捜索の処理オーダーをノードに比例する量に削減できます。
もちろんこれはメモリとのトレードオフですが、リストのサイズの最大値はノード数ではなく
盤面の辺長に比例するだけなので、大きさが巨大になる場合には有効です。
本当に問題が巨大で、盤面を圧縮する必要がある場合も、「現在」と「次」をリストに保持すると
ノードは8通りになるので、16通りから1ビット減らせたりします。
ま、3時間の解答時間ではその辺に手をつけることはないでしょうが。