Informatyka i programowanieAlgorytmy — sprytne sposoby rozwiązywania problemów

Branch-and-bound odrzuca rozwiązania, których nie musi nigdy zobaczyć

W problemach kombinatorycznych liczba możliwych rozwiązań może być tak wielka, że pełne sprawdzenie wszystkich wariantów jest niepraktyczne. Branch-and-bound nadal szuka rozwiązania dokładnego, ale dla części przestrzeni oblicza optymistyczną granicę: jak dobry mógłby być najlepszy wynik ukryty w tej gałęzi. Jeśli nawet ta granica nie może pobić najlepszego rozwiązania znalezionego dotąd, całą gałąź można bezpiecznie porzucić. Metoda nie przybliża odpowiedzi — pod warunkiem poprawnych granic pomija wyłącznie obszary, o których wiadomo, że nie zawierają lepszego optimum. Im ciaśniejsze granice i wcześniej znalezione dobre rozwiązanie, tym większa część ogromnego drzewa może zniknąć bez pełnego przeszukiwania.

Pełne przeszukiwanie rośnie zbyt szybko

W problemie komiwojażera chcemy znaleźć najkrótszą trasę odwiedzającą wszystkie miasta i wracającą do punktu startowego. Nawet po usunięciu oczywistych symetrii liczba możliwych tras rośnie bardzo szybko wraz z liczbą miast. Najprostszy dokładny algorytm mógłby wygenerować wszystkie kandydatury, policzyć ich długość i wybrać najlepszą, lecz taka enumeracja szybko przestaje być praktyczna.

Branch-and-bound zachowuje dokładność, ale zmienia sposób eksploracji. Przestrzeń rozwiązań dzieli się na gałęzie opisujące coraz bardziej szczegółowe decyzje. Dla każdej gałęzi algorytm próbuje odpowiedzieć nie tylko „jakie rozwiązania tu są?”, lecz wcześniej: „czy najlepsze możliwe rozwiązanie z tej całej części ma jeszcze szansę pokonać to, co już znalazłem?”.

Granica może zastąpić tysiące dokładnych obliczeń

Dla problemu minimalizacyjnego algorytm wyznacza dolną granicę kosztu wszystkich rozwiązań znajdujących się w danej gałęzi. Granica jest optymistyczna: prawdziwe rozwiązanie może być droższe, ale nie może być tańsze od niej. Jednocześnie przechowuje koszt najlepszego pełnego rozwiązania znalezionego dotąd, nazywanego incumbentem albo górną granicą optimum.

Jeśli dolna granica gałęzi wynosi 120, a mamy już poprawne rozwiązanie o koszcie 110, nie musimy wiedzieć, czy wewnątrz gałęzi najlepszy wariant kosztuje 121, 150 czy milion. Żaden nie pobije 110. Można skasować całą gałąź. To logiczny dowód zbędności dalszego liczenia, podobny w duchu do przycinania alpha–beta, ale stosowany do ogólniejszych problemów optymalizacyjnych.

„Bound” musi być bezpieczny, inaczej można odciąć optimum

Siła metody zależy od jakości granicy, ale jej poprawność zależy od tego, by granica była rzeczywiście gwarantowana. W minimalizacji dolna granica nie może przypadkiem przekroczyć kosztu najlepszego rozwiązania ukrytego w gałęzi. Gdyby algorytm użył zbyt „pesymistycznego” oszacowania i na tej podstawie odciął gałąź, mógłby wyrzucić prawdziwe optimum.

Dobra granica powinna więc łączyć dwie cechy: być łatwa do policzenia i możliwie ciasna. Granica bardzo słaba, np. zawsze równa zero, jest bezpieczna, ale prawie niczego nie przytnie. Granica prawie równa rzeczywistemu optimum w każdej gałęzi byłaby doskonała, ale jeśli jej obliczenie jest równie trudne jak rozwiązanie całego problemu, nie daje zysku. Projektowanie branch-and-bound jest sztuką znalezienia użytecznego kompromisu.

Pierwsze dobre rozwiązanie potrafi zmienić całe wyszukiwanie

Przycinanie działa tym mocniej, im lepszy jest incumbent. Jeśli początkowo mamy tylko słabe rozwiązanie o wysokim koszcie, wiele gałęzi zachowuje teoretyczną szansę na poprawę i trzeba je rozwijać. Gdy szybko znajdziemy trasę bliską optimum, granica do pobicia staje się niska i nagle wiele innych części drzewa można odrzucić.

Dlatego kolejność przeszukiwania, heurystyki wybierania gałęzi i szybkie konstruowanie dobrych rozwiązań początkowych mogą mieć ogromne znaczenie dla czasu działania, choć końcowa odpowiedź pozostaje dokładna. W najgorszym przypadku branch-and-bound nadal może zbadać olbrzymią część przestrzeni; nie jest magicznym sposobem na usunięcie kombinatorycznej trudności. Potrafi jednak wykorzystać strukturę konkretnej instancji, aby ominąć wielką liczbę wariantów.

Historyczny przykład: komiwojażer

Klasyczna praca Little’a, Murty’ego, Sweeneya i Karela z 1963 roku przedstawiła algorytm branch-and-bound dla problemu komiwojażera. Artykuł stał się jednym z wczesnych, wpływowych przykładów techniki, w której problem dzieli się na podproblemy i oblicza dla nich granice, by eliminować obszary niemożliwe do poprawy.

Idea wykracza daleko poza trasy. Branch-and-bound stosuje się do różnych problemów optymalizacji dyskretnej, harmonogramowania i programowania całkowitoliczbowego. W każdym przypadku najciekawszy moment jest podobny: algorytm zdobywa wystarczająco dużo informacji o całej rodzinie rozwiązań, aby udowodnić, że żaden jej członek nie zasługuje już na indywidualne sprawdzenie.

Relaksacja problemu często daje granicę taniej niż pełne rozwiązanie

Jednym ze sposobów budowania boundu jest rozwiązanie łatwiejszej wersji problemu, która dopuszcza więcej możliwości niż oryginał. W minimalizacji optimum takiej relaksacji nie może być większe niż optimum problemu z dodatkowymi ograniczeniami, więc staje się bezpieczną dolną granicą. Granica może być daleka od rzeczywistego wyniku, ale jeśli jest tania do policzenia, nadal pomaga. Mocniejsze relaksacje zwykle dają ciaśniejsze granice, lecz kosztują więcej czasu. Branch-and-bound ma więc wewnętrzny problem optymalizacyjny: ile pracy opłaca się wydać na dowiedzenie się, że dalsza praca nie jest potrzebna? Zbyt słaby bound powoduje ogromne drzewo; zbyt drogi może pochłonąć oszczędności. Najlepsze implementacje dobierają granice do struktury konkretnej klasy problemów.

#algorytmy dokładne#branch and bound#kombinatoryka#optymalizacja#przycinanie#TSP
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki