幅優先探索の計算量削減

Question

#問題
ABC007C 幅優先探索

#方針
「Pythonではじめるアルゴリズム入門」（増井敏克著）のコードの書き方に倣い、実装をしました。
障壁部分は9, 未踏部分は0, ゴール部分は1, 既踏部分は2で更新するとします。

#コード

from collections import deque

R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

maze = []
for _ in range(R):
    li = list(str(input()))
    li = [9 if el == '#' else 0 for el in li]
    maze.append(li)

maze[gy - 1][gx - 1] = 1

data = deque([[sy - 1, sx - 1, 0]])
while data[0]:
    x, y, d = data.popleft()

    if maze[x][y] == 1:
        print(d)
        break

    maze[x][y] = 2

    if maze[x - 1][y] < 2:
        data.append([x - 1, y, d + 1])
    if maze[x + 1][y] < 2:
        data.append([x + 1, y, d + 1])
    if maze[x][y - 1] < 2:
        data.append([x, y - 1, d + 1])
    if maze[x][y + 1] < 2:
        data.append([x, y + 1, d + 1])

#質問
上のコードを提出すると、半分程度のテストケースで実行時間(2s)超過がおきました。
問題の制約は 1 <= R, C <= 50 程度なので、計算量も高が知れていると考えましたが、上のコードだとどのような箇所が計算時間を長くさせているのでしょうか。元の本のコードではdataの管理にリストを用いていましたが、dequeによる管理に切り替えてもさほど芳しい結果は得られませんでした。またサンプルとなる正解コードを複数見ても、アプローチが非常に多種多様で、自分のコードにおける問題点がはっきり見えませんでした。幅優先探索に関する学習を始めて日が浅いため、やや丸投げのような形にはなってしまいましたが、どのような部分に着眼すれば良いかといったヒントだけでも頂けますと幸いです。素人質問にて恐縮ですが、お力添え頂ける箇所がございましたら、ご教授のほど何卒よろしくお願い申し上げます。

Answer 1

この実装だと，あるマスが探索リスト（queue）に複数回登録され得るのでは．

例えば，

S A
B C

というマップがあって，Sから処理が始まるとき，

• Sの隣接マス A と B をリストに追加．
• リストからAを取り出し，Cをリストに追加
• リストからBを取り出し，Cをリストに追加←ここでCがダブる

あるマスが
「リストから取り出された」ことはマークされているが，
「リストに追加された」ことは把握されていないと見えるので，
多重登録され，多重の探索が行われるように思える．

Comments

[kay_ventris4]

ご回答ありがとうございます。
探索ノードを別途辞書で管理し、一度見たものであればもう探索不要としたところ大幅に計算量を削減してACすることが出来ました。

[fana]

> maze[x][y] = 2

この，2という値でマークする処理を，
「リストから取り出された」際に行うのではなくて，
「リストに追加する」際に行うようにすればどうでしょう？

[kay_ventris4]

if maze[x - 1][y] < 2:
　　data.append([x - 1, y, d + 1])
　　maze[x][y] = 2
...
とするということですか？（おそらく意図が汲みきれていません。申し訳ございません。）

[fana]

if maze[x - 1][y] < 2:
　　data.append([x - 1, y, d + 1])
　　maze[x-1][y] = 2　　←ココ

かな．
2という値でマークする処理の目的と言うのは
「各マスを２回以上探索しない」ことであり，そのためには「各マスはリストに１度しか登録されない」形とすれば良いのではなかろうか，と．

[fana]

（スタート地点もループに入る前に2にマークしておくことを忘れずに）

[fana]

質問文のコードだと，maze[x][y]の値が2というのは
「もうこのマス(x,y)は調べました」という意味だけど，
これを
「もうこのマス(x,y)は探索リストに追加されました」という意味に変える．

[kay_ventris4]

仰ることは理解致しましたが、maze[sy - 1][sx - 1] = 2 として、さらに
if maze[x - 1][y] < 2:
　　data.append([x - 1, y, d + 1])
　　maze[x - 1][y] = 2
if maze[x + 1][y] < 2:
　　data.append([x + 1, y, d + 1])
　　maze[x + 1][y] = 2
if maze[x][y - 1] < 2:
　　data.append([x, y - 1, d + 1])
　　maze[x][y - 1] = 2
if maze[x][y + 1] < 2:
　　data.append([x, y + 1, d + 1])
　　maze[x][y + 1] = 2
としたところ、答えが何も出力されないということが発生しましたので、x, y, d = data.popleft()下のprint(d)部分を削除し、代わりにans = []を準備しans.append(d)として最後にprint(ans[-1])として対応したところ、半数程度のケースでWAとなりました。

