Строится первая матрица ветвления, производится ее приведение и сумма констант приведения суммируется к уже имевшейся ... - Большая Энциклопедия Нефти и Газа
Строится первая матрица ветвления, производится ее приведение и сумма констант приведения суммируется к уже имевшейся нижней границе ( равной 48), что дает 56 как нижнюю границу стоимости любого тура в данной подзадаче. Ветвь не имеет смысла исследовать, если нижняя граница для туров в данной подзадаче превышает стоимость наилучшего тура, найденного в данный момент. Следовательно, это и есть искомый тур задачи. Рассмотренный пример хорошо показывает, как много вариантов в ряде случаев удается исключить из рассмотрения. Алгоритмы ветвей и границ являются одним из наиболее эффективных методов решения ряда переборных задач. Как правило, эти алгоритмы сложны для понимания, но выигрыш, получаемый в результате их применения, стоит тех усилий, которые приходится затрачивать либо на разработку собственного подобного алгоритма, либо на понимание предлагаемого готового алгоритма.
