Cтраница 1
Функция нижней оценки, которая ставит в соответствие каждому частичному решению нижнюю оценку его стоимости, служащую оценкой всех полных решений, получаемых из данного частичного решения. [1]
А) для потомка с минимальной стоимостью, и такой функцией нижней оценки, которая была бы легко вычислимой. [2]
Следующие теоремы показывают, каким образом изменяются потребности в вычислительных ресурсах при улучшении функции нижней оценки и начального решения, дающего верхнюю оценку. [3]
Следующая теорема показывает, что, когда 5LLB или SDF / LLB, при улучшении функции нижней оценки может произойти возрастание требований к вычислительным ресурсам. Такая ситуация возможна, однако в большинстве случаев все же следует ожидать уменьшения потребностей. [4]
Для решения Т - задачи необходимо определить алгоритм перечислений tp, операцию сокращения гр, функцию нижней оценки Фо и алгоритм начального разбиения во. [5]
Это является результатом применения хорошего решения, дающего верхнюю оценку, и хорошей границы, вычисляемой с помощью функции нижней оценки L. Когда заданная степень точности устанавливается близкой к 0 01, то среднее количество затрачиваемых вычислительных ресурсов незначительно отличается от того, какое необходимо для получения оптимального решения, поскольку в этом случае оба способа обычно превышают заданные предельные значения вычислительных ресурсов. Однако в тех случаях, когда этого не происходит, достигается экономия. [6]
Теорема 6.4. ( При использовании правил выбора FIFO или LIFO потребности в вычислительных ресурсах не увеличиваются при использовании более точной / функции нижней оценки и улучшенного начального решения, дающего верхнюю оценку. [7]
Алгоритм ветвей и границ без возвратов всегда генерирует п ( п - 2) / 2 - j - l вершни, для каждой из которых необходимо вычислять функцию нижней оценки; следовательно, время счета растет приблизительно как пл. [8]
Формальное доказательство этой теоремы приводится методом индукции так же, как в теореме 6.1. Заметим, что поскольку 5 FIFO или 5 LIFO, то порядок ветвления одинаков для ВВ1 и ВВа, так как он не зависит от функции нижней оценки. [9]
Выбирается та текущая активная вершина, которая была порождена первой. Этот метод поиска в ширину не зависит от функции нижней оценки L. [10]
В случае, когда несколько вершин оказываются равноправными по этому критерию, то выбирается либо первая порожденная вершина, ( LLBFIFO), либо последняя, ( LLBL. В обоих случаях порядок, в котором вершины подвергаются ветвлению, определяется функцией нижней оценки L. [11]