최선 우선 탐색(Best First Search)은 다음에 방문할 노드를 정할 때, 가장 유망해 보이는(promising) 노드를 판단하여 선택하는 그래프 순회(traversal) 기법입니다. 단순히 순서대로 노드를 방문하는 것이 아니라, 평가 함수(evaluation function)를 사용해 각 노드의 비용이나 점수를 계산하고, 가장 좋아 보이는 노드부터 우선적으로 탐색합니다.
이처럼 노드를 평가할 때 휴리스틱(heuristic), 즉 경험적 지식을 활용하기 때문에 최선 우선 탐색은 휴리스틱 탐색(heuristic search) 또는 정보 활용 탐색(informed search) 기법으로 분류됩니다.
우선순위 큐와 BFS와의 관계
최선 우선 탐색에서는 노드의 비용(cost)을 우선순위 큐(priority queue)에 저장합니다. 이 때문에 구현 구조가 너비 우선 탐색(BFS, Breadth-First Search)과 매우 유사합니다. 차이점은 일반적인 큐(queue) 대신 우선순위 큐를 사용한다는 것뿐입니다. 즉, BFS에서 큐를 사용하듯 최선 우선 탐색에서는 우선순위 큐를 동일하게 활용하면 됩니다.
최선 우선 탐색 알고리즘
Step 1 : 우선순위 큐 pqueue를 생성한다.
Step 2 : 시작 노드(start)를 pqueue에 삽입한다 : pqueue.insert(start)
Step 3 : pqueue의 원소를 하나씩 꺼내며 반복한다.
Step 3.1 : 꺼낸 원소가 목표(goal) 노드라면 종료한다.
Step 3.2 : 아니라면, 이웃 노드들을 순회하고 해당 노드를 '검사 완료'로 표시한다.
Step 4 : 종료(End).
이 알고리즘은 큐에 담긴 경로 중 가장 짧은(비용이 낮은) 경로를 먼저 순회합니다. 최악의 경우 시간 복잡도는 O(n·log n)입니다. 이는 우선순위 큐의 삽입·삭제 연산이 로그 시간(log n)이 소요되고, 총 n개의 노드를 처리하기 때문입니다.
장점과 한계
장점: 휴리스틱 함수를 활용해 목표 지점까지 더 빠르게 도달할 수 있으며, 불필요한 노드 탐색을 줄여 탐색 효율을 높일 수 있습니다.
한계: 성능이 휴리스틱 함수의 품질에 크게 좌우되며, 함수가 잘못 설계되면 최적 경로를 보장하지 못할 수 있습니다. 또한 탐색 대기 목록을 계속 유지해야 하므로 메모리 사용량이 늘어날 수 있다는 점도 고려해야 합니다.