[인공지능원론] 2. 탐색(Search) - (1)

📍1. 탐색(Search) 이란?

인공지능에서 기본적인 도구로, 컴퓨터가 문제 해결을 위해 스스로 해답에 이르는 경로를 찾아가는 과정이다.

= 시작상태에서 목표상태까지의 경로를 찾는 것!

✔️상태공간(state space): 상태들이 모여 있는 공간
✔️연산자: 다음 상태를 생성하는 것

 

 

 

📍2. 상태 공간 탐색 문제

✍️ 8-puzzle

8-puzzle에서 연산자는 빈간을 4방향으로 움직이는 UP, DOWN, LEFT, RIGHT이 있다.

 

 

✍️ 경로 찾기 문제

✔️초기 상태: 에이전트가 A에 있는 것

✔️목표 상태: 에이전트가 F에 있는 것

✔️연산자: 가능한 결러 중 하나의 경로를 선택하는 것 (=다음 상태를 생성하는 것)

 

☑️에이전트란?

어떤 환경에서 특정 목적을 달성하기 위해 행동하는 존재로, 그 과정에서 학습이나 최적화된 결정을 내리는 특성을 가진다.

 

 

✍️  8-queen 문제

8x8 체스판에 두 개의 퀸이 서로를 위협하지 않도록 8개의 퀸을 배치하는 문제이다.

각 퀸은 고유한 열(세로줄)에 하나씩 배치되며, 배치 과정에서 "퀸은 같은 행(가로줄), 열, 또는 대각선에 다른 퀸이 있어선 안 된다"는 규칙을 따른다.

 

✔️초기 상태: 퀸들이 배치된 체스판의 상태입니다. 초기 상태는 퀸이 없는 빈 체스판

✔️목표 상태: 8개의 퀸이 서로 위협하지 않는 배치를 만족할 때

✔️연산자: 새로운 퀸을 특정 행에 배치하는 동작

 연산자 집합은 각 열에 퀸을 배치할 때 i번째 행에 배치하는 연산자를 의미한다.

즉, 위 그림에서 place3 연산자는 현재 열에 퀸을 3번째 행에 배치하는 것을 뜻한다.

 

 

📍3. 탐색 트리

✔️상태 = 노드(node)

✔️초기 상태 = 루트 노드

✔️연산자 = 간선(edge) (다음 상태를 생성하는 것)

 

➡️ 탐색 트리는 초기 상태에서 연산자를 적용하면 만들어지는 트리

(연산자를 적용하기 전까지는 탐색 트리는 미리 만들어져 있지 않음! 현재 상태에 연산자를 가할 때마다 새롭게 생성되는 것)

 

 

✍️  4-queen 문제 탐색 트리의 일부

 

 

---

 

📍4. 기본적인 탐색 기법

✔️탐색의 종류

 

 

☑️맹목적인 탐색 방법(blind search method)

목표 노드에 대한 정보를 이용하지 않고 기계적인 순서로 노드를 확장하는 방법으로 매우 소모적인 탐색을 하게 된다.

e.g.) 깊이우선탐색, 너비우선탐색, 균일비용탐색

 

☑️경험적 탐색 방법(heuristic search method)

목표 노드에 대한 경험적인 정보를 사용하는 방법으로, 효율적인 탐색이 가능하다. 이런 경험적인 정보를 휴리스틱(heuristic)이라고 한다.

 

✔️탐색 성능 측정

1️⃣완결성(completeness)

문제에 해답이 있다면, 반드시 해답을 찾을 수 있는지 여부

2️⃣최적성(optimality)

가장 비용이 낮은 해답을 찾을 수 있는지 여부

3️⃣ 시간 복잡도(time complexity)

해답을 찾는데 걸리는 시간

4️⃣ 공간 복잡도(space complexity)

탐색을 수행하는 데 필요한 메모리의 양

 

✔️시간/공간 복잡도 표현

b: 탐색 트리의 최대 분기 계수

d: 목표 노드의 깊이

m: 트리의 최대 깊이

 

 

📍5. 깊이 우선 탐색(depth-first search , DFS)

탐색 트리 상에서 해가 존재할 가능성이 존재하는 한, 앞으로 계속 전진하여 탐색하는 방법이다.

🚨목표 노드가 깊은 곳에 있는 경우에는 빠르게 해를 구할 수 있지만, 반대로 해가 없는 경로에 빠지게 되면 나오지 못할 수 있다.

 

 

✔️8-puzzle에서의 DFS

 

✔️OPEN 리스트와 CLOSED 리스트

탐색에서는 중복된 상태를 막기 위하여 2개의 리스트를 사용한다.
1️⃣ OPEN 리스트: 확장은 되었으나 아직 탐색하지 않은 상태들이 들어 있는 리스트
2️⃣ CLOSED 리스트: 탐색이 끝난 상태들이 들어 있는 리스트

 

 

✔️DFS algorithm

def DFS(root):
    open = [root]  # 탐색할 노드를 담는 리스트 (스택처럼 사용)
    closed = []    # 이미 탐색한 노드를 담는 리스트

    while open != []:  # open 리스트가 비어 있지 않을 때까지 반복 (open 리스트에 뭐라도 있으면 시행)
        X = open.pop(0)  # open 리스트의 첫 번째 요소(현재 노드)를 꺼냄

        if X == goal:  # 현재 노드가 목표 노드라면 탐색 성공
            return "SUCCESS"
        
        # 자식 노드 생성 (여기서는 구체적 생성 과정이 생략됨)
        children = generate_children(X)

        closed.append(X)  # 현재 노드를 closed에 추가

        for child in children:
            # 자식 노드가 이미 open이나 closed에 있다면 무시
            if child not in open and child not in closed:
                open.insert(0, child)  # 자식 노드를 open의 처음에 추가 (스택 구조)

    return "FAIL"  # 탐색 실패

 

 