[fana]

ああ，ごめん．
mazeを2にした際にゴールの1を上書きして消してしまうわけだ．
ゴール判定を maze[x][y] == 1 じゃなくて，「座標(x,y)がゴール座標か？」という座標値での判定にすれば良いかと．

[kay_ventris4]

うまく行きました。
最後までご丁寧にありがとうございました。

Answer 2

単純に以下の判定を追加するだけでよいように思います。

while data[0]:
    x, y, d = data.popleft()

    if maze[x][y] == 1:
        print(d)
        break

    # 探索済み（や壁）はそれ以上の探索は不要
    if maze[x][y] >= 2:
        continue

    maze[x][y] = 2

Comments

[kay_ventris4]

なるほど、踏破したところは最初から処理しないということですね。こちらは実装も非常でシンプルで自己解決方法よりもさらに高速に処理することが出来ました。ありがとうございました。

Answer 3

解答を頂いたお二方のアプローチをそれぞれ以下に示しておきます：

解法①

from collections import deque

R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

maze = []
for _ in range(R):
    li = list(str(input()))
    li = [9 if el == '#' else 0 for el in li]
    maze.append(li)

maze[gy - 1][gx - 1] = 1

dic = {}
for i in range(R - 1):
    for j in range(C - 1):
        dic[i, j] = 0

data = deque([[sy - 1, sx - 1, 0]])
while data[0]:
    x, y, d = data.popleft()

    if maze[x][y] == 1:
        print(d)
        break
    maze[x][y] = 2

    if maze[x - 1][y] < 2:
        if dic[x - 1, y] < 1:
            data.append([x - 1, y, d + 1])
            dic[x - 1, y] += 1
    if maze[x + 1][y] < 2:
        if dic[x + 1, y] < 1:
            data.append([x + 1, y, d + 1])
            dic[x + 1, y] += 1
    if maze[x][y - 1] < 2:
        if dic[x, y - 1] < 1:
            data.append([x, y - 1, d + 1])
            dic[x, y - 1] += 1
    if maze[x][y + 1] < 2:
        if dic[x, y + 1] < 1:
            data.append([x, y + 1, d + 1])
            dic[x, y + 1] += 1

解法②

from collections import deque

R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

maze = []
for _ in range(R):
    li = list(str(input()))
    li = [9 if el == '#' else 0 for el in li]
    maze.append(li)

maze[sy - 1][sx - 1] = 2
maze[gy - 1][gx - 1] = 1

data = deque([[sy - 1, sx - 1, 0]])
while data[0]:
    x, y, d = data.popleft()

    if x == gy - 1 and y == gx - 1:
        print(d)
        break

    if maze[x - 1][y] < 2:
        data.append([x - 1, y, d + 1])
        maze[x - 1][y] = 2
    if maze[x + 1][y] < 2:
        data.append([x + 1, y, d + 1])
        maze[x + 1][y] = 2
    if maze[x][y - 1] < 2:
        data.append([x, y - 1, d + 1])
        maze[x][y - 1] = 2
    if maze[x][y + 1] < 2:
        data.append([x, y + 1, d + 1])
        maze[x][y + 1] = 2

解法③

from collections import deque

R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

maze = []
for _ in range(R):
    li = list(str(input()))
    li = [9 if el == '#' else 0 for el in li]
    maze.append(li)

maze[gy - 1][gx - 1] = 1

data = deque([[sy - 1, sx - 1, 0]])
while data[0]:
    x, y, d = data.popleft()

    if maze[x][y] == 1:
        print(d)
        exit()

    if maze[x][y] >= 2:
        continue

    maze[x][y] = 2

    if maze[x - 1][y] < 2:
        data.append([x - 1, y, d + 1])
    if maze[x + 1][y] < 2:
        data.append([x + 1, y, d + 1])
    if maze[x][y - 1] < 2:
        data.append([x, y - 1, d + 1])
    if maze[x][y + 1] < 2:
        data.append([x, y + 1, d + 1])