アルゴリズムを解く４

n*mのマスの迷路

• 障害物、外壁を通ることができない
• 隣接し、障害物、外壁のないマスは移動できる
• 迷路の解はこの移動の繰り返しで視点から終点にたどり着くまでのマスの並び
• 迷路の解は同じマスを二回以上通ることができない
• 始点と終点は異なるますに指定されている

迷路の解を見つける探索

• 迷路と外壁の各マスの位置をx,yの座標で表す
• マスに関する情報をマス情報と考える
• 障害物と外壁はNGフラグ、それ以外のマス情報はOKフラグで表す
• マス情報全体を迷路図情報という

移動には進む、戻る、訪問がある。

進むとは？

• 進むとはy,xの座標を１増減する方向に動くこと
• マスに進むと同時に足跡フラグを入れる
• 足跡フラグの入ったマスには進むことはできない

戻るとは?

• 戻るは進んできた一つ前のマスに動く

訪問とは?

• マスに移動した時、移動先のマスを訪問したという

探索の手順

• 始点のマスのマス情報に足跡フラグを入れて探索開始する

探索における進むの繰り返し処理

以下の処理を繰り返し迷路の解の一つとなる

• 試みた方向のマスに進むことができなければ他の方向に進むことを試みる
• 四方向いずれも進めない場合、今いるマスを足跡フラグからOKフラグに変更し、戻る

迷路の解を見つけた後も探索する迷路の終点から一つ前のマスに戻り、迷路の探索を行う。
全ての探索が終われば終了

探索中のデータの格納

• 迷路の探索している間それまでの経路をスタックに格納

迷路の解を全て求めて表示するプログラム

迷路を探索してマスを移動する関数visit

function visit(x,y)
    maze[x][y] ← VISITED # VISITED:足跡フラグを任意の座標に入れる
    stack_visit[stack_top] ← (x,y) # たどってきた経過の座標を格納するスタックに任意の座標を格納
    if(xがgoal_xと等しいかつyがgoal_yと等しい) # 任意の座標がゴールの座標と等しいならば
        for(kを0からstack_topまで1ずつ増やす) # stack_topはスタックの一番上を表す
            <イ> ← stack_visit[k] # ゴールまでの経過の座標のスタックを格納する
        endfor
        sol_num ← sol_num + 1 # 格納処理終了時、加算処理が行われる
    else # ゴールでなければ
        stack_top ← stack_top+1 # 1足されスタックの一番上が更新される
        if(maze[x][y+1]がOKと等しい) # y軸に進む
            visit(x,y+1)
        endif
        if(maze[x+1][y]がOKと等しい) # x軸に進む
            visit(x+1,y)
        endif
        if(maze[x][y-1]がOKと等しい) # y軸に戻る
            visit(x,y-1)
        endif
        if(maze[x-1][y]がOKと等しい) # x軸に戻る
            visit(x-1,y)
        endif
        stack_top ← <ウ> # 移動処理、終了時
    endif
    <エ> ← OK
endfunction

<イ> ← stack_visit[k]

終点に到着したとき、始点から終点まで"進む”ことでたどってきたマスの並びが迷路の解の一つとなる。

<イ> ← stack_visit[k]は解の一つをpaths[u][v]に格納する処理と考える。
2次元配列は左から右へ格納され上から下に格納されると思った。
v:kは左から右格納する添字にする。
u:sol_num ← sol_num + 1が格納処理終了時に加算されるので上から下へ格納する変数に使うと考える。

paths[sol_num][k]と考える

stack_top ← <ウ>

stack_top ← stack_top -1と考える。
この関数は進むことができなくなるまで探索するため
ここは具体的に考えることができなかった。

<エ> ← OK

現在いるマスのマス情報をOKフラグに戻し

と書いてある

maze[x][y]にOKを格納すると考える
現在いた座標にOKとするのでmaze[x][y]だと考える

メインプログラム

function main
    stack_top ← 0
    sol_num ← 0
    maze[x][y]に迷路図情報を設定する
    start_x, start_y, goal_x, goal_yに始点と終点の座標を設定する
    visit(start_x, start_y)
    if(<オ>が0と等しい)
        ”迷路の解が見つからなかった”と印字する
    else 
        paths[][]を順に全て印字する
    endif
endfunction

if(<オ>が0と等しい)

もう一つ下の行に”迷路の解が見つからなかった”と印字すると書いてある。
迷路の解に関係するものはpath[u][v]、sol_numだと考える。
path[u][v]は2次元配列、sol_numは数字だ。
sol_num

解が複数ある迷路

図２が解が複数ある迷路の例で、一つ目の解が見つからなかった後に、他の解を見つけるために、迷路を続ける。一つ目の解が見つかった後で、最初に実行される関数visitの引数の値は<カ>である。この引数の座標を基点として二つ目の解が見つかるまでに、マスの"移動"は<キ>回起き、その間に座標が(4､2)のマスは<ク>回”訪問”される

一つ目の解が見つかった後で、最初に実行される関数visitの引数の値は<カ>である。

一つ目の解が見つかった後のvisit()処理を知ることができれば解けそう。

迷路の解を見つけた後も、他の解を見つけるために、終点から一つ前のマスに"戻り"

と書いあり、図２の終点の一番手前のマスが(5,4)だけなので
visit(5,4)

間違えた。
迷路の解を見つけた後、処理が終了、次は壁で終了、３つ目の下移動のvisit()が始まるので
visit(5,3)

二つ目の解が見つかるまでに、マスの"移動"は<キ>回起き

25回

間違えた。
真剣にトレースできれば正解できた。

関数visitの引数の値は<カ>である。この引数の座標を基点として...

と書いてあったのを見落としていた。
22回だった

その間に座標が(4､2)のマスは<ク>回”訪問”

三回

図１の例で終点に到達した時に、この訪問されなかったますの総数を、障害物と外壁のマスをのぞきこたえよ

7マス

スタックには<ア>個の座標を格納されている。

9

上２問間違えた
図２を見ていた。

• 見間違えには注意する

感想

設問２が正解してた
前回までと比べて解く速度は速い気がする。
問題が簡単なのだろう。