パスワードを忘れた? アカウント作成
182676 journal

cyber205の日記: 某社の採用試験は迷路の最短経路探索プログラム 12

日記 by cyber205

人材獲得作戦・4 試験問題ほか
う~む。

AAで問題となる迷路を書いたテキストを読んでメモリに展開し、
最短経路を見つけて$文字で埋めて帰すというモノ。
迷路の探索といえば、とにかく壁に当たるまで右か左に進んで、ダメだったら分岐を
一つ一つ引き返して別の道を行くというLISPで書いたら楽しそうなアルゴリズムが
思い付くけど、これだと問題によってはとてつもなく時間がかかって終わらないので、
見当はずれの間違いってことじゃないものの、正解ではないらしい。

自分は優秀じゃないので解けませんでした。
凄い人は30分から1時間で解いてしまうのね。

というか、アルゴリズムの考え方がしっかりできる人でないと無理ぽ。
いまどきのプログラミングはどうにかして自前コードを書くよりも、既存のAPIと
便利なライブラリを組み合わせて、徹底的に手間をかけずにゴマかす方法を探す
という部分が重視されてるからね。

# 驚くほどたくさんコメントつけてくれてありがとう(汗
# 自分はきちんと理解して返事書けるようなレベルじゃないので何言っていいやら(大汗
# 恥ずかしながら、アルゴリズム本は途中まで読んで挫折した人です。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
    1. 準備
      テキストからメモリに読み込む(unsigned int 2次元配列)。壁はオール0xff、空間は0x0、読み込みの際にSの位置を見つけておいて0x1、Gは0xfffffffe。
    2. ループ
      1. 0x1の周囲の空間0x0を0x2で埋める。
        (メモリが潤沢ならここで0x2を埋めた座標を保存しておいて次のループで使う。メモリが少ないなら毎回2次元配列をフルスキャンして0x2を見つける)
      2. 0x2の周囲0x0を0x3で埋める。
      3. 数字を大きくしながら、1-2を繰り返す。数字が0xfffffffdになったら探索失敗。
      4. 埋める過程でG(0xfffffffe)が見つかれば探索終了。ゴール周囲の 0x4 -> 0x3 -> 0x2 を順に辿って 0x1まで 0xfffffffdで埋める。同じ数字が複数あるなら複数解があるので、そのうち1つをチョイスする(どれでもよい。どのルートも0x1に繋がっている)。
    3. 壁、空間、0xfffffffdを$に置き換えて2次元配列をテキスト出力。

     最短経路が2^32-3ステップ未満ならこれでいけると思います。ゴールが見つかったときに打ち切らず、そのステップが終了するまで探索すれば、複数解がある場合も求められます。

     Cで30分くらいで書けるんじゃないかな。

    •  おおっと。他のコメント読んでいませんでしたが、okkyさんとほぼ同じでしたか。ちなみにこのやり方なら、迷路が長方形であろうとなかろうと(壁で囲まれているなら)使えます。

       最短経路より短い経路は全て調べつくし、それより長い経路は調べないので、直感ですが探索量は最小だと予想します。アルゴリズムも単純なので、バグが少なく短時間で組める点もメリットです。
       リンク先の「Lv4の2名」も似たような方法で解いたと思いますが、もしこれ以外の方法で解いたのならどんな方法だか興味があります。

      親コメント
  • 迷路の探索といえば、とにかく壁に当たるまで右か左に進んで、ダメだったら分岐を
    一つ一つ引き返して別の道を行くというLISPで書いたら楽しそうなアルゴリズムが
    思い付くけど、これだと問題によってはとてつもなく時間がかかって終わらないので、
    見当はずれの間違いってことじゃないものの、正解ではないらしい。

    マップが小さいなら、水平探索を優先して全マス目を「そのマス目への最短到着経路」で埋め尽くして、Gに到着したらそれが最短、という手がある、Sに隣接するマス目を1、1に隣接するマス目を2…って埋めていく。もちろん、壁は数字でうめちゃダメね。この時に、Gの数字が最短ステップ。もちろん、Gが埋まったらそれ以上升目を埋める必要はない。

    あとはSからGまでのパスを見つけるのだけれど、その際には「Gから逆に、マス目の数字が1づつ減るように」手繰っていく。複数候補がある場合は、適当に選ぶので構わない。Step0に到着したら、そこがSでなくちゃおかしい。

    .

    ただし、この方法が使えるには、地図が全部メモリ上に展開できて、なおかつ各マスに対して十分なメモリが割り当てられなくちゃいけない(たとえばステップ数カウントに4byte。仮の経路マークに1bit…は無理なので、alignment を考えてやはり4byte)。なので、一般解じゃない。

    正規表現で言う DFA エンジンと同じなので、「一般解」にする場合は NFA エンジン(再帰探索エンジン)とのハイブリッドにしなくちゃいけない。そんなのが25分はもちろん、3時間で組めるわけがない。

    なので、個人的な結論は
    「これは出題者側のレベルが低すぎて、問題として熟慮されていない」
    だと思うな。

    --
    fjの教祖様
  • 難しく考えなくていいんじゃないかな、というのが感想。
    何しろ、バリテーションが要らないんだから、一般解を求めているわけではないと思ふ。
    スタートとゴールの位置が判っているので、理論的な最短距離は算出できるし、探索方向の優先順位もつけられる。
    最短経路探索なので、一旦経路が求まればその距離を超えるものは探索時に無視してしまえばよい。
    また、外形のサイズ以上の経路は存在しない。
    それでも、最悪、全経路を探索することになるかもしれないが、それは問題の性質上、仕方がないことやね。

    確かに、こういうアルゴリズムを考えることは、実務だとほとんどないですね。
    • 昨夜、「壁とスペースで構成された迷路」ってところに、閉領域かどうかとか解の存在とかを考慮しなきゃならないのかとか、その辺を問い合わせられないとコミュニケーション力不足とかなるんじゃないかとか変なところで悩んで寝落ちしました。
      文書に書かれていないところを考慮しなきゃダメって生活していると、変に勘ぐるような癖が付いちゃうんですかね。
      --
      fj.jokes出身:
      親コメント
  • アルゴリズム知識問題という気がしました。
    経路探索系アルゴリズムを知っているかどうかで、
    時間内に回答できるかどうかが決まると思います。

    # 幅優先探索あたりを知ってれば解けるなぁ、とは思いましたが、
    # 世の中にはもっと良いアルゴリズムがあるのかもしれない。

    • ダイクストラ法 [google.co.jp] ってことかな?

      #さー、ここでコーディングせよ。とか言われたらお手上げだけど。

      親コメント
    • by Anonymous Coward
      ダイクストラとかA*とかまでいかなくても
      幅優先探索でいけないでしょうか?
      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
                 
  • by nodocuments (12199) on 2010年01月12日 12時02分 (#1701218) 日記

    0pass目でマップ全体を読み込んでS,G,壁をマーク。
    1pass目で壁が3方向にある通路(行き止まり)をマーク
    2pass目で壁が2方向未満の通路(分岐)をマーク
    3pass目で、1pass目でマークした位置から2pass目でマークした位置に当たるまでを壁としてマーク。もし、SやGに当たったら経路なし迷路で終了。
    1pass目に戻す。
    1pass目の結果が0で2pass目が2以下(SとGのみ)なら、通路として残った経路が最短距離。2pass目が3以上なら残った通路に対してSからの距離をマークしていく。
    つまりokky氏やTarZ氏のやりかたです。

    経路が一つしかない場合や、経路が存在しない場合はこれが最速だと思います。

    • by GeoJ (32542) on 2010年01月12日 20時13分 (#1701568) 日記
      okky氏やTarZ氏の方法は各マス(文字)をノードとした時のダイクストラ法です。
      通路単位での処理はしていませんので、アルゴリズムとしては異なるのではないでしょうか?

      ところで、okky氏やTarZ氏を含め距離を記録するためにメモリを使おうとされていますが、
      ダイクストラ法で各マス(文字)をノードとするとリンクの重みがすべて等しくなるので、
      実際には処理したノードを「これまで」、「現在」、「次」の三種類に分類してそれぞれに
      最短経路方向を記録できればよく、「未処理」、壁と始終端を合わせて16通りで表現できます。
      なので、入力イメージを出力用に保持するなら、その空白部分を使うだけでできてしまいます。

      この場合、手順としては全ての「現在」について、隣接する「未処理」を「現在」に向いた
      「次」としてマークします。これが終わったら全ての「現在」を「これまで」に、全ての
      「次」を「現在」に書き換えます。他はokky氏やTarZ氏と同じです。

      なお、途中で「現在」と「次」の全探査が必要です。盤面をすべて捜索すると実装は楽ですが、
      処理オーダーはノード数の二乗に比例するため他の処理よりも大きくなってしまいます。
      元記事の著者がその前の記事でキューやリストの使用について言及していましたが、リスト等で
      「現在」と「次」を保持すると、この捜索の処理オーダーをノードに比例する量に削減できます。
      もちろんこれはメモリとのトレードオフですが、リストのサイズの最大値はノード数ではなく
      盤面の辺長に比例するだけなので、大きさが巨大になる場合には有効です。
      本当に問題が巨大で、盤面を圧縮する必要がある場合も、「現在」と「次」をリストに保持すると
      ノードは8通りになるので、16通りから1ビット減らせたりします。
      ま、3時間の解答時間ではその辺に手をつけることはないでしょうが。
      親コメント
typodupeerror

あと、僕は馬鹿なことをするのは嫌いですよ (わざとやるとき以外は)。-- Larry Wall

読み込み中...