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

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

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 6 мес., 3 нед. назад.

  • Автор
    Сообщения
  • #2206

    questioner
    Участник

    Помогите улучшить алгоритм решения задачи о ранце на Prolog при помощи метода ветвей и границ.
    Метод ветвей и границ отсеивает варианты, для которых очевидна их неоптимальность. В результате часть ветвей дерева не обрабатывается.
    В ряде задач при этом используется некоторая эвристика — например в искусственном интеллекте, шахматах. Как применить такой метод к задаче о рюкзаке?

  • #2209

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

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

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

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

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

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

Для ответа в этой теме необходимо авторизоваться.