08 Dec 2015, 12:26

TopCoderで深さ優先探索と幅優先探索の問題を解いてみる(Python)

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

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

深さ優先探索(DFS)

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

実装方法

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    実装では再帰関数を用いる. ここでは、答えを最大化する深さ優先探索の例.
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> def dfs(now):<br /> if &#8220;nowが終了条件&#8221;:<br /> return &#8220;nowの答え&#8221;
  </p>

  <p>
    ret = -1<br /> for i in range(&#8220;次の状態の個数&#8221;):<br /> next = &#8220;i番目の次の状態&#8221;<br /> if &#8220;nextが条件を満たしている&#8221;:<br /> ret = max(dfs(next), ret)<br /> return ret<br /> [/sourcecode]
  </p>
</div>

SRM 425 Div2 500

<div class="outline-text-3" id="text-orgheadline3">
  <ul class="org-ul">
    <li>
      <a href="https://community.topcoder.com/stat?c=problem_statement&pm=10095&rd=13516">https://community.topcoder.com/stat?c=problem_statement&pm=10095&rd=13516</a>
    </li>
  </ul>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> # -*- coding: utf-8 -*-<br /> import math,string,itertools,fractions,heapq,collections,re,array,bisect
  </p>

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

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

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

  <p>
    for i in range(4):<br /> ret += self.dfs(x + self.vx[i],<br /> y + self.vy[i], n &#8211; 1) * self.prob[i]
  </p>

  <p>
    self.grid[x][y] = False<br /> return ret
  </p>

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

  <p>
    return self.dfs(50, 50, n)<br /> [/sourcecode]
  </p>
</div>

幅優先探索(BFS)

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

実装方法

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    実装ではQueueを用いる.
  </p>

  <p>
    [sourcecode language=&#8221;text&#8221; title=&#8221;&#8221; ]<br /> 1. 根ノードを空のキューに加える。<br /> 2. ノードをキューの先頭から取り出し、以下の処理を行う。<br /> ノードが探索対象であれば、探索をやめ結果を返す。<br /> そうでない場合、ノードの子で未探索のものを全てキューに追加する。<br /> 3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ&#8221;not found&#8221;と結果を返す。2に戻る。<br /> [/sourcecode]
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> queue = []<br /> queue.append(&#8220;初期状態&#8221;)<br /> while len(queue) > 0:<br /> # 取り出し<br /> now = queue[0]<br /> del queue[0]<br /> # now に対しての処理<br /> for i in range(&#8220;次の状態の個数&#8221;):<br /> next = &#8220;i番目の次の状態&#8221;<br /> if &#8220;nextが訪問済みであるかどうかの判定&#8221;:<br /> queue.append(next)<br /> [/sourcecode]
  </p>
</div>

SRM 453.5 Div2 500

<div class="outline-text-3" id="text-orgheadline6">
  <ul class="org-ul">
    <li>
      <a href="https://community.topcoder.com/stat?c=problem_statement&pm=10451&rd=14174">https://community.topcoder.com/stat?c=problem_statement&pm=10451&rd=14174</a>
    </li>
  </ul>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> # -*- coding: utf-8 -*-<br /> import math,string,itertools,fractions,heapq,collections,re,array,bisect
  </p>

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

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

  <p>
    # スタート地点のマーク<br /> board[startRow][startCol] = 0
  </p>

  <p>
    # キューの宣言<br /> queueX = []<br /> queueY = []<br /> queueX.append(startCol)<br /> queueY.append(startRow)
  </p>

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

  <p>
    for i in range(len(moveRow)):<br /> nextX = x + moveCol[i]<br /> nextY = y + moveRow[i]
  </p>

  <p>
    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] </div> </div> </div> 

    <div id="outline-container-orgheadline7" class="outline-2">
      <h2 id="orgheadline7">
        DFSとBFSの比較
      </h2>

      <div class="outline-text-2" id="text-orgheadline7">
        <ul class="org-ul">
          <li>
            全通りを列挙し、をまとめる必要がある場合は DFS
          </li>
          <li>
            始点からもっとも近いものを求めたいときは、BFS
          </li>
        </ul>
      </div>
    </div>

    <div id="outline-container-orgheadline8" class="outline-2">
      <h2 id="orgheadline8">
        Special Thanks
      </h2>

      <div class="outline-text-2" id="text-orgheadline8">
        <ul class="org-ul">
          <li>
            <a href="http://www.itmedia.co.jp/enterprise/articles/1001/16/news001.html">最強最速アルゴリズマー養成講座:知れば天国、知らねば地獄――「探索」虎の巻 &#8211; ITmedia エンタープライズ</a>
          </li>
          <li>
            <a href="http://qiita.com/MasayaMizuhara/items/86099ad721a329e1d6cd">全探索アルゴリズム入門 &#8211; Qiita</a>
          </li>
        </ul>
      </div>
    </div>