Алгоритм - ветвь
Cтраница 1
Алгоритмы ветвей и границ можно применять для решения разнообразных дискретных задач оптимизации; они являются алгоритмами направленного перебора допустимых решений и в отличие от точных методов полного перебора обычно обеспечивают получение оптимального варианта за реально реализуемое число шагов. Так как V / ограничено сверху технологическими пли организационными условиями, а У /, V / могут быть выбраны только из стандартных рядов, число возможных состояний каждой стадии конечно, а следовательно, конечно, хотя и очень велико, число вариантов синтезируемой ХТС. Обычно набор решений ( вариантов ХТС) удобно представить в виде дерева ( рис. 3.20), где уровни иерархии соответствуют аппаратурным стадиям ХТС, вершины - вариантам аппаратурного оформления ХТС. [1]
Алгоритм ветвей и границ основан на следующих построениях, позволяющих уменьшить объем перебора. [2]
Алгоритм ветвей и границ позволяет решить любую задачу о многомерном ( одномерном) ранце как при целых, так и при действительных значениях параметров задачи. Алгоритм динамического программирования решает задачу об одномерном ранце лишь с целочисленными значениями параметров. [3]
Алгоритм ветвей и границ позволяет, по крайней мере теоретически, решить любую задачу о ранце с любой заранее заданной оценкой точности. Алгоритм динамического программирования направлен на нахождение точного решения задачи об одномерном ранце с целочисленными значениями параметров. [4]
Алгоритмы ветвей и границ, как и большая часть алгоритмов, описанных ранее, применяются для решения переборных задач. В целях упрощения понимания сути алгоритмов такого рода рассмотрим одну конкретную задачу, в которой такой алгоритм весьма хорошо работает и достаточно прост в понимании. [5]
Алгоритм ветвей и границ без возвратов всегда генерирует п ( п - 2) / 2 - j - l вершни, для каждой из которых необходимо вычислять функцию нижней оценки; следовательно, время счета растет приблизительно как пл. [6]
Примените алгоритм ветвей и границ, изложенный в разд. Постройте дерево работы алгоритма, аналогичное дереву, изображенному на рис. 13.1. Для решения задач большой размерности можно использовать алгоритм с переменными, ограниченными сверху ( с двусторонним ограничением), описанный в разд. [7]
Эффективность алгоритма ветвей и границ определяется числом решенных задач. Решение задачи состоит из двух основных этапов. На втором этапе производится доказательство оптимальности полученного решения. Второй этап, как правило, оказывается более трудоемким, чем первый. Это означает, что число подзадач, решаемых до получения оптимума, может оказаться существенно меньше числа подзадач, решаемых для доказательства оптимальности. [8]
 |
Число исследуемых узлов при полном переборе и переборе по методу ветвей и границ. [9] |
Иногда даже алгоритм ветвей и границ не может полностью перебрать дерево решения. Дерево для задачи о формировании портфеля с 65 элементами содержит более 7 101S узлов. Если алгоритм ветвей и границ перебирает только десятую часть процента этих узлов, а компьютер проверяет - МИЛЛИ01Г узлов в секунду, то потребовалось бы более 2 млн лет, чтобы решить эту задачу. [10]
 |
Дерево решений для метода ветвей и границ. [11] |
К недостаткам алгоритма ветвей и границ относится его медленная сходимость, особенно когда продолжительность технологического цикла аппаратов периодического действия является функцией массового размера партии продукта. [12]
Исследуйте применение алгоритма ветвей п границ к примеру ( 8), ( 9) из разд. Проследите подробно все вычисления, выполняемые на каждой итерации. В частности, покажите, что решения в ( 11), ( 13), ( 15), ( 17), ( 19) и ( 20) оптимальны. Покажите, что задачи 2, 6 и 8 не имеют допустимого решения. [13]
Лемма 6.3. ( Алгоритм ветвей и границ всегда дает нижнюю оценку стоимости оптимального решения; если известно некоторое полное решение, то он также дает величину отклонения стоимости этого решения от оптимальной. [14]
Еще один пример: алгоритмы ветвей и границ успешно решают задачу о рюкзаке и поэтому многие исследователи считают ее хорошо решаемой, хотя алгоритмы ветвей и границ имеют экспоненциальную оценку сложности. Приведенные примеры хорошего поведения экспоненциальных алгоритмов, достаточно редки, поэтому хотя экспоненциальные алгоритмы известны для многих задач, немногие из них можно использовать для практических целей. [15]
Страницы: 1 2 3 4