Cтраница 3
При реализации алгоритма используется схема ветвления, описанная выше. Ветвление осуществляется по двум множествам переменных: X xrv; г 1, R, v 1, V иУ yif, I 1, L, f 1, F, каждое из которых образует дерево ветвления Р и Q соответственно. [31]
Нахождение точного решения задачи с применением алгоритма ветвей и границ требует значительных вычислительных ресурсов. При этом для хранения информации о дереве ветвления может потребоваться большой объем памяти. Отметим также, что в процессе работы алгоритма на каждом шаге процесса ветвления известна оценка отклонения приближенного решения ( рекорда) от оптимума. Интуитивно представляются естественными следующие предположения. Если алгоритм ориентировать с самого начала на нахождение е-приближенных решений, то это может привести к усилению отсева. При этом сократится информация о дереве ветвления и уменьшится число решаемых подзадач. [32]
Глобальные подходы повышения эффективности следует искать путем перехода от поиска точного решения к е-оптимизации. Рассмотрим задачу о ранце. Основной результат для этой задачи состоит в том, что переход к е-оптимизации переводит задачу о ранце из класса NP в класс Р, т.е. при е-оптимизации наблюдается полиномиальный рост числа вершин дерева ветвления. Вычислительная реализация алгоритма подобного типа не представляется тривиальной. [33]
Нахождение точного решения задачи с применением алгоритма ветвей и границ требует значительных вычислительных ресурсов. При этом для хранения информации о дереве ветвления может потребоваться большой объем памяти. Отметим также, что в процессе работы алгоритма на каждом шаге процесса ветвления известна оценка отклонения приближенного решения ( рекорда) от оптимума. Интуитивно представляются естественными следующие предположения. Если алгоритм ориентировать с самого начала на нахождение е-приближенных решений, то это может привести к усилению отсева. При этом сократится информация о дереве ветвления и уменьшится число решаемых подзадач. [34]
Четыре варианта с суммой 15 дают, соответственно, 2315 9, 1915 4, 2415 9, 19 15 4, что больше минимального. В [2] приведен несколько иной способ решения этой же задачи методом ветвей и границ. Там 24 варианта делились на 4 ветви, у каждой ветви первым из ресурсных этапов выполняется ресурсный этап одной и той же работы. Каждая из этих 4 - х ветвей имеет, в свою очередь, 3 ветви, ветвление тут происходит по номеру ресурсного этапа, выполняемым вторым. Каждая из этих 3 - х ветвей имеет 2 ветви, ветвление тут происходит по номеру ресурсного этапа, выполняемым третьим. Отсечение проводилось по оценке снизу, а именно по сумме начала и конца, описанной выше. Самое сложное в методе ветвей и границ с использованием оценок ( сверху при поиске максимума и снизу при поиске минимума) это найти оценку для дальнейшего отсечения, а дерево ветвления придумать легче. [35]