01-BFSとぶつかり稽古

(前回の記事↓の続きです)

politeness.hatenadiary.com

上に貼った記事の中で1つ、挑戦しようとしたが「難しくね？」と思い直し一旦保留にしていた問題があった。

それがABC176-D問題である。問題自体は後ほど掲載するとして、この問題ではBFS(幅優先探索)の中でも"01-BFS"と呼ばれる手法が用いられるらしい。まずは01-BFSについて勉強していこう。

なお、この記事を書く上で下の記事を大いに参考にした。ありがたいですわね。
betrue12.hateblo.jp

01-BFSの動作

BFSはグラフにおける各辺の長さが1である(または全て等しい)場合の始点から各頂点への最短路長を求めるアルゴリズムであったが、01-BFSというのは各辺の長さが0または1である場合の最短路長を求めるためのアルゴリズムである。

01-BFSのアルゴリズムの概要は以下の通りである。

まず始点を両端キュー*1に格納する。

キューから先頭の要素 $v$ を取り出す。

$v$ の隣接点の中で訪問済みでない点(最短路長が確定していない点)に対し、暫定最短距離を更新できる頂点がある場合更新して

　-その点に入るときに0の辺を用いた場合はその点を両端キューの先頭に加える。

　-その点に入るときに1の辺を用いた場合はその点を両端キューの末尾に加える。

2,3を繰り返し、キューが空になった段階で終了。

BFS同様言葉だけじゃ難しいので、頑張って一例を絵に描いてみました。

オレンジ色が訪問予定、赤色が訪問済みの点であることを表している。また、頂点の上に書いてある赤い数字が暫定最短距離である。
通常のキューと違い先頭にも末尾にも要素が追加されうる点に注意されたい。
（9/6 追記：7枚目のキューの末尾、6でなくて5です。）

このアルゴリズムで、なぜ正しく各点への最短路長が求まるのかを考えていく。

01-BFSのアルゴリズムが機能するワケ

そもそもBFSがなぜ上手く機能していたかを考えよう。

BFSではキューの先頭から要素を1つずつ取り出してその点への最短路を確定させていった。
キューの先頭の要素は常にキューの中で暫定最短距離が最小である点であり、各辺の長さが1(>0)であることから、その長さがその点への最短距離として確定するという仕組みである。

またBFSの特徴として、キューの中の先頭と末尾の要素の暫定最短距離の差が最大で1であるという事がある。
各辺の長さが1であることからキュー(の末尾)に追加される点の暫定最短距離は常にキューの先頭から取り出された点の(暫定)最短距離 $+1$ であるからである。

以下ではこの、先頭に最小要素があり、最大要素と最小要素の差が1以下であるという状態を「理想的な状態」と呼ぶことにする。
わかりやすいように以下に理想的な状態にあるキューの例を出しておこう。(各点の暫定最短距離を表示)

[1,1,1,2,2]
[3,3,4]
[100,100,100.100]　等々...

BFSが上手く機能していた理由をまとめると、BFSのアルゴリズムではキューが理想的な状態に保たれ、暫定最短距離が最も小さい頂点を選んで、そこから伸びる辺で他の頂点の暫定最短距離を更新するということの繰り返しが可能となっていたからだった。

実は各辺の長さが0または1である場合での、キューの中身を(上で挙げた例と同じような)理想的な状態に保ったまま探索をする方法が01-BFSなのである。

01-BFSがBFSと異なる点に、辺の長さによってキューにその点を加える位置が変わるという点があるが、それも理想的な状態を保つための工夫である。

新たにキューに加える点が、最短路長が確定しキューから取り出した点(以降、「最小点」と呼ぶ)と長さ0の辺で結ばれている時を考える。
この時、新たに加える点の暫定最短路長は最小点の最短路長と等しいため、その点はキューの中で最も暫定最短路長が短い点となる。
そのような点はキューの先頭にあるべきであるため、01-BFSのアルゴリズムでは先頭に追加している。

次に新たにキューに加える点が、最小点と長さ0の辺で結ばれている時を考える。
この時、新たに加える点の暫定最短路長は最小点の最短路長 $+1$ となるが、キューの内部の暫定最短距離の差が最大で1であることから、この点はキューの中で最も暫定最短路長が長い点となる。
そのような点はキューの末尾にあるべきであるため、01-BFSのアルゴリズムでは末尾に追加している。

よって01-BFSもBFS同様キューを理想的な状態に保つアルゴリズムとなっているため、正しく最短路長を求めることができるのだ。

あれ？

そういえば、01-BFSはキューの中の点の暫定最短距離が更新されることがあるという点でも通常のBFSとは異なるのであった。

更新されることでキューの中の順番がおかしくなる(つまり暫定最短距離の小さい順にキューに格納されていない状態になる)ことがあるのではないか、という疑問が浮かんでくる。この点はどうなっているのだろう。

実際のところ、こういう場合はある。以下の例を見てもらいたい。

図を見ると、キューの中に同じ頂点が複数個格納されているタイミングがあることがわかるだろう。

01-BFSのアルゴリズムに従うと、暫定最短距離を更新した点は再びキューに追加されるため、このようなことが起こる。

それに付随して、先ほど疑った通り、キューの中の暫定最短距離の順番がめちゃくちゃになっている。理想的な状態でもなんでもないように見える。

しかし、キューの中に複数回現れる点を2回目以降キューから取り出す時に起こる変化を考えると、"無"であることは少し考えればわかる。
その点を1回目に取り出した段階で、その点の最短路長は確定し、さらに近傍の点の暫定最短路長も更新済みであるからだ。

