[인공지능] 맹목적 탐색

그래프 탐색 방법

 

맹목적 탐색 (uniformed search)

• 정해진 순서에 따라 상태 공간 그래프를 점차 확장 (open) 해가면서 해를 탐색하는 방법

 

탐색 과정:

• 시작 시, 확장 (open) 공간에는 초기 상태 노드만 존재
• 반복:
  • 만약 확장 (open) 공간이 비었다면, 목표 노드에 도달하는 해는 존재하지 않음
  • 확장 (open) 공간에서 하나의 노드 선택하여 제거
  • If: 선택된 노드가 목표 상태라면 탐색을 종료하고 결과 반환
  • Else: 선택된 노드에서 확장할 수 있는 모든 노드를 확장 (open) 공간에 추가

 

이때 이미 방문한 노드에 대해 처리를 해주지 않는다면 탐색이 무한 반복될 수 있다.

 

예를 들어,

순환 그래프의 경우 탐색이 무한 반복되는 경우가 발생할 수 있다.

 

따라서 빈 탐색 완료된 (closed) 노드를 저장할 집합을 시작 시 생성한 후,

확장 (open) 공간에서 노드를 선택할 때, 선택한 노드는 탐색 완료된 (closed) 집합에 저장한다.

 

또한 선택된 노드에서 확장할 수 있는 모든 노드 중 (Else), closed set에 없는 노드를 확장 (open) 공간에 추가한다.

 

이를 통해 무한 반복 문제를 해결할 수 있다.

 

이때 Open의 데이터 타입에 따라,

확장 공간에서 어떤 노드를 선택하는 지가 결정된다.

 

깊이 우선 탐색 (DFS)

 

2024.04.11 - [[학교 수업]/[학교 수업] 자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack

자료구조 및 알고리즘 5 - Queue and Stack

 

깊이 우선 탐색 (depth-first search) 은 해가 존재할 가능성이 존재하는 한 앞으로 계속 전진, 즉 깊이 방향으로 탐색한다.

 

최근에 생성된 노드를 가장 먼저 확장한다.

즉, open의 자료 구조가 stack이다.

 

일반적으로 백트래킹을 위해 깊이 제한을 둔다.

또한 재귀로 구현한다면 stackoverflow의 위험성이 있고,

효율성의 측면에서는 잘못된 방향으로 끝까지 가는 것을 막기 위함이 있다.

 

너비 우선 탐색 (BFS)

 

초기 노드에서 시작하여 모든 자식노드를 확장하여 생성, 이 때 생성된 순서대로 노드를 확장한다.

즉, open의 자료구조가 queue이다.

 

BFS는 출발 노드에서 목표 노드까지의 최단 길이 경로 (shortest-length path)를 찾는 것을 보장한다.

하지만, 목표 상태를 찾을 때까지 생성된 모든 노드를 관리하기 위해 많은 기억공간을 필요로 한다는 단점이 있다.

 

깊이 우선 탐색 vs 너비 우선 탐색

 

깊이 우선 탐색

• 메모리 공간 사용 효율적
• 최단 경로해 탐색 보장 불가

 

너비 우선 탐색

• 최단 경로해 탐색 보장
• 메모리 공간 사용 비효율적

 

만약 노드와 노드 사이에 경로 비용이 추가되면 어떻게 탐색할까?

 

균일 비용 탐색 (Uniform cost search)

 

균일 비용 탐색이란 그래프에서 노드 간의 경로를 찾아주는 다익스트라 알고리즘을 이용해 탐색하는 방식을 의미한다.

2024.09.24 - [[학교 수업]/[학교 수업] 자료구조 및 알고리즘] - [자료구조 및 알고리즘] #20 - Shortest Path

[자료구조 및 알고리즘] #20 - Shortest Path