Исследование алгоритма перебора вариантов с отсечением

[Baralgin91]

Здравствуйте всем!!
как должен работать перебор вариантов с отсечением ??


я непонимаю, расскажите пожалуйста как это происходит.

спасибо заранее за ваши ответы!

[sabbathist]

скорее всего это рекурсия, где указаны доп. условия для выхода, не достигая ее дна.
Например: есть сетка NхN, куда вписаны числа от 1 до 100. Необходимо найти путь с максимальной суммой из левого верхнего угла в правый нижний. можно переходить только вниз либо в право. тогда, запуская dfs, можно найти какой либо путь с какой-либо суммой. суть в том, что если текущая сумма меньше максимальной более чем на tх100, где t - количество оставшихся клеток, путь по которым мы можем достроить, то дальше идти по этой ветви нет смысла. вот и отсечение. в случае же простого полного перебора, необходимо было проходить весь путь, и только потом смотреть его сумму и сравнивать с текущим максимумом. Доступно?

[PSix1_73]

А можно ли реализовать венгерский алгоритм (если кто знаком, если нет это задачи о назначениях) при помощи перебора вариантов с отсечением, программа же будет более производительной нежеле чем при полном переборе!

[Baralgin91]

да спасибо большое, теперь боле-менее понятно что делать