Алгоритм - ветвь
Cтраница 3
 |
Окно программы BandB. [31] |
На рис. 8.5 изображено окно программы BandB после решения задачи о формировании портфеля с двадцатью элементами. В данном случае алгоритм ветвей и границ нашел лучшее решение после исследования всего 1613 из более 2 млн узлов дерева. [32]
Перейдем к описанию уже собственно алгоритма ветвей и границ, а именно, определим вычисление границ - вторую компоненту ( ветвление уже описано) алгоритма. [33]
Нахождение точного решения задачи с применением алгоритма ветвей и границ требует значительных вычислительных ресурсов. При этом для хранения информации о дереве ветвления может потребоваться большой объем памяти. Отметим также, что в процессе работы алгоритма на каждом шаге процесса ветвления известна оценка отклонения приближенного решения ( рекорда) от оптимума. Интуитивно представляются естественными следующие предположения. Если алгоритм ориентировать с самого начала на нахождение е-приближенных решений, то это может привести к усилению отсева. При этом сократится информация о дереве ветвления и уменьшится число решаемых подзадач. [34]
Эти экспериментальные данные показывают, что, прежде чем пытаться найти оптимальное решение с помощью метода ветвей и границ, следует найти хорошее субоптимальное решение. DB совместно с хорошим начальным решением, дающим верхнюю оценку, существенно уменьшает объем вычислений, и если алгоритм ветвей и границ превышает заданные предельные значения объема памяти и времени счета, то, тем не менее, известное решение, дающее верхнюю оценку, и наименьшая нижняя оценка, взятая по активным вершинам, позволяют с хорошей точностью оценить степень близости полученного решения к оптимальному. [35]
Идея заключается в том, чтобы осуществлять перебор эффективно, используя при этом как можно больше информации для сокращения дерева поиска. Здесь мы обсудим общую схему такого перебора с возвратом, включающую все, что в литературе обычно называют алгоритмами ветвей и границ. [36]
Этапы выполнения алгоритма BBFLDs представлены в табл. 6.4. То обстоятельство, что в качестве примера также взято дерево, изображенное на рис. 6.13, позволяет сравнить эти этапы с этапами метода динамического программирования, представленными в табл. 6.3. Это сравнение показывает, что генерируются и исключаются одни и те же вершины, кроме последнего шага, на котором выполнение BBFLDs завершается нахождением решения 1234 и проверкой его оптимальности. Единственное существенное различие состоит в том, что алгоритм динамического программирования генерирует все необходимые вершины на каждом уровне дерева до объединения и исключения, в то время как в алгоритме ветвей и границ каждая новая вершина проверяется сразу после ее генерирования. [37]
Иногда даже алгоритм ветвей и границ не может полностью перебрать дерево решения. Дерево для задачи о формировании портфеля с 65 элементами содержит более 7 101S узлов. Если алгоритм ветвей и границ перебирает только десятую часть процента этих узлов, а компьютер проверяет - МИЛЛИ01Г узлов в секунду, то потребовалось бы более 2 млн лет, чтобы решить эту задачу. [38]
Целочисленные алгоритмы, описанные в гл. В этом приложении мы обсудим другой подход, который может быть назван методом дерева поиска. Сюда относятся алгоритм ветвей и границ ( Лэнд и Дойг [139], Литтл и др. [144]), аддитивный алгоритм ( Балаш [4], Бил и Смол [14]), алгоритм прямого поиска ( Лемке и Шпильберг [143]) и многие другие. [39]
В главе 9 предпринимается попытка выделить параметры, характеризующие задачу большой размерности. Построена вычислительная модель решения задач этого типа. Показано, что применение алгоритма ветвей и границ в рамках построенной модели позволяет выделить основной параметр, характеризующий задачу большой размерности. Этим параметром является отношение трудоемкости вычисления оценки к трудоемкости вычисления значения функции. При выделенном вычислительном ресурсе определены области изменения этого параметра, зависящие от ресурса, для задач большой размерности и задач, не являющихся таковыми. Выделение этого параметра может быть основой для параметризации задачи большой размерности. [40]
Следовательно, необходим дополнительный анализ решаемых задач для получения дополнительной информации. По мере уменьшения мощности отбрасываемых множеств алгоритм ветвей и границ стремится к полному перебору, п таким образом значительно ухудшается его сходимость. [41]
В главе 4 рассматривается применение алгоритма динамического программирования для решения некоторых аддитивных задач. В пособии не ставится цель изложить методологические вопросы, связанные с общими схемами динамического программирования: этому посвящена обширная литература. Применение алгоритмов демонстрируется на задаче о ранце, для этой задачи приведено сравнение алгоритма ветвей и границ и динамического программирования. [42]
Заметим, что в этом примере при преобразовании ( 4) теряется некоторая информация. Это связано со следующим обстоятельством: формально допускается возможность wi IT. Читателю следует сформулировать общее правило выбора коэффициента при гг.. Напомним, что в случае применения алгоритма ветвей п границ, приведенного в разд. [43]
Строится первая матрица ветвления, производится ее приведение и сумма констант приведения суммируется к уже имевшейся нижней границе ( равной 48), что дает 56 как нижнюю границу стоимости любого тура в данной подзадаче. Ветвь не имеет смысла исследовать, если нижняя граница для туров в данной подзадаче превышает стоимость наилучшего тура, найденного в данный момент. Следовательно, это и есть искомый тур задачи. Рассмотренный пример хорошо показывает, как много вариантов в ряде случаев удается исключить из рассмотрения. Алгоритмы ветвей и границ являются одним из наиболее эффективных методов решения ряда переборных задач. Как правило, эти алгоритмы сложны для понимания, но выигрыш, получаемый в результате их применения, стоит тех усилий, которые приходится затрачивать либо на разработку собственного подобного алгоритма, либо на понимание предлагаемого готового алгоритма. [44]
Когда я Ояг, то говорят, что я ( / доминирует над яг. Обычно предполагают, что D определено так, чтобы содержать по крайней мере все пары nf / Dn. При использовании алгоритма ветвей и границ пары вида ( я, лг) проверяются на предмет принадлежности к D. Следовательно, при выборе отношения D обычно приходится идти на компромисс между сильным отношением и таким, принадлежность к которому легко проверяется. [45]
Страницы: 1 2 3 4