Рубрики

Рюкзак 0/1 с использованием Branch and Bound

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

Рассмотрим ниже задачу о ранце 0/1, чтобы понять ветвление и границу.

Даны два целочисленных массива val [0..n-1] и wt [0..n-1], которые представляют значения и веса, связанные с n элементами соответственно. Найдите максимальное значение подмножества val [], чтобы сумма весов этого подмножества была меньше или равна вместимости рюкзака W.

Давайте рассмотрим все подходы к этой проблеме.

  1. Жадный подход заключается в выборе предметов в порядке убывания стоимости на единицу веса. Подход Greedy работает только для дробной задачи о ранце и может не дать правильного результата для ранца 0/1 .
  2. Мы можем использовать D инамической P rogramming (DP) для 0/1 задачи о рюкзаке . В DP мы используем 2D-таблицу размером nx W. Решение DP не работает, если веса элементов не являются целыми числами .
  3. Поскольку решение DP не всегда работает, решение заключается в использовании Brute Force . Для n элементов необходимо сгенерировать 2 n решений, проверьте каждое, чтобы убедиться, что они удовлетворяют ограничению, за исключением максимального решения, которое удовлетворяет ограничению. Это решение может быть выражено в виде дерева .

  4. Мы можем использовать Backtracking для оптимизации решения Brute Force. В представлении дерева мы можем сделать DFS дерева. Если мы достигаем точки, когда решение более неосуществимо, нет необходимости продолжать изучение. В данном примере возврат будет намного эффективнее, если бы у нас было еще больше предметов или меньший объем рюкзака.

Ветвь и Связка

Решение на основе обратного отслеживания работает лучше, чем грубая сила, игнорируя невыполнимые решения. Мы можем добиться большего успеха (чем возврат), если мы знаем границы поддерева наилучшего решения, укорененного с каждым узлом. Если лучшее в поддереве хуже текущего лучшего, мы можем просто проигнорировать этот узел и его поддеревья. Таким образом, мы вычисляем оценку (лучшее решение) для каждого узла и сравниваем границу с текущим наилучшим решением, прежде чем исследовать узел.

Ниже приведены примеры границ, приведенных ниже: А вниз может дать 315 долларов, В вниз может 275 долларов, С снизится на 225 долларов, D снизится на 125 долларов и E снизится на 30 долларов. В следующей статье мы обсудили процесс получения этих границ.

Ветвление и граница — очень полезный метод для поиска решения, но в худшем случае нам нужно полностью рассчитать все дерево. В лучшем случае нам нужно только полностью рассчитать один путь через дерево и обрезать остальную часть.

Источник:
Выше изображения и содержание принимается по следующей приятной ссылке. http://www.cse.msu.edu/~torng/Classes/Archives/cse830.03fall/Lectures/Lecture11.ppt

Ветвь и Связанный | Набор 2 (реализация рюкзака 0/1)

Эта статья предоставлена Уткарш Триведи. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Рюкзак 0/1 с использованием Branch and Bound

0.00 (0%) 0 votes