Probabilistic Focal Search: szybsze przeszukiwanie z ograniczeniem

Nowe badanie opublikowane na arXiv 6 września 2026 roku przedstawia Probabilistic Focal Search (PFS) — probabilistyczne rozszerzenie klasycznego algorytmu Focal Search, które ma przyspieszyć wyszukiwanie rozwiązań o ograniczonej suboptymalności. Autorzy: Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phuong Khanh Nguyen oraz Huynh Thi Thanh Binh, wykazują, że wprowadzenie elementu losowości do decyzji o ekspansji węzłów może zredukować liczbę odwiedzanych stanów nawet o ponad 90 procent w wybranych problemach.

Praca dotyczy szczególnej klasy algorytmów przeszukiwania grafów stosowanych w planowaniu i optymalizacji: bounded-suboptimal search, czyli metod poszukujących rozwiązania nie gorszego niż o współczynnik $w$ od optymalnego, ale przy znacznie mniejszym nakładzie obliczeniowym niż pełne przeszukiwanie optymalne.

Kluczowe wnioski

• Probabilistic Focal Search (PFS) łączy dwie strategie: z prawdopodobieństwem $p$ podąża za klasycznym wskazaniem Focal Search, a z prawdopodobieństwem $1-p$ rozwija węzeł o minimalnym $f$ z listy OPEN.
• Drugi mechanizm ma za zadanie „przesuwać” dolną granicę ($f_{\min}$), poszerzając zbiór FOCAL i dopuszczając nowe węzły mogące prowadzić do rozwiązań spełniających kryteria.
• W testach na N-Puzzle, Pancake Sorting i problemie komiwojażera (TSP) największe korzyści z PFS pojawiają się wtedy, gdy klasyczny Focal Search „zawiesza się” na długich plateaus wartości $f_{\min}$.
• W takich sytuacjach czynnik probabilistyczny redukuje liczbę ekspansji węzłów o około 90 procent lub więcej, np. w N-Puzzle i TSP.
• Anytime Probabilistic Focal Search (APFS) — wariant przystosowany do zwracania coraz lepszych rozwiązań w czasie — pokonał wszystkie testowane algorytmy w ewaluacji metod anytime na Generalized Covering TSP (GCTSP).

Problem długich plateaus w Focal Search

Klasyczny Focal Search opiera się na dwóch listach: OPEN, zawierającej wszystkie odkryte, jeszcze nierozwinięte węzły, oraz FOCAL, będącej podzbiorem OPEN ograniczonym progiem $w \cdot f_{\min}$. Algorytm preferuje węzły z FOCAL kierowane heurystyką, licząc na szybsze dotarcie do rozwiązania spełniającego wymóg suboptymalności $w$. Problem, który identyfikują autorzy, polega na tym, że deterministyczna polityka wyboru węzłów może przez wiele kolejnych ekspansji nie zmieniać wartości $f_{\min}$ — a to oznacza, że zbiór FOCAL nie rośnie i nowe, potencjalnie użyteczne węzły nie zostają do niego dopuszczone. W efekcie algorytm „krąży” wokół tego samego progu, tracąc czas bez realnego postępu w kierunku rozwiązania.

PFS rozwiązuje ten problem poprzez wprowadzenie losowego przełącznika. Zamiast zawsze rozwijać węzeł wskazany przez heurystykę wewnątrz FOCAL, algorytm z określonym prawdopodobieństwem $1-p$ sięga po węzeł o minimalnej wartości $f$ z całej listy OPEN. Taki ruch bezpośrednio przybliża $f_{\min}$ do wartości potrzebnej do poszerzenia FOCAL, otwierając drzwi dla nowych kandydatów na rozwiązanie. Autorzy podkreślają, że mechanizm ten balansuje między dwoma celami: kierowaniem heurystycznym (szybkie znajdowanie „obiecujących” ścieżek) i przesuwaniem dolnej granicy (uwalnianie nowych możliwości poszukiwań).

Testy na klasycznych problemach optymalizacyjnych

Zespół zbadał efektywność PFS na trzech uznanych benchmarkach: N-Puzzle (przesuwanie kafelków), Pancake Sorting (sortowanie „naleśników”) oraz problemie komiwojażera (TSP). Testy przeprowadzono przy wielu wartościach współczynnika suboptymalności $w$ oraz prawdopodobieństwa $p$, co pozwoliło ocenić, jak zmienia się skuteczność algorytmu w zależności od charakteru problemu.

Wyniki pokazują wyraźną zależność: tam, gdzie deterministyczny Focal Search napotyka długie plateaus wartości $f_{\min}$ — czyli okresy, w których dolna granica nie rośnie, a użyteczne węzły nie są dopuszczane do FOCAL — probabilistyczny czynnik przynosi bardzo duże korzyści. W przypadku N-Puzzle i TSP redukcja liczby ekspansji węzłów sięgała około 90 procent lub więcej. Inaczej wyglądała sytuacja przy Pancake Sorting, gdzie klasyczny, deterministyczny Focal Search już z natury efektywnie przesuwa dolną granicę. Tam korzyść z wprowadzenia losowości była zauważalnie mniejsza, co według autorów wskazuje jednoznacznie: mechanizm probabilistyczny jest najbardziej użyteczny wtedy, gdy dopuszczanie węzłów do FOCAL stanowi rzeczywisty bottleneck (wąskie gardło) przeszukiwania, a nie wtedy, gdy problem nie generuje takich zatorów.

Rozszerzenie anytime i transfer do innych metod

Poza podstawowym testem porównawczym autorzy zbadali też wariant anytime — Anytime Probabilistic Focal Search (APFS), przeznaczony do zastosowań, w których algorytm musi zwracać coraz lepsze rozwiązania w miarę upływu czasu, a nie tylko jedno rozwiązanie ograniczone współczynnikiem $w$. APFS testowano na Generalized Covering TSP (GCTSP) — rozszerzeniu klasycznego problemu komiwojażera. W tej ewaluacji APFS pokonał wszystkie inne testowane algorytmy anytime, co pozycjonuje probabilistyczny mechanizm jako obiecujące narzędzie nie tylko dla pojedynczych rozwiązań o ograniczonej suboptymalności, ale i dla scenariuszy iteracyjnego doskonalenia wyniku.

Jako dodatkowy eksperyment transferowy zespół zastosował ten sam mechanizm harmonogramowania (scheduler) do algorytmu Dynamic Potential Search, tworząc Probabilistic Dynamic Potential Search (PDPS). Wynik pokazuje, że idea probabilistycznego balansowania między kierowaniem heurystycznym a przesuwaniem dolnej granicy przenosi się także na inne rodziny algorytmów wykorzystujących „potencjał” jako miarę postępu, choć — jak zaznaczają autorzy — efekty wspólnego sukcesu (common-success effects) tego transferu pozostają zależne od konkretnej domeny problemu oraz przyjętego współczynnika ograniczenia.

Podsumowanie

Probabilistic Focal Search pokazuje, że proste wprowadzenie losowości do reguły wyboru węzła w przeszukiwaniu o ograniczonej suboptymalności może znacząco przyspieszyć znajdowanie rozwiązań, zwłaszcza w problemach podatnych na długie zastoje przy poszerzaniu zbioru FOCAL. Mechanizm okazuje się przenoszalny na inne metody sterowania heurystycznego, co otwiera pole do dalszych badań nad probabilistycznymi wariantami klasycznych algorytmów przeszukiwania.