🔍 인공지능 탐색알고리즘 - 맹목적 탐색 알고리즘

📌 1. 맹목적 탐색(Blind Search)이란?

맹목적 탐색(Blind Search)은 탐색 과정에서 목표 상태까지의 거리나 비용을 고려하지 않고, 단순한 규칙에 따라 탐색을 진행하는 방식입니다.
즉, 휴리스틱(heuristic) 정보 없이 가능한 모든 경우의 수를 무작위로 탐색하며 해결책을 찾습니다.

📌 맹목적 탐색의 특징
✔ 사전 정보 없이 모든 경로를 탐색
✔ 비효율적일 수 있으나, 완전 탐색이 보장됨
✔ 최적의 해를 보장하지 않음 (경우에 따라 최적 경로가 아닐 수도 있음)
✔ 그래프 또는 트리 구조에서 사용됨

📌 대표적인 맹목적 탐색 알고리즘
1. 깊이 우선 탐색(DFS, Depth-First Search)
2. 너비 우선 탐색(BFS, Breadth-First Search)
3. 깊이 제한 탐색(DLS, Depth-Limited Search)
4. 반복적 깊이 심화 탐색(IDDFS, Iterative Deepening DFS)

이제 각각의 알고리즘을 하나씩 살펴보겠습니다.

📌 2. 깊이 우선 탐색(DFS: Depth-First Search)

✅ DFS란?

DFS(깊이 우선 탐색, Depth First Search)는 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방식입니다.
즉, 먼저 갈 수 있는 곳까지 최대한 깊이 탐색한 후, 막히면 되돌아가 다른 경로를 탐색하는 방식입니다.

이미지 출처: 위키백과, '깊이 우선 탐색'

🔍 DFS 동작 과정

1. 시작 노드를 스택(Stack)에 삽입하고 방문 처리

2. 스택의 최상단 노드에서 방문하지 않은 인접 노드를 찾아 방문 후 스택에 삽입

3. 더 이상 방문할 노드가 없으면 스택에서 노드를 꺼내며 백트래킹(Backtracking)

4. 목표 노드를 찾거나 모든 경로를 탐색할 때까지 반복

이미지 출처: 위키백과, '깊이 우선 탐색'

✅ DFS의 특징

✔ 스택(Stack) 또는 재귀(Recursion)를 사용하여 구현 가능
✔ 깊은 곳에 있는 목표를 빨리 찾을 수 있음
✔ 경로가 매우 깊거나 무한 루프가 발생할 수 있음 → 백트래킹 필요

✅ DFS 코드 구현 (Python)

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# DFS 호출
dfs(graph, 'A')

📌 3. 너비 우선 탐색(BFS: Breadth-First Search)

✅ BFS란?

BFS(너비 우선 탐색, Breadth First Search)는 모든 이웃 노드를 먼저 탐색한 후, 다음 깊이의 노드를 탐색하는 방식입니다.
즉, 가까운 곳부터 차례대로 탐색하는 방식입니다.

🔍 BFS 동작 과정

1. 시작 노드를 큐(Queue)에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내고, 방문하지 않은 인접 노드를 모두 큐에 삽입

3. 목표 노드를 찾거나 모든 경로를 탐색할 때까지 반복
   DFS(깊이우선탐색)과의 비교
   
   이미지 출처: 위키백과, 너비우선탐색

✅ BFS의 특징

✔ 최단 경로 탐색에 유리
✔ 큐(Queue)를 사용하여 구현
✔ 메모리 사용량이 DFS보다 많음

✅ BFS 코드 구현 (Python)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# BFS 호출
bfs(graph, 'A')

📌 BFS 실행 결과 예시

A B C D E F

📌 4. 깊이 제한 탐색(DLS: Depth-Limited Search)

✅ DLS란?

DLS(깊이 제한 탐색)는 DFS 방식과 동일하지만, 탐색할 최대 깊이를 제한하여 무한 루프를 방지하는 방식입니다.
즉, 깊이 제한을 설정하여, 해당 깊이까지만 탐색을 수행합니다.

🔍 DLS 동작 과정

1. DFS 방식으로 탐색을 진행하되, 현재 탐색 깊이가 제한 깊이에 도달하면 탐색을 중단

2. 목표 노드를 찾거나 탐색이 끝날 때까지 반복

✅ DLS의 특징

✔ DFS의 무한 루프 문제 해결 가능
✔ 너무 깊은 경로를 탐색하지 않도록 조절 가능
✔ 최적 해를 보장하지 않으며, 목표가 깊은 곳에 있으면 탐색 실패 가능

✅ DLS 코드 구현 (Python)

def dls(graph, node, goal, depth_limit, depth=0):
    if depth > depth_limit:
        return False
    print(node, end=' ')
    if node == goal:
        return True
    for neighbor in graph[node]:
        if dls(graph, neighbor, goal, depth_limit, depth+1):
            return True
    return False

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# DLS 호출
print("\nDLS 탐색 결과:")
dls(graph, 'A', 'F', 2)

📌 DLS 실행 결과 예시 (깊이 제한 2일 때)

A B D E C

📌 5. 반복적 깊이 심화 탐색(IDDFS: Iterative Deepening Depth-First Search)

✅ IDDFS란?

IDDFS(반복적 깊이 심화 탐색)는 깊이 제한 탐색(DLS)을 여러 번 수행하면서 탐색 깊이를 점진적으로 증가시키는 방식입니다.
즉, 깊이 제한을 1부터 시작해 점진적으로 늘려가면서 탐색하는 방식으로,
DFS의 메모리 효율성과 BFS의 최단 경로 보장 장점을 결합한 알고리즘입니다.

🔍 IDDFS 동작 과정

1. 깊이 제한 탐색(DLS)을 깊이 0부터 시작하여 하나씩 증가시키며 반복 실행

2. 목표 노드를 찾거나 탐색이 끝날 때까지 반복

3. DLS의 깊이를 계속 증가시키며 최적의 해를 찾음

✅ IDDFS의 특징

✔ DFS의 메모리 효율성과 BFS의 최단 경로 보장 장점을 결합한 방식
✔ 메모리를 DFS보다 적게 사용하면서도 BFS처럼 최단 경로를 찾을 수 있음
✔ 중복 탐색이 많아질 수 있어 실행 시간이 길어질 수도 있음

✅ IDDFS 코드 구현 (Python)

def dls(graph, node, goal, depth_limit, depth=0):
    """깊이 제한 탐색(DLS) 함수"""
    if depth > depth_limit:
        return False
    print(node, end=' ')
    if node == goal:
        return True
    for neighbor in graph[node]:
        if dls(graph, neighbor, goal, depth_limit, depth + 1):
            return True
    return False

def iddfs(graph, start, goal, max_depth):
    """반복적 깊이 심화 탐색(IDDFS) 함수"""
    for depth in range(max_depth + 1):
        if dls(graph, start, goal, depth):
            return True
    return False

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# IDDFS 호출
print("\nIDDFS 탐색 결과:")
iddfs(graph, 'A', 'F', 3)

📌 IDDFS 실행 결과 예시 (최대 깊이 3일 때)

A B D E C F

✅ IDDFS의 장점과 단점

🟢 장점

🔴 단점

🎯 마무리: 맹목적 탐색 알고리즘 비교