[AI] Search Algorithm

<ナビゲーションアルゴリズム分類>

1.盲目的探索方法

ターゲットノードの情報を使用せずに、ノードを機械的に展開します.

uninformed search

タイプ:深度優先ナビゲーション(DFS)/BFS(幅優先ナビゲーション)/統一コストナビゲーション

2.経験探索方法

ターゲットノードの使用方法の経験情報(ヒント)

効率的なナビゲーション

種類:貪欲な探索/A*探索

DFS

■探索木では、太陽が存在する可能性がある限り、探索を続ける.続行可能なパスがない場合は、以前の状態で他のパスに移動できる場所に戻り、ブラウズを続行します.
■ターゲットノードが奥まっている場合は、素早く解くことができ、逆に、無解経路に入ると、解くことができない場合があります.したがって、一般的には、最大深度を設定し、その深度にのみナビゲートします.
■無限の繰り返しを避けるために、繰り返しの状態を排除することができます.ちなみに、ナビゲーションでは「開く」リストと「閉じる」リストを使用して重複状態を防止します.
(1)open list:拡張されたがまだ閲覧されていないリストを含む
(2)closed list:ナビゲーション終了状態を含むリスト
■DFSはOpenリストを使ってスタックのようです.(LIFO)

# Pseudo code

depth_first_search()

open ← [시작노드]
closed ← []
while open != [] do
    X ← open 리스트의 첫 요소
    if X == goal then return SUCCESS
    else
        X의 자식 노드 생성
        X를 closed 리스트에 추가
        X의 자식노드가 이미 open이나 closed에 있다면 버린다.
        나머지 자식 노드들을 open의 맨 앞(위)에 추가 (stack)
return FAIL

BFS

■ルートノードのすべてのサブノードを探索した後、太陽が発見されなければ、レベルを下げて同じ方法で探索を続ける.すなわち,ターゲットノードに遭遇するまで横方向に行う.
■メリット:ターゲットノードに到達する最短経路を見つけることができます.また、ターゲットノードが存在する場合は、必ず見つけることができます.
■短所:一歩下に進むほど(木が深いほど)ノード数が多くなるため、探索時間が長くなる可能性が高い.
■BFSではOpenListをQのように使用する.(FIFO)

# Pseudo code

breadth_first_search()

open ← [시작노드]
closed ← []
while open != [] do
    X ← open 리스트의 첫 요소
    if X == goal then return SUCCESS
    else
        X의 자식 노드 생성
        X를 closed 리스트에 추가
        X의 자식노드가 이미 open이나 closed에 있다면 버린다.
        나머지 자식 노드들을 open의 맨 뒤(밑)에 추가 (queue)
return FAIL

BFSで8-難問を解決
盲目的なナビゲーション方法では、開始ノードからターゲットノードへのパスの検索に多くの時間がかかります.これは簡単だが、実際の複雑な問題ではほとんど役に立たない.したがって,体験的検索手法を用いることを考慮すべきである.
8−Huritic情報を用いてパズルを解く.
(1)h 1(N)=現在位置していないタイルの個数で、値が小さいほど良いノード.スペースを含まない
(2)h 2(N)=各タイルから目標位置までの距離は、値が小さいほど良いノードである.


例えば、1つのノードが別々に与えられると、上は現在のノードの状態であり、下はターゲットノードの状態である.このとき、h 1とh 2をそれぞれ求め、以下に示す.
h 1(N)=現在位置していないタイル数=1+1+0+1+0+0+1=4
h 2(N)=タイル毎のその位置までの距離=1+1+0+2+0+2+2=6
■評価関数(Evaluation Function):現在の状態の真の値を計算して返す関数

Hill-Climbing Search

従来の盲目的探索法は,無条件に決定された順序で,次の処理するノードを選択する.ただし、各ノードを評価する値があれば、より速くナビゲートできます.これらの戦略の一つは登山のテクニックです.Hill−Climbing法はまず評価関数値の高いノード(=クラス値の小さいノード)を扱う.
■純粋なHill-Climping技術
純粋なHill-Climbing技術では,オープンリストやクローズリストを用いず,h(n)のみを用いる.

while True:
1. 노드의 확장 : 현재 위치 기준으로 각 방향의 높이를 판단
2. 목표 상태인지 검사 : 만약 모든 위치가 현 위치보다 낮다면, 현재 위치를 정상이라고 판단
3. 자식 노드 선택 : 만약 현 위치가 정상이 아니라면, 확인된 위치 중 가장 높은 곳으로 이동

純粋なHill-Climbingテクノロジーを使用すると、生成されたサブノードの評価関数の値が親ノードより高い場合や同じ値を持つ場合があります.すなわち,評価関数値を下げる方向に進むことは不可能である.これを「領域最小問題(ローカル最小問題)」と呼びます.

Best-First Search

最適優先探索(Best-First Search)はHill-Climbing技術の改良である.ここではopen/cclosedリストとともに評価関数を使用します.「≪ベスト・ファースト・サーチ|Optimal First Search|emdw≫」テクノロジーでは、「≪リストを開く|Open List|emdw≫」に格納されているノードで、まず関数の値を評価するのに最適なノードを選択します.
Hill-Climbingテクノロジーでは、生成されたサブノードはどこにも保存されません.(openとclosedリストがないため).したがって、一度選択されなければ、再考されない.ただし、最適な最初の検索でopenリストが使用されているため、最初に選択されなかったノードも選択される可能性があります.

# Pseudo code

best_first_search()

open ← [시작노드]
closed ← []
while open != [] do
    X ← open 리스트에서 평가 함수 값이 제일 좋은 요소
    if X == goal then return SUCCESS
    else
        X의 자식 노드 생성
        X를 closed 리스트에 추가
        if X의 자식노드가 이미 open이나 closed에 있지 않다면,
            자식 노드의 평가 함수 h(n)의 값을 계산
            자식 노드들을 open 리스트에 추가
return FAIL

A*アルゴリズム

最適第1探索では,h(n)のみを評価関数として考慮した.ただし、Aの場合、評価関数に「パスのコスト」が追加されます.(最終的には最小費用の経路を求める必要があるため)、Aアルゴリズムの評価関数値は以下のようにすることができる.
f(n) = g(n) + h(n)
h(n):現在のノードからターゲットノードまでの距離
g(n):開始ノードから現在のノードへのコスト(開始ノードから0に増加.1を下に増加)
これにより、A*アルゴリズムは、最小費用経路を返すことを保証する.

# Pseudo code

astar_search()

open ← [시작노드]
closed ← []
while open != [] do
    X ← open 리스트에서 평가 함수 값이 제일 좋은 요소
    if X == goal then return SUCCESS
    else
        X의 자식 노드 생성
        X를 closed 리스트에 추가
        if X의 자식노드가 이미 open이나 closed에 있지 않다면,
            자식 노드의 평가 함수 f(n) = g(n) + h(n) 값을 계산
            자식 노드들을 open 리스트에 추가
return FAIL

A*アルゴリズムで8-パズルを解決する

[References]

人工知能-Pythonで学ぶ機械学習と深さ学習-