검색 알고리즘: 상세 설명과 Python 구현

탐색 알고리즘 소개

탐색 알고리즘은 인공지능(AI)과 컴퓨터 과학의 핵심 도구입니다. 이 알고리즘은 문제 해결 에이전트가 복잡한 환경을 탐색하고, 해답을 찾으며, 의사결정을 내릴 수 있도록 도와줍니다. 탐색 알고리즘은 주어진 시작 상태로부터 목표 상태에 도달하는 경로를 찾기 위해 문제 공간 내의 가능한 경로를 체계적으로 조사합니다.

일반적으로 탐색 알고리즘은 다음 두 가지 주요 범주로 나뉩니다:

비정보 탐색 알고리즘 (Uninformed Search Algorithms): 이러한 알고리즘은 문제 정의 외에 도메인에 대한 구체적인 정보를 갖고 있지 않습니다. 목표의 방향을 예측하지 않고 모든 노드를 동일하게 취급하며, 무작위로 탐색 공간을 확장합니다. 복잡하거나 규모가 큰 환경에서는 비효율적일 수 있지만, 특정 조건 하에서 해답이 존재하면 반드시 찾을 수 있다는 보장을 제공하며, 더 발전된 기술의 개념적 기반이 됩니다.

정보 기반 탐색 알고리즘 (Informed Search Algorithms): 휴리스틱 탐색 알고리즘이라고도 불리는 이 방식은 추가적인 정보(휴리스틱)를 사용하여 노드의 유망도를 평가합니다. 이를 통해 알고리즘은 특정 경로를 우선적으로 탐색하며 더 효율적으로 목표에 도달할 수 있습니다.

여기서는 비정보 탐색 알고리즘과 정보 기반 탐색 알고리즘 모두에 대한 상세한 설명, 복잡도 분석, 그리고 Python 구현을 제공합니다. 각 섹션은 이해를 돕기 위해 예제 사용 사례와 함께 설명됩니다.

 

1. 비정보 탐색 알고리즘 (Uninformed Search)

1.1 너비 우선 탐색 (Breadth-First Search, BFS)

원리: 현재 깊이에 있는 모든 노드를 탐색한 후 다음 깊이로 넘어가는 방식입니다. 큐 (FIFO)를 사용합니다.

시간 복잡도: $O(b^d)$
공간 복잡도: $O(b^d)$

Python 코드:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            queue.extend(graph[node])

# 사용 예시:
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}
bfs(graph, 'A')

1.2 깊이 우선 탐색 (Depth-First Search, DFS)

원리: 가능한 한 깊게 노드를 탐색하고 더 이상 진행할 수 없을 때 이전 단계로 되돌아갑니다. 스택 (LIFO)를 사용합니다.

시간 복잡도: $O(b^d)$
공간 복잡도: $O(bd)$

Python 코드:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 사용 예시:
dfs(graph, 'A')

1.3 균일 비용 탐색 (Uniform Cost Search, UCS)

원리: BFS와 비슷하지만 깊이 대신 비용을 기준으로 탐색합니다. 가장 비용이 적은 경로를 우선적으로 탐색합니다.

시간 복잡도: $O(b^{1+C^*/\epsilon})$
공간 복잡도: $O(b^{1+C^*/\epsilon})$

Python 코드:

import heapq

def ucs(graph, start, goal):
    queue = [(0, start)]
    visited = set()

    while queue:
        cost, node = heapq.heappop(queue)
        if node == goal:
            print(f"Reached {goal} with cost {cost}")
            return
        if node not in visited:
            visited.add(node)
            for neighbor, weight in graph[node]:
                heapq.heappush(queue, (cost + weight, neighbor))

# 사용 예시:
graph_cost = {
    'A': [('B', 1), ('C', 5)],
    'B': [('D', 3), ('E', 1)],
    'C': [('F', 2)],
    'D': [],
    'E': [('F', 1)],
    'F': []
}
ucs(graph_cost, 'A', 'F')

1.4 제한 깊이 탐색 (Depth-Limited Search, DLS)

원리: 깊이 우선 탐색에 최대 탐색 깊이 제한을 추가하여 너무 깊이 들어가는 것을 방지합니다.

시간 복잡도: $O(b^l)$
공간 복잡도: $O(bl)$

Python 코드:

def dls(graph, node, goal, limit):
    if node == goal:
        print(f"Found {goal}")
        return True
    if limit <= 0:
        return False
    for neighbor in graph[node]:
        if dls(graph, neighbor, goal, limit - 1):
            return True
    return False

# 사용 예시:
dls(graph, 'A', 'F', 3)

1.5 반복 깊이 증가 탐색 (Iterative Deepening Depth-First Search, IDDFS)

원리: 깊이 제한 탐색을 반복적으로 수행하되, 매번 탐색 깊이를 증가시킵니다.

시간 복잡도: $O(b^d)$
공간 복잡도: $O(bd)$

Python 코드:

def iddfs(graph, start, goal, max_depth):
    for depth in range(max_depth):
        if dls(graph, start, goal, depth):
            return True
    return False

# 사용 예시:
iddfs(graph, 'A', 'F', 5)

2. 정보 기반 탐색 알고리즘 (Informed Search)

2.1 탐욕적 최선 우선 탐색 (Greedy Best-First Search)

원리: 휴리스틱 함수 $h(n)$을 사용하여 목표에 가장 가까워 보이는 노드를 선택해 탐색합니다.

시간 복잡도: $O(b^m)$
공간 복잡도: $O(b^m)$

Python 코드:

def greedy_best_first(graph, start, goal, heuristic):
    queue = [(heuristic[start], start)]
    visited = set()

    while queue:
        _, node = heapq.heappop(queue)
        if node == goal:
            print(f"Reached {goal}")
            return
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                heapq.heappush(queue, (heuristic[neighbor], neighbor))

# 사용 예시:
heuristic = {'A': 5, 'B': 4, 'C': 2, 'D': 6, 'E': 1, 'F': 0}
graph_simple = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
greedy_best_first(graph_simple, 'A', 'F', heuristic)

2.2 A* 탐색 (A* Search)

원리: 실제 비용 $g(n)$과 휴리스틱 예측 비용 $h(n)$을 합산하여 최소 $f(n) = g(n) + h(n)$을 가지는 노드를 선택합니다.

시간 복잡도: 휴리스틱 품질에 따라 다르지만, 최악의 경우 $O(b^d)$
공간 복잡도: $O(b^d)$

Python 코드:

def a_star(graph, start, goal, heuristic):
    queue = [(heuristic[start], 0, start)]
    visited = set()

    while queue:
        f, cost, node = heapq.heappop(queue)
        if node == goal:
            print(f"Reached {goal} with total cost {cost}")
            return
        if node not in visited:
            visited.add(node)
            for neighbor, weight in graph[node]:
                g = cost + weight
                h = heuristic[neighbor]
                heapq.heappush(queue, (g+h, g, neighbor))

# 사용 예시:
graph_weighted = {
    'A': [('B', 1), ('C', 5)],
    'B': [('D', 3), ('E', 1)],
    'C': [('F', 2)],
    'D': [],
    'E': [('F', 1)],
    'F': []
}
heuristic2 = {'A': 5, 'B': 4, 'C': 2, 'D': 6, 'E': 1, 'F': 0}
a_star(graph_weighted, 'A', 'F', heuristic2)

3. 참고문헌

• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
• Wikipedia 기여자들. (2025). Search Algorithm. Wikipedia.
• GeeksforGeeks Tutorials: Search Algorithms.