✔️DFS 예시 - 목표: 노드 U 찾기

 

✔️DFS의 분석

🧷완결성

무한 상태 공간에서는 깊이 우선 탁색은 무한 경로를 따라 끝없이 나갈 수 있다.

따라서 무한 상태 공간에서는 완결적이지 않다.

 

🧷시간 복잡도

여기서 b는 분기 계수이다. 만약 m(트리의 최대 깊이)이 d(정답의 깊이)보다 아주 크다면 시간이 많이 걸린다. 그렇지 않은 경우에는 너비 우선 탐색보다도 빠를 수 있다.

 

🧷공간 복잡도

O(𝑏𝑚), 즉 선형 복잡도만을가진다. 탐색 트리에서 한 줄 단위로 탐색하므로, 모든 노드를 저장하고 있을 필요는없다. 이점은 너비 우선탐색에 비하여 큰 장점이다.

🧷최적성

가장 경로가 짧은 최적의 해답은 발견할 수 없다. 가장 왼쪽(leftmost)에 있는 해답만을 발견한다.

 

 

📍6. 너비 우선 탐색(BFS)

루트 노드의 모든 자식 노드들을 탐색한 후에 해가 발견되지 않으면 한 레벨 내려가서 동일한 방법으로 탐색을 계속하는 방법이다.

루트노드에서의거리순으로탐색이진행된다.

 

 

✔️BFS algorithm

def BFS(root):
    open = [root]  # 탐색할 노드를 담는 리스트 (큐처럼 사용)
    closed = []    # 이미 탐색한 노드를 담는 리스트

    while open != []:  # open 리스트가 비어 있지 않을 때까지 반복
        X = open.pop(0)  # open 리스트의 첫 번째 요소(현재 노드)를 꺼냄

        if X == goal:  # 현재 노드가 목표 노드라면 탐색 성공
            return "SUCCESS"
        
        # 자식 노드 생성 (구체적 생성 과정은 생략)
        children = generate_children(X)

        closed.append(X)  # 현재 노드를 closed에 추가

        for child in children:
            # 자식 노드가 이미 open이나 closed에 있다면 무시
            if child not in open and child not in closed:
                open.append(child)  # 자식 노드를 open의 끝에 추가 (큐 구조)

    return "FAIL"  # 탐색 실패

 

 

✔️BFS 예시 - 목표: 노드 U 찾기

 

 

✔️BFS의 분석

🧷완결성

분기 계수 b가 유한하면 너비 우선 탐색은 반드시 해답을 발견할 수 있다.

 

🧷시간 복잡도와 공간 복잡도

일단 생성되는 노드의 개수를 세어보자.

이 노드들이 메모리 상에 있어야 하기 때문에 왼쪽과 같은 지수복잡도가 된다. 

➡️BFS는 가장 가까운 정답을 발견할 수 있지만, 메모리가 많이 필요하다.

 

 

📍7. 깊이 제한 탐색(Deep-Limited Search)

DFS와 기본적인 것은 같지만, 끝까지 깊이 들어가지 않고 어떤 한계를 정해서 그 깊이 이상은 탐색하지 않고 백트랙킹하는 것이다.

 

 

☑️IDDFS(Iterative Deepening DFS, 반복적 깊이 우선 탐색)

한계 깊이를 1, 2, 3, 4 ... 차례대로 늘려가며 깊이 제한 탐색을 진행하는 것이다. 목표를 찾을 때까지 제한 깊이를 늘려가면서 탐색한다.

 

 

✔️IDDFS algorithm

def IDDFS(root):
    # 0부터 무한대(∞)까지 깊이를 점진적으로 증가시키며 탐색
    for depth in range(0, float('inf')):
        # 현재 깊이에서 DFS 실행 (깊이 제한 있는 DFS 사용)
        found, remaining = DFS(root, depth)
        
        # 만약 찾았다면 결과 반환 (성공)
        if found is not None:
            return found
        
        # 더 탐색할 노드가 남아 있지 않다면 NULL 반환 (실패)
        elif not remaining:
            return None

 

 

✔️IDDFS의 장점

1️⃣완결성(completeness) 보장

해답이 존재하면 반드시 찾아낸다. (BFS의 완전성을 결합)

2️⃣최적의 경로 탐색

해답이 여러 개일 경우, 가장 적은 비용(최단 경로)을 가진 해답을 찾을 수 있다.

3️⃣ 빠른 초기 응답

🧷 탐색 초기에는 깊이가 얕은 노드를 빠르게 탐색하기 때문에 결과를 빠르게 제공할 수 있다.

(알고리즘의 응답성이 향상된다.)

🧷 프로그램이 지금까지 탐색한 중에서 최고의 결과를 언제든 활용할 수 있다.

4️⃣ 공간 효율성

🧷 깊이 우선 탐색(DFS)의 특성을 활용해 메모리 사용량이 적다.

🧷 한 번에 한 경로만 탐색하기 때문에 너비 우선 탐색(BFS)보다 메모리를 아낄 수 있다.