Дерево - ветвление
Cтраница 2
Выбор множества ( подзадачи) для ветвления производится из множества неотсеянных концевых на дереве ветвления ( активных) подзадач. [16]
Но такой способ поиска обладает, по крайней мере, двумя существенными недостатками: быстрым ростом дерева ветвлений и медленной генерацией допустимых решений. Последнее свойство особенно нежелательно для приближенных методов. [17]
Производится расширение множества фиксированных переменных xrv выбранного варианта частичного решения и образование новых вариантов следующего уровня дерева ветвления в соответствии с принятой схемой ветвления. [18]
Вычислительный опыт показывает, что при решении симметричных задач возникают большие трудности, которые связаны с тем, что дерево ветвления имеет большое число вершин. Для симметричных задач разработан другой алгоритм, который будет рассмотрен далее. [19]
В ВВС, начиная с исходной задачи Р ( 0), разбиения проводятся таким образом, чтобы множества Nx в процессе движения в глубь по дереву ветвлений формировались последовательно. [20]
 |
Дерево ветвлений с последовательной нумерацией вершин. [21] |
Из выполнения при каждом ветвлении условий (5.7) следует, что на любом этапе работы G ( 0) jGj, где операция объединения выполняется по всем висячим вершинам дерева ветвлений. [22]
Ветвление производится одновременно по двум множествам пере-менных X xrv ( v 1, V r 1, R) и Z гц ( I - 1, L; / 1, F) t образующих два дерева ветвления: Р и Q соответственно. [23]
Все вершины дерева ветвления распределены по уровням. Начальная ( корневая) вершина соответствует исходной задаче и находится на первом уровне дерева. Задачи, которые получаются при разбиении исходной задачи на подзадачи, находятся на втором уровне дерева. [24]
Для сокращения времени счета и объема требуемой оперативной памяти предлагается использовать следующую стратегию движения к оптимуму. Первоначальное движение по дереву ветвления осуществляется из вершины с минимаксной оценкой. Одновременно запоминается оценка, ближайшая к минимаксной, которая играет роль рекорда. Если на / х-м шаге ветвления, соответствующем выбранному направлению, все оценки окажутся хуже рекорда, то за исходную точку ветвления принимается вершина с оценкой, равной рекорду, а из множества остальных выбирается ближайшая к лучшей, и процедура повторяется в новом направлении. [25]
Под методом ветвей и границ понимается алгоритм решения задачи, имеющий древовидную структуру поиска оптимального решения и использующий результаты решения оценочных задач. Древовидная структура называется обычно деревом ветвления. [26]
Здесь описаны лишь три пункта общей схемы: ветвление, вычисление оценок, правило отсева. Монотонное возрастание значений оценок по ветвям дерева ветвления, т.е. выполнение условия (3.1.2), очевидно. Все шаги алгоритма, не описанные в этом параграфе, реализуются в соответствии с общей схемой из параграфа 3.1 этой главы. [27]
Вершины на каждом из уровней получают номера в порядке их возникновения на дереве ветвления. Для ветвления выбирается концевая неотсеянная вершина, для которой вычислена оценка. [28]
Эффективность алгоритма ветвей и границ при решении задач дискретного программирования оценивается числом решенных подзадач, т.е. числом вершин в дереве ветвления. [29]
Остановимся подробнее на некоторых других операциях, выполнение которых может быть существенно упрощено при применении описанного способа организации информации о дереве подзадач. Эти операции можно выполнить при помощи просмотра всей информации о дереве, но это не представляется возможным при многократном просмотре дерева ветвления. [30]
Страницы: 1 2 3