베스트 퍼스트 검색

그래프 및 트리쉬 알고리즘
α–β A* B* 역추적 빔 벨먼-포드 베스트 퍼스트 양방향 보르슈프카 분기 & 바운드 BFS 대영 박물관 D* DFS 디크스트라 에드먼즈 플로이드-워셜 프린지 검색 힐 클라이밍 IDA* 반복적 심화 존슨 점프 포인트 크루스칼 사전 BFS LPA* 프라이머리 SMA*
목록
그래프 알고리즘 검색 알고리즘 그래프 알고리즘 목록
관련 항목
동적 프로그래밍 그래프 통과 나무횡단 검색 게임 그래프 컬러링
v t

베스트 퍼스트 검색은 특정 규칙에 따라 선택한 가장 유망한 노드를 확장해 그래프를 탐색하는 검색 알고리즘의 한 종류다.

유대 펄은 "일반적으로 n의 설명, 목표에 대한 설명, 그 시점까지의 검색에 의해 수집된 정보, 그리고 가장 중요한 것은 p에 대한 어떤 추가적인 지식에도 의존할 수 있는$$ "휴리스틱 평가 함수 $f{\displaystyle }$ ${\displaystyle (n}$ ${\displaystyle )}$ ${\displaystyle f(n)}$에 의한 노드 n의 약속을 추정하는 것"이라고 설명했다.로블레스 도메인."^[1][2]

일부 저자들은 특히 "최선 검색"을 사용하여 경로의 끝이 솔루션(또는 목표)에 얼마나 가까운지를 예측하여 솔루션(또는 목표)에 더 가깝다고 판단되는 경로를 먼저 확장하려는 경험적 접근법을 가진 검색을 참조했다. 이런 특정한 유형의 검색을 탐욕스러운 최선의 우선^[2] 검색 또는 순수한 휴리스틱 검색이라고 한다.^[3]

현재 가장 적합한 확장 후보를 효율적으로 선택하는 것은 일반적으로 우선 순위 대기열을 사용하여 구현된다.

A* 검색 알고리즘은 B*와 같이 최선의 첫 번째 검색 알고리즘의 예다. 최상의 알고리즘은 조합 검색에서 경로 찾기에 종종 사용된다. A*와 B*는 둘 다 탐욕스러운 최선의 우선 검색이 아니며, 이는 출발부터 목표까지의 거리 외에 추가로 출발까지의 거리를 포함하기 때문이다.

탐욕스러운 BFS

탐욕스러운 알고리즘을 사용하여 부모의 첫 번째 후계자를 확장하십시오. 후속 프로그램이 생성된 후:^[4]

1. 후계자의 휴리스틱이 부모보다 나은 경우, 후계자는 대기열의 전면에 설정(부모가 바로 뒤에 재삽입된 상태), 루프가 다시 시작된다.
2. 그렇지 않으면 후임자를 큐에 삽입한다(휴리스틱 값으로 결정된 위치). 이 절차는 부모의 나머지 후계자(있는 경우)를 평가한다.

아래는 이 알고리즘의 유사 코드 예로서, 여기서 대기열은 목표로부터의 경험적 거리를 기준으로 노드를 주문하는 우선순위 대기열을 나타낸다. 이 구현은 방문한 노드를 추적하므로 리디렉션되지 않은 그래프에 사용할 수 있다. 경로를 검색하도록 수정할 수 있다.

절차 GBS(시작, 대상): 대기열이 비어 있지 않은 동안 방문하여 대기열에 추가 시작으로 표시 Do: current_node an min distance to target: current_node를 current_node의 대기열 인접 n에서 current_node를 제거하는 대기열의 정점: n을 방문하지 않은 경우 n: marc n을 방문하여 대기열 반환 실패에 n을 추가함  

참고 항목

• 빔 검색
• A* 검색 알고리즘
• 디크스트라의 알고리즘

참조

외부 링크

• Wikibooks: 인공지능: 베스트 퍼스트 검색