Ветвь и Связанное объяснение

У меня есть тест на ветвь и связанный алгоритм. Я теоретически понимаю, как работает этот алгоритм, но я не смог найти примеров, иллюстрирующих, как этот алгоритм может быть реализован практически.

Я нашел несколько примеров, таких как этот, но я все еще смущен этим. Я также искал проблему коммивояжера и не мог ее понять.

Что мне нужно, так это некоторые проблемы и как можно решить эти проблемы с помощью ветвления и привязки.

Давайте применим Branch и Bound к ранцу , надеюсь, это прояснит вам концепцию.

$n$$1$$n$$v_i$$i$$w_i$$T$

$v_1$$n-1$$v_1$$n-1$

$i$$i$$n$$O(2^n)$

$T$$n/2$$n/2+1$$n$$n/2+1$$n$$2^{n/2}$

$d$$O(2^d)$

Обратите внимание, что это называется « Ограничение », потому что обычно оно включает в себя некоторую нижнюю или верхнюю границу: для критерия « даже если я добавлю все оставшиеся элементы, стоимость элементов, которые я вставил, не будет превышать лучшую конфигурацию». До сих пор я обнаружил , что «ценность вашей лучшей конфигурации на данный момент - это нижняя граница для лучшей конфигурации, поэтому все, что никогда не пройдет через эту нижнюю границу, обречено на провал».

Вы можете сделать «Ограничивающую» часть настолько сложной, насколько захотите. Например, задачи целочисленного программирования часто решаются с помощью релаксаций: вы переводите вашу программу в линейную программу, которую вы можете решить за полиномиальное время, а затем вы можете отбросить множество случаев для ваших двоичных переменных, которые никогда не сработают. Затем вы переходите на остальные варианты.

Обратите внимание, что Branch and Bound обычно дает вам только увеличение скорости на практике, но не в теории: трудно сказать, сколько именно дерева поиска вырезано с использованием вашей эвристики. Об этом свидетельствует количество различных эвристик, используемых на практике для решения таких задач. Если вам не повезло, оставшееся дерево поиска остается огромным, даже с большим количеством ограничений.

Рассмотрите планирование , задачу назначения заданий с определенной продолжительностью и сроками для машин. Мы предполагаем дискретное время. Многие такие проблемы являются NP (O) -hard.

$1 \mid r_i \mid L_\max$

• на одной машине
• проблемы с датами выпуска и мы
• минимизировать максимальную задержку , то есть максимальную разницу между крайним сроком и временем завершения для всех заданий.$L_\max$

Версия решения этой проблемы NP-трудна; это можно увидеть по сокращению от 3PARTITION .

Интересно, что если мы допустим приоритетное вытеснение , то есть замену активных заданий, проблема может быть решена за квадратичное время с помощью эвристики «Самый ранний срок исполнения» («Измененные сроки исполнения»). Нетрудно видеть, что оптимальное решение этого варианта может быть не хуже оптимального решения исходной задачи.

Теперь, чтобы применить Branch & Bound к этой проблеме, нам нужно исправить некоторые параметры:

• Мы вычисляем нижние границы, допуская приоритет и используя EDD.
• Мы осуществляем ветвление, исправляя каждую из незапланированных работ как следующую.
• Сначала мы идем к ребенку с нижней границей.

Вы должны сделать это для каждого приложения B & B.

Для конкретного примера рассмотрим этот экземпляр :$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}$

с время обработки заданий, даты выпуска и сроки исполнения.$p_i$$r_i$$d_i$

При выполнении B & B, как указано выше, это происходит:

_{Этот GIF не зацикливается. Перезагрузите его в новой вкладке, чтобы увидеть с самого начала.}
^{[ источник ] [ статическая версия ]}

Обратите внимание, что из 41 узла только четыре посещаются правильно, и только для десяти рассчитываются нижние границы.