よって、キューに複数個含まれている点の2個目以降の点がキューに含まれていても含まれていなくても、実はアルゴリズム全体としては同じ動作をする。
その考えのもとキューの中の複数個の同じ点を(先頭の)1つに集約して考えてみると、キューは確かに理想的な状態を保持していると言える。

以上より01-BFSの正当性は(なんとなく)確かめられた。以下で実装を行ってみよう。

01-BFSの実装

以下が01-BFSをPython3で実装したコードとなる。入力は以下の形式を想定している。

$\begin{align*} &N\quad M\\ &a_0\quad b_0\quad c_0\\ &a_1\quad b_1\quad b_1\\ &\cdots \quad \cdots \quad \cdots\\ &a_{M-1}\quad b_{M-1} \quad c_{M-1}\\ \end{align*}$

グラフは無向グラフで、 $N$ はグラフの頂点数、 $M$ はグラフの辺数、各辺 $i=0,1,\ldots ,M-1$ が頂点 $a_i$ と $b_i$ をつないでいる長さ $c_i$ の辺であることを表している。

from collections import deque

N, M = map(int, input().split())
G = [[] for i in range(N)] #グラフを隣接リストで表現。G[i]には(iから向かう点、その辺の長さ)を格納していく。

for i in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c)) #aからbに入る長さcの有向辺が存在
    G[b].append((a,c)) #bからaに入る長さcの有向辺が存在

def BFS01(s): #sから各点への最短路長を01-BFSで求める関数
    dist=[float('inf')] * N
    dist[s] = 0
    queue = deque([s])

    while queue:
        v = queue.popleft()
        for u, c in G[v]:
            d = dist[v] + c
            if d < dist[u]:
                dist[u] = d
                if c == 1:
                    queue.append(u)
                else:
                    queue.appendleft(u)
    return dist

dist=BFS01(0) #点0から各頂点への最短路
print(dist) #最短路のリストが出力される。到達不可能点の場合、最短路はinfとなる。

いざ実装してみるとBFSのコードに2,3行足しただけのコードが出来上がった。

僕が今まで書いてきた5000字は...徒労...?

千秋楽

いよいよ初めに述べていた問題の解決をしよう。それは以下の問題であった。

Wizard in Maze

縦 $H$ マス、横 $W$ マスの $H\times W$ マスからなる迷路があります。

上から $i$ 行目、左から $j$ 列目のマス $(i,j)$ は、 $S_{ij}$ が'#'のとき壁であり、'.'のとき道です。

マス $(C_h,C_w)$ に魔法使いがいます。魔法使いは次の2種類の方法で移動することができます。

移動A：現在いるマスと上下左右に隣接する道のマスへ歩いて移動する。
移動B：現在いるマスを中心とする $5\times 5$ の範囲内にある道へのマスへワープ魔法で移動する。

どちらの行動でも、迷路の外へ移動することはできません。

マス $(D_h,D_w)$ まで移動するには、ワープ魔法を最低で何度使う必要があるでしょうか。

噂によると、迷路問題の中でも特に

ノーコストの手段で移動する

何らかのコストや回数制限のある手段で移動する

の2通りの移動方法が与えられているような問題は、01-BFSに帰着できることが多いそうだ。

この問題も01-BFSに帰着させて、以下のコードで解ける。

from collections import deque
 
#入力受け取り
H,W=map(int,input().split())
Ch,Cw=[int(x)-1 for x in input().split()]
Dh,Dw=[int(x)-1 for x in input().split()]
maze=[input() for i in range(H)]
 
dirs=[-2,-1,0,1,2] #ワープ移動できる縦横の範囲

#初期化
dist=[[float('inf')]*W for _ in range(H)] #distには各点への到達コストを格納
dist[Ch][Cw]=0
queue=deque()
queue.append((0,Ch,Cw)) #キューには(コスト、x座標、y座標)を追加していく
arrive=False #ゴールに到着すればTrueに変更

while queue:
    k,i,j=queue.popleft()
    if k>dist[i][j]:
        continue
    if i==Dh and j==Dw:
        arrive=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0: #その場から移動しない時
                continue
            ni,nj=i+di,j+dj #移動後の座標(ni,nj)
            if not (0<=ni<H and 0<=nj<W):
                continue
            if maze[ni][nj]=='#': #移動先が壁の中
                continue
            if k<dist[ni][nj]: 
                if abs(di)+abs(dj)==1: #歩行圏内(コスト:0)
                    nk=k
                    dist[ni][nj]=nk
                    queue.appendleft((nk,ni,nj))
                else: #歩行圏外(コスト:1)
                    nk=k+1
                    dist[ni][nj]=nk
                    queue.append((nk,ni,nj))   
if arrive:
    ans=dist[Dh][Dw]
else:
    ans=-1
print(ans)

今回の問題は各マスから上下左右の4マスに長さ0の辺が伸びていて、その外かつ $5\times 5$ マス内にあるマスに長さ1の辺が伸びているようなグラフに対して01-BFSを行う問題と解釈できる。

更新先の座標が歩行圏内にある場合はコスト0であるからキューの先頭に、更新先の座標が歩行圏外にある場合はコスト1であるからキューの末尾に要素を追加している。これは01-BFSの基本操作であった。

このように01-BFSを素直に実装することでこの問題の解答を得ることができた。

以上で01-BFSの概要の学習と基本的・応用的な実装を終える。

また秋場所で会いましょうや。

*1:データ構造の一つ。先頭または末尾で要素を追加・削除できる機能を持つ。

naruの日記

いい記事を書きます。あと、日記ではないです。

01-BFSとぶつかり稽古

01-BFSの動作

01-BFSのアルゴリズムが機能するワケ

あれ？

01-BFSの実装

千秋楽