[인공지능개론] 탐색 Search

탐색 (Search)

탐색은 출발지에서 목적지까지 어떻게 가야 하는지를 해결하는 문제이다.

탐색 알고리즘의 기본 3가지

• DFS (Depth First Search) - 깊이 우선 탐색
• BFS (Breadth First Search) - 너비 우선 탐색
• UCS (Uniform Cost Search) - 균일 비용 탐색, 다익스트라(Dijkstra) 알고리즘을 이용한다.

Tree Search와 Graph Search

• Tree Search: 지나온 노드로 다시 갈 수 있는 탐색 방식이다.
• Graph Search: 지나온 노드로 다시 갈 수 없는 탐색 방식이다.

DFS (Depth First Search)

• 스택을 이용한 알고리즘이다.

STEP

1. 상태(state)를 이동할 때 스택에 해당 노드를 삽입한다.
2. 더 이상 방문하지 않은 노드가 없을 때까지 깊이 우선으로 이동한다.
3. 방문하지 않은 노드가 없으면 스택에서 순서대로 노드를 꺼낸다.
4. 노드를 꺼내면서 다시 2번 과정을 반복한다.
5. 더 이상 스택에 노드가 남아있지 않을 때까지 반복한다.

DFS 코드 (Python)

# DFS (깊이 우선 탐색) - 재귀함수 사용
def dfs(initNode):
    visited[initNode] = True
    print(initNode)
    for node in graph[initNode]:
        if not visited[node]:
            dfs(node)

# DFS (깊이 우선 탐색) - 스택 사용
def dfs(initNode):
    stack = [initNode]
    visited[initNode] = True
    while stack:
        currentNode = stack.pop()
        print(currentNode)
        for node in graph[currentNode]:
            if not visited[node]:
                stack.append(node)
                visited[node] = True

BFS

• 큐를 이용한 알고리즘

STEP

BFS 코드 (Python)

# BFS (너비 우선 탐색) - 큐 사용
from collections import deque

def bfs(initNode):
    queue = deque([initNode])
    visited[initNode] = True
    while queue:
        currentNode = queue.popleft()
        print(currentNode)
        for node in graph[currentNode]:
            if not visited[node]:
                queue.append(node)
                visited[node] = True

UCS

• 우선순위 큐를 사용