Wyjaśnienie rozgałęzień i granic

Mam test dotyczący gałęzi i związanego algorytmu. Rozumiem teoretycznie, jak działa ten algorytm, ale nie mogłem znaleźć przykładów, które ilustrują praktyczne zastosowanie tego algorytmu.

Znalazłem kilka przykładów takich jak ten, ale nadal jestem tym zdezorientowany. Szukałem również problemu sprzedawcy podróży i nie mogłem go zrozumieć.

Potrzebuję pewnych problemów i jak można je rozwiązać za pomocą gałęzi i powiązania.

Zastosujmy Branch i Bound do Knapsack , mam nadzieję, że to wyjaśni ci tę koncepcję.

Mamy $n$ przedmioty oznaczone $1$ przez do $n$. $v_i$ jest wartością $i$pozycja i $w_i$jego waga. Staramy się zmieścić je w plecaku, który może pomieścić do$T$ waga w sumie i staramy się zmaksymalizować sumę wartości przedmiotu, który wkładamy do plecaka.

Podstawą jest zwykłe podejście zwrotne. Najpierw stawiamy$v_1$ w paczce, a następnie rozwiąż problem z pozostałymi $n-1$przedmioty z rekurencją. Następnie usuwamy$v_1$ z paczki i rozwiązać problem dla pozostałych $n-1$ ponownie, a my zwrócimy najlepszą konfigurację, jaką znaleźliśmy.

Cofanie jest częścią „Branch” i „Bound”. Rozgałęziasz się (w przypadku plecaka) na dwa przypadki: „przedmiot$i$ jest częścią rozwiązania ”i„ item $i$nie jest częścią rozwiązania ”. Możesz to sobie wyobrazić jako drzewo binarne, w którym lewe dziecko to jedna sprawa, a prawe dziecko to druga sprawa. To drzewo jest drzewem wyszukiwania (lub przestrzenią wyszukiwania ): jego głębokość wynosi$n$i dlatego ma $O(2^n)$węzły Algorytm ma zatem wykładniczy czas działania pod względem liczby elementów.

Teraz przechodzimy do części „Związanej”: staramy się znaleźć takie kryteria, że ​​możemy powiedzieć, że „ta konfiguracja nigdy się nie sprawdza, więc równie dobrze możemy nie zawracać sobie tym głowy”. Przykładem takiego kryterium jest „waga przedmiotów, które już włożyliśmy do plecaka, przekracza$T$„: jeśli dodaliśmy, powiedzmy, pierwszy $n/2$ przedmioty do plecaka i dlatego jest już pełny, nie ma sensu wkładać przedmiotów $n/2+1$ przez do $n$ również w plecaku, ale nie ma sensu próbować dopasować żadnego podzbioru $n/2+1$ przez do $n$ w plecaku, ponieważ jest już pełny, więc oszczędzamy $2^{n/2}$skrzynie Innym przykładem jest „ nawet jeśli wstawię wszystkie pozostałe elementy, wartość przedmiotów, które włożyłem, nie przekroczy najlepszej konfiguracji, jaką do tej pory znalazłem ”.

Kryteria te zasadniczo odcinają części drzewa wyszukiwania: w pewnym węźle mówisz na przykład: „lewe poddrzewo nie da mi lepszej konfiguracji, ponieważ X”, więc zapominasz o tym poddrzewie i nie eksplorujesz go. Poddrzewo głębi$d$ że wycięty w ten sposób cię ratuje $O(2^d)$ węzły, które mogą być nieco przyspieszone, jeśli masz szczęście.

Zauważ, że nazywa się to „ Bounding ”, ponieważ zwykle wiąże się to z pewnym dolnym lub górnym zakresem: dla kryterium „ nawet jeśli wstawię wszystkie pozostałe elementy, wartość elementów, które wprowadzę, nie przekroczy najlepszej konfiguracji Znalazłem do tej pory ”, wartość twojej najlepszej konfiguracji do tej pory stanowi dolną granicę najlepszej konfiguracji, więc wszystko, co nigdy nie przekroczy tej dolnej granicy, jest skazane na niepowodzenie.

Możesz sprawić, by część „Bounding” była tak złożona, jak tylko chcesz. Na przykład problemy z programowaniem liczb całkowitych są często rozwiązywane za pomocą relaksacji: rozluźniasz swój program do programu liniowego, który możesz rozwiązać w czasie wielomianowym, a następnie możesz wyrzucić wiele przypadków dla zmiennych binarnych, które i tak nigdy się nie sprawdzą. Następnie rozgałęziasz się na pozostałych opcjach.

Zauważ, że Rozgałęzienia i Związania zwykle dają ci tylko wzrost prędkości w praktyce, ale nie w teorii: trudno jest dokładnie powiedzieć, ile wycinanych drzewek wyszukiwania jest wycinanych za pomocą heurystyki. Świadczy o tym liczba różnych heurystyk stosowanych w praktyce w przypadku takich problemów. Jeśli masz pecha, pozostałe drzewo wyszukiwania pozostaje ogromne nawet przy dużym ograniczeniu.

Rozważ planowanie , zadanie polegające na przypisywaniu do maszyn zadań o określonym czasie trwania i terminie. Zakładamy dyskretny czas. Wiele takich problemów jest twardych NP (O).

W szczególności ta odpowiedź będzie mówić $1 \mid r_i \mid L_\max$, czyli planujemy

• na jednej maszynie
• problemy z datami wydania i my
• zminimalizuj maksymalną spóźnienie $L_\max$, to maksymalna różnica między terminem a czasem realizacji we wszystkich zleceniach.

Wersja decyzyjna tego problemu jest trudna NP; widać to po zmniejszeniu z 3PARTITION .

Co ciekawe, jeśli pozwolimy na prewencję , czyli zamianę aktywnych zadań, problem można rozwiązać w kwadratowym czasie przez heurystykę najwcześniejszej daty pierwszej (w zmodyfikowanych terminach). Łatwo zauważyć, że optymalne rozwiązanie tego wariantu nie może być gorsze niż optymalne rozwiązanie pierwotnego problemu.

Teraz, aby zastosować Branch & Bound do tego problemu, musimy naprawić niektóre parametry:

• Obliczamy dolne granice, umożliwiając prewencję i korzystanie z EDD.
• Rozgałęziamy się, ustalając każdą nieplanowaną pracę jako następną.
• Najpierw idziemy do dziecka z małymi dolnymi granicami.

Musisz to zrobić dla każdej aplikacji B & B.

Konkretnym przykładem jest ten przykład $1 \mid r_i \mid L_\max$:

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p_i & 4 & 2 & 6 & 5 \\ r_i & 0 & 1 & 3 & 5 \\ d_i & 8 & 12 & 11 & 10 \end{array}$

z $p_i$ czasy przetwarzania zleceń, $r_i$ daty wydania i $d_i$ terminy.

Wykonywanie B & B, jak określono powyżej, dzieje się tak:

_{Ten GIF nie zapętla się. Załaduj ponownie w nowej karcie, aby zobaczyć od początku.}
^{[ źródło ] [ wersja statyczna ]}

Zauważ, że z 41 węzłów tylko cztery są odwiedzane poprawnie, a tylko dla dziesięciu są obliczane dolne granice.