연구진은 경계가 있는 준최적 탐색 기법인 Focal Search(FS)의 한계를 보완한 확률적 초점 탐색(Probabilistic Focal Search, PFS)을 제안했다. 기존 FS는 결정론적 정책으로 인해 탐색 하한값(f_min)이 오래 정체될 수 있는데, PFS는 확률 p로 FS의 휴리스틱 안내를 따르고 1-p 확률로 최소 f값 노드를 확장해 하한값 갱신을 촉진한다. N-퍼즐, 팬케이크 정렬, 외판원 문제(TSP)에서 FS와 비교 실험한 결과, f_min 정체가 길게 발생하는 상황에서 노드 확장 수를 약 90% 이상 줄이는 효과를 보였다. 애니타임 확장판인 APFS는 일반화 커버링 TSP에서 비교 대상 알고리즘 전체를 능가했다.

• •결정론적 FS의 f_min 정체 문제를 확률적 노드 확장으로 보완한 PFS 제안
• •N-퍼즐, 팬케이크 정렬, TSP에서 노드 확장 수 최대 약 90% 감소
• •애니타임 확장판 APFS가 일반화 커버링 TSP에서 전체 비교 알고리즘 능가
• •동적 잠재력 탐색에도 메커니즘 이전 적용해 PDPS로 확장
• •FS가 이미 효율적인 경우(팬케이크 정렬)에는 개선 폭이 작음