양방향 탐색

양방향 탐색(Bidirectional search)은 유향 그래프에서 초기 꼭짓점에서 목표 꼭짓점까지의 최단 경로를 찾는 그래프 탐색 알고리즘이다. 이는 두 가지 동시 탐색을 실행하는데, 하나는 초기 상태에서 앞으로 진행하고 다른 하나는 목표에서 뒤로 진행하여 두 탐색이 만날 때 중지한다. 이 접근 방식의 이유는 많은 경우 더 빠르기 때문이다. 예를 들어, 두 탐색이 모두 분기 인자 b를 가진 트리를 확장하고 시작점에서 목표까지의 거리가 d인 탐색 문제 복잡성의 단순화된 모델에서, 두 탐색 각각은 O(bd/2)의 복잡도(큰 O 표기법 참조)를 가지며, 이 두 탐색 시간의 합은 시작점에서 목표까지의 단일 탐색에서 발생하는 O(bd) 복잡도보다 훨씬 적다.

앤드루 골드버그 외 다수는 데이크스트라 알고리즘의 양방향 버전에서 올바른 종료 조건을 설명했다.

A* 탐색과 마찬가지로 양방향 탐색은 목표까지의 남은 거리(정방향 트리) 또는 시작점부터의 거리(역방향 트리)에 대한 휴리스틱 추정치에 의해 안내될 수 있다.

이라 폴은 양방향 휴리스틱 탐색 알고리즘을 설계하고 구현한 최초의 인물이었다. 시작 노드와 목표 노드에서 발생하는 탐색 트리가 해법 공간의 중간에서 만나지 못했다. 드 샹포의 BHFFA 알고리즘이 이 결함을 해결했다.

허용 가능한 휴리스틱을 사용하는 단방향 A* 알고리즘에 의해 발견된 해법은 최단 경로 길이를 가지며, 드 샹포가 설명한 BHFFA2 양방향 휴리스틱 버전도 동일한 속성을 가진다. BHFFA2는 BHFFA보다 더 신중한 종료 조건을 가진다.

 설명 

양방향 휴리스틱 탐색은 특정 상태 에서 다른 상태 로의 상태 공간 탐색이며, 에서 로, 그리고 에서 로 동시에 탐색한다. 이는 에 적용하면 를 얻을 수 있는 유효한 연산자 목록을 반환한다.

역방향 탐색을 위해 연산자가 가역적이어야 하는 것처럼 보일 수 있지만, 주어진 노드 에 대해, 각 부모 노드에서 으로 가는 유효한 연산자가 존재하는 의 부모 노드 집합을 찾을 수 있는 것만 필요하다. 이는 종종 경로 찾기 영역에서 일방통행 도로에 비유된다. 즉, 양방향으로 이동할 수 있을 필요는 없지만, 도로의 끝에 서 있을 때 도로의 시작을 가능한 경로로 결정하는 것이 필요하다.

마찬가지로, 역방향 아크(즉, 양방향으로 가는 아크)가 있는 엣지의 경우 각 방향의 비용이 같을 필요는 없다. 역방향 탐색은 항상 역비용(즉, 정방향 아크의 비용)을 사용한다. 더 공식적으로, 이 부모 를 가진 노드라면, 는 에서 까지의 비용으로 정의된다.

 용어 및 표기법 

   탐색 트리의 분기 인자
   노드 에서 노드 으로 이동하는 데 관련된 비용
   루트에서 노드 까지의 비용
   노드 과 목표 사이의 거리에 대한 휴리스틱 추정치
   시작 상태
   목표 상태 (때때로 로 표시되지만 함수와 혼동하지 말 것)
   현재 탐색 방향. 관례상 는 정방향의 경우 1, 역방향의 경우 2이다
   반대 탐색 방향 (즉, )
   방향 d의 탐색 트리. 이면 루트는 이고, 이면 루트는 이다.
   의 리프 (때때로 라고도 함). 이 집합에서 확장을 위한 노드가 선택된다. 양방향 탐색에서는 이를 탐색 '프론티어' 또는 '파면'이라고 부르기도 하는데, 탐색이 그래픽으로 표현될 때 나타나는 방식 때문이다. 이 비유에서, 확장 단계 중 한 파면의 노드가 반대 파면에서 후계자를 가지는 것으로 발견될 때 '충돌'이 발생한다.
   의 비리프 노드. 이 집합에는 탐색에 의해 이미 방문된 노드가 포함된다.

 양방향 휴리스틱 탐색 접근 방식 

양방향 알고리즘은 크게 세 가지 범주로 나눌 수 있다: 프론트 투 프론트, 프론트 투 백(또는 프론트 투 엔드), 그리고 경계 탐색. 이들은 휴리스틱을 계산하는 데 사용되는 함수가 다르다.

 프론트 투 백 

프론트 투 백 알고리즘은 노드 의  값을 과 반대 탐색 트리의 루트인  또는  사이의 휴리스틱 추정치를 사용하여 계산한다.

프론트 투 백은 세 가지 범주 중 가장 활발하게 연구되는 분야이다. 2004년 현재, 현재 가장 좋은 알고리즘(최소한 15-퍼즐 영역에서)은 BiMAX-BS*F 알고리즘이다.

 프론트 투 프론트 

프론트 투 프론트 알고리즘은 노드 의  값을 과 의 일부 부분 집합 사이의 휴리스틱 추정치를 사용하여 계산한다. 전형적인 예는 BHFFA(양방향 휴리스틱 프론트 투 프론트 알고리즘)이다. 여기서  함수는 현재 노드와 반대쪽 프론트의 노드들 사이의 모든 휴리스틱 추정치 중 최소값으로 정의된다. 또는 공식적으로:

여기서 는 노드 과  사이의 거리에 대한 허용 가능한(즉, 과대평가하지 않는) 휴리스틱 추정치를 반환한다.

프론트 투 프론트는 지나치게 많은 계산을 요구한다는 단점이 있다. 노드 이 열린 목록에 들어갈 때마다 해당  값을 계산해야 한다. 이는 위에서 설명한 대로 에서 반대쪽  집합의 모든 노드까지의 휴리스틱 추정치를 계산하는 것을 포함한다. 인 모든 영역에서  집합의 크기는 기하급수적으로 증가한다.

 각주 

 더 읽어보기 
.

분류:그래프 알고리즘
분류:검색 알고리즘