확률적 초점 탐색: 하한 진전을 통한 제한된 비최적 탐색 가속화

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

제한된 비최적 탐색은 최적 해의 $w$ 배수 내에서 솔루션을 찾으면서 탐색 노력을 줄이는 방법이다. 확률적 초점 탐색(PFS)은 기존의 초점 탐색(FS)에서 확률 $p$로 선택된 경로를 따르며, 최소 $f$ OPEN 노드를 확장하는 확률 $1-p$를 사용한다. 이 방법은 하한을 진전시키고 FOCAL을 확대하여 유효한 솔루션으로 이어질 수 있는 노드를 수용한다. PFS는 N-Puzzle, 팬케이크 정렬, 외판원 문제(TSP)에서 FS와 비교되었으며, FOCAL 수용이 지연될 때 최대 90% 이상의 노드 확장을 줄일 수 있다. 또한, Anytime Probabilistic Focal Search(APFS)는 GCTSP에서 모든 테스트된 알고리즘을 초월하는 성능을 보였다.