探索アルゴリムズまとめ

edX ColumbiaXのAI (CSMM.101x)で説明されているAIで使用される探索アルゴリムズのまとめです。

b: 一つの分岐における最大の分岐数
d: 探索木における解がある深さ
m: 探索木における最大の深さ

Uninformed Search (=網羅的探索 brute-force search, 盲目的探索 blind search)
BFS: Breadth-first Search 横型探索法、幅優先探索法
空間計算量：O(b^d)
時間計算量：O(b^d)
　　完全性：○（分岐bが有限の場合。無限の場合は完全ではない）
　　最適性：○（グラフの重みが全て同じであれば、最適である）

アルゴリズム
function BFS (initialState, goalTest)
    returns SUCCESS or FAILURE:

    frontier = Queue.new(initialState)
    explored = Set.new()

    while not frontier.isEmpty()

        state = frontier.dequeue()
        explored.add(state)

        if goalTest(state):
            return SUCCESS(state)

        for neighbour in state.neighbours():
            if neighbour not in frontier U explored:
                frontier.enqueue(neighbour)
    return FAILURE

DFS: Depth-first Search 縦型探索法、深さ優先探索法
空間計算量：O(bm)
時間計算量：O(b^m)
　　完全性：○（深さが有限の場合）
　　最適性：✖️

アルゴリズム
function DFS (initialState, goalTest)
    returns SUCCESS or FAILURE:

    frontier = Stack.new(initialState)
    explored = Set.new()

    while not frontier.isEmpty()
        state = frontier.pop()
        explored.add(state)

        if goalTest(state):
            return SUCCESS(state)

        for neighbour in state.neighbours():
            if neighbour not in frontier U explored:
                frontier.push(neighbour)
    return FAILURE

IDS: Iterative Deepening Depth-first Search 反復深化深さ優先探索
空間計算量：O(bd): bは分岐係数、dは深さ
時間計算量：O(b^d)
　　完全性：○
　　最適性：○

説明：IDSを知識あり探索にしたものがIDA*である。これは、ダイクストラ法を知識あり探索にしたものがA*であることに対応する。

DA: Dijkstra Algorithm ダイクストラ法
空間計算量：
時間計算量：
　　完全性：
　　最適性：

UCS: Uniform-Cost Search 均一コスト探索法
空間計算量：O(b^(c/e)): Cは最適解のコスト、eは1アクションあたりの最低コスト
時間計算量：O(b^(c/e))
　　完全性：○(コストが有限の場合)
　　最適性：○

説明：ステップコストが全て同じであるときは幅優先探索と同じアルゴリズムになる。

アルゴリズム
function UCS (initialState, goalTest)
    returns SUCCESS or FAILURE: /*Cost f(n) = g(n) */

    frontier = Heap.new(initialState)
    explored = Set.new()

    while not frontier.isEmpty()
        state = frontier.deleteMin()
        explored.add(state)

        if goalTest(state):
            return SUCCESS(state)

        for neighbour in state.neighbours():
            if neighbour not in frontier U explored:
                frontier.insert(neighbour)
            else if neighbour in frontier:
                 frontier.decreaseKey(neighbour)
    return FAILURE

Informed Search (=発見的探索法 heuristic search)
Greedy Best-first Search 最良優先探索法

空間計算量：
時間計算量：
　　完全性：
　　最適性：

説明：
（１）方向性をもった探索なので、縦型探索や横型探索よりも早く解が求められる。
（２）未探索接点を全て保存しておく必要があるので使用メモリが膨大となる。
（３）適当な発見的関数が存在しない場合には使えない

アルゴリズム
function GBFS (initialState, goalTest)
    returns SUCCESS or FAILURE: /*Cost f(n) = h(n) */

    frontier = Heap.new(initialState)
    explored = Set.new()

    while not frontier.isEmpty()
        state = frontier.deleteMin()
        explored.add(state)

        if goalTest(state):
            return SUCCESS(state)

        for neighbour in state.neighbours():
            if neighbour not in frontier U explored:
                frontier.insert(neighbour)
            else if neighbour in frontier:
                 frontier.decreaseKey(neighbour)
    return FAILURE

A* Search エイスター探索法

空間計算量：
時間計算量：
　　完全性：
　　最適性：○（発見的関数h(n)が許容的（admissibleな場合））

説明：A*アルゴリズムは、ダイクストラ法を推定値つきの場合に一般化したもので、hが常に0である場合はもとのダイクストラ法に一致する。
（１）最適経路が必ず得られる
（２）条件を満たす発見的関数が思いつかない場合には使えない
（３）方向性をもった探索なので、縦型探索や横型探索よりも早く解が求められる
（４）最良優先探索と同様の理由で使用メモリが膨大になる

アルゴリズム
function GBFS (initialState, goalTest)
    returns SUCCESS or FAILURE: /*Cost f(n) = g(n) + h(n) */

    frontier = Heap.new(initialState)
    explored = Set.new()

    while not frontier.isEmpty()
        state = frontier.deleteMin()
        explored.add(state)

        if goalTest(state):
            return SUCCESS(state)

        for neighbour in state.neighbours():
            if neighbour not in frontier U explored:
                frontier.insert(neighbour)
            else if neighbour in frontier:
                 frontier.decreaseKey(neighbour)
    return FAILURE

Local Search
Hill Climbing Search(Greedy Local Search): 山登り法
空間計算量：
時間計算量：
　　完全性：
　　最適性：✖️

説明：
（１）現在の状態だけを保存しておけばよいので、最良優先探索法に比べ使用メモリならびに探索の手間が少ない
（２）バックトラックが得られるとは限らない
（３）最適解が得られるとは限らない

アルゴリズム
function HILL-CLIMBING(initialState)
    returns State that is a local maximum
   
    initialize current with initialState

    loop do
         neighbour = a highest - valued successor of current

         if neighbour.value <= current.value:
              return current.state
         current = neighbour