본 논문은 GBFS(Greedy Best-First Search)와 같은 비허용적 탐색 알고리즘의 병렬화 과정에서 발생하는 문제점을 다룹니다. 단순한 병렬화는 순차적 탐색과 크게 다른 탐색 행동을 초래할 수 있습니다. 기존 연구에서는 GBFS에 대한 어떤 동점 해결 전략으로도 확장 가능한 상태만을 확장하도록 제한하는 병렬 탐색 알고리즘인 PUHF를 제안했습니다. 본 논문은 이러한 제약에도 불구하고 PUHF가 확장하는 상태 수가 최악의 경우 동점 해결 전략을 사용하는 순차적 GBFS가 확장하는 상태 수의 상수 배로 제한되지 않음을 보입니다. 그리고 순차적 GBFS가 어떤 동점 해결 정책으로 확장하는 상태 수의 상수 배 이내에서 상태를 확장한다는 것을 보장하는 병렬 탐욕적 탐색 알고리즘인 OBAT(One Bench At a Time)를 제안하고 실험적으로 평가합니다.
