Ответ в теме: Задача о ранце методом ветвей и границ

      Комментарии к записи Ответ в теме: Задача о ранце методом ветвей и границ отключены
#2209

Метод ветвей и границ в отличии от полного перебора каждый предмет может быть добавлен или пропущен – каждая ситуация дает отдельный узел в дереве решения. На рисунке показано дерево решения, где красным цветом выделены дуги, отвечающие за пропуск узла, а черным – за его добавление.
Дерево поиска решения метода ветвей и границ
Большее дерево поиска решения метода ветвей и границ

В алгоритме полного перебора (поиска с возвратами) использовался поиск в глубину, однако метод ветвей и границ применяет поиск в ширину, сравнивая узлы, находящиеся на одном ярусе в дереве поиска. На основании результатов сравнения, некоторые узлы могут быть отброшены как неперспективные. Возможны различные алгоритмы определения перспективности, но в любом случае, они не дадут точного решения, т.к. используют эвристику.
Функции сравнения узлов называют граничными функциями. В задаче о рюкзаке граничные функции могут опираться лишь на объем и цену предметов уже уложенных в рюкзак и всех остальных предметов.
Предметы вне рюкзака удобно хранить упорядоченными по убыванию цены (ci), тогда граничная функция стоимости может быть записана следующим образом:
Граничная функция задачи о рюкзаке

Предметы для добавления в рюкзак выбираются в порядке уменьшения их стоимости до тех пор, пока ранец не заполнится.
PossibleWeight – это объем предметов, которые могут быть полностью помещены в рюкзак.
Граничная функция (costBound, граница стоимости) вычисляется как сумма предметов уже уложенных в рюкзак на предыдущих шагах (currentCost), суммы цен предметов, которые могут быть помещены в рюкзак целиком, а также стоимость части предмета, который полностью в рюкзак не поместился.

Добавление предмета считается неперспективным если его добавление:

  • приводит к превышению предельного размена мешка;
  • не приводит к улучшению наилучшей границы стоимости, найденной к текущему шагу.

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