• このエントリーをはてなブックマークに追加

以下の参考書を元に、TopCoderの対策をしています。

今日は、深さ優先探索と、幅優先探索について勉強しました。

スポンサードリンク

深さ優先探索(DFS)

なるべく左に深い点から探索するアルゴリズム.

実装方法

実装では再帰関数を用いる. ここでは、答えを最大化する深さ優先探索の例.

def dfs(now):
    if "nowが終了条件":
        return "nowの答え"

    ret = -1
    for i in range("次の状態の個数"):
        next = "i番目の次の状態"
        if "nextが条件を満たしている":
            ret = max(dfs(next), ret)
    return ret

SRM 425 Div2 500

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class CrazyBot:
    def __init__(self):
        self.grid = [[False for i in range(100)] for j in range(100)]
        self.vx = [1, -1, 0, 0]
        self.vy = [0, 0, 1, -1]
        self.prob = [0.0, 0.0, 0.0, 0.0]

    def dfs(self, x, y, n):
        # 一度通った場所は確率0
        if self.grid[x][y]:
            return 0
        if n == 0:
            return 1

        # 通った場所にフラグを立てる
        self.grid[x][y] = True
        ret = 0.0

        for i in range(4):
            ret += self.dfs(x + self.vx[i],
                            y + self.vy[i],  n - 1) * self.prob[i]

        self.grid[x][y] = False
        return ret

    def getProbability(self, n, east, west, south, north):
        self.prob[0] = east / 100.0
        self.prob[1] = west / 100.0
        self.prob[2] = south / 100.0
        self.prob[3] = north / 100.0

        return self.dfs(50, 50, n)

幅優先探索(BFS)

深さの浅い、左側の点から順に探索するアルゴリズム.

実装方法

実装ではQueueを用いる.

1. 根ノードを空のキューに加える。
2. ノードをキューの先頭から取り出し、以下の処理を行う。
     ノードが探索対象であれば、探索をやめ結果を返す。
     そうでない場合、ノードの子で未探索のものを全てキューに追加する。
3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ"not found"と結果を返す。2に戻る。
queue = []
queue.append("初期状態")
while len(queue) > 0:
    # 取り出し
    now = queue[0]
    del queue[0]
    # now に対しての処理
    for i in range("次の状態の個数"):
        next = "i番目の次の状態"
        if "nextが訪問済みであるかどうかの判定":
            queue.append(next)

SRM 453.5 Div2 500

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class MazeMaker:
def longestPath(self, maze, startRow, startCol, moveRow, moveCol):
width = len(maze[0])
height = len(maze)
board = []

# ボードの初期化
for i in range(height):
list = []
for j in range(width):
list.append(-1)
board.append(list)

# スタート地点のマーク
board[startRow][startCol] = 0

# キューの宣言
queueX = []
queueY = []
queueX.append(startCol)
queueY.append(startRow)

# キューが空になるまで、一つずつ取り出す
while len(queueX) > 0:
x = queueX[0]
y = queueY[0]
del queueX[0]
del queueY[0]

for i in range(len(moveRow)):
nextX = x + moveCol[i]
nextY = y + moveRow[i]

if 0 <= nextX and nextX < width \ and 0 <= nextY and nextY < height \ and board[nextY][nextX] == -1 \ and maze[nextY][nextX] == ".": # ボードに移動量を更新する board[nextY][nextX] = board[y][x] + 1 # 末尾に次の移動点を挿入 queueX.append(nextX) queueY.append(nextY) # 最大移動量の計算 ret = 0 for i in range(height): for j in range(width): # 移動できない点があったら、-1を返す if maze[i][j] == "." and board[i][j] == -1: return -1 ret = max(ret, board[i][j]) return ret [/sourcecode]

DFSとBFSの比較

  • 全通りを列挙し、をまとめる必要がある場合は DFS
  • 始点からもっとも近いものを求めたいときは、BFS