Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 33

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 84 >> Следующая


I (z) > do + min cfk] + min eg.

кфз тфг J

Для каждого нулевого перехода может быть вычислена величина Oij = min + min с\g. (3.4.1)

ACt=J га^рг

Для вычисления Qij для нулевого перехода нужно найти минимальные элементы в строке и столбце, пересекающихся на этом переходе (минимумы находятся без учета рассматриваемого нулевого перехода (г, j)), и полученные минимумы сложить.

В качестве перехода, используемого для разветвления, выбирается тот, у которого значение Оц максимально, I (z) > do -\-0ц. Находим max Oij, и этот переход выбираем в качестве того, по которому про-

исходит разветвление. Это связано с тем, что необходимо получить по возможности большую оценку для множества (г, j). В нашем примере получаем

#14 = Ю, 024 = 1, 036 = 5, 041 = 1, 042 = 0, 056 = 2,

062 = 0, 063 = 9, 065 = 2. ___

Поэтому ветвление происходит по переходу (1,4), для ^ Є (1,4) получаем l(z) > 48 + 10 = 58, для ^ Є (1,4) оценка остается прежней: l(z) > 48 (рис. 3.7).

В матрице, соответствующей множеству G\ = (?, j), вычеркиваем

(2)

строку г и столбец j и положим Cji = М, чтобы предотвратить появление цикла і —> j —> і. Полученную матрицу можно привести; пусть
96

Разд. II. Комбинаторные методы решения задач

сумма констант приведения равна ао, тогда для z Є (г, j) получим

I (z) > do + ao.

В матрице, соответствующей множеству G\ = (?, j), следует положить C-f = M, И ДЛЯ Z Є (ijj) получим

I (z) > 6?o + •

Если эту матрицу привести и сумма констант приведения равна /Зо, то для Z Є (i,j) получаем

l(z) > б?о + + /Зо-

В нашем примере (г, j) = (1,4), поэтому в матрице, соответствующей множеству (1,4), вычеркиваем строку 1 и столбец 4 и полагаем С41 = = M. После этого выполняем процедуру приведения, при этом а?о = 1, l(z) > 48 + 1 = 49. В матрице, соответствующей множеству (1,4), полагаем с 14 = М, l(z) > 48 + 10 = 58. После выполнения процедуры приведения Po = 10 и l(z) > 58 + 10 = 68. В данном примере

в соответствии с правилами отсева множество (1,4) можно отбросить, т.е. исключить из дальнейшего рассмотрения. Это означает, что в оптимальном решении задачи обязательно содержится переход (1,4). После реализации отсева получим дерево ветвления в виде рис. 3.8.

3.4.4. Общий шаг алгоритма. 1) Среди неотсеянных по правилам отсева множеств, не подвергавшихся разбиению, выбираем множество Gtv с наименьшей нижней оценкой dy.

2) В матрице (7, соответствующей выбранному множеству, для всех CsI = 0 определяем константы 0si по формуле (3.4.1) и определяем Okp = шах в si.

Csl= О

3) Разбиваем множество Gtv на два подмножества по правилу z Є Є (к,р) и z Є (к,р). В матрице, соответствующей множеству (к,р), запрещаем переход (к,р), т.е. полагаем скр = М. Полученную матрицу расстояний приводим. Если сумма констант приведения равна /Зу, то для z Є (к,р) получаем оценку

I (z) > dy + Okp + /3у. (3.4.2)

В матрице, соответствующей множеству (&,р), вычеркиваем строку к и столбец р и реализуем алгоритм запрещения под циклов. Нужно рассмотреть все связные пути вида х\, X2,..., хг, которые образованы входящими ребрами, и положить cXrXs = M для s = 1,2,...,г — 1. Полученную матрицу приводим. Если сумма констант приведения равна Qttv, то для z Є (к,р) получаем оценку

I (z) > dy + ay. (3.4.3)
Гл. 3. Метод ветвей и границ

97

4) Модифицируем список множеств, не подвергавшихся разбиению. Вместо множества Gtv записываем множества (к,р) и (к,р) и полученные множества переобозначаем: G^+1, G^+1,..., Gt7^h • Удаляем (или отмечаем) множества, отсеянные по правилам отсева, и переходим к п. 1, положив t равным t + 1.

В результате применения описанного общего шага получаем дерево ветвления в виде рис. 3.9.

Рис. 3.9

Здесь описаны правила ветвления и вычисления оценок. Все остальные элементы алгоритма реализуются по общей схеме из параграфа 3.1. Процесс вычисления завершается после отсева по правилам отсева всех множеств, не подвергавшихся разбиению.

Как уже многократно отмечалось, трудоемкость алгоритма определяется числом решенных оценочных задач. В описанном алгоритме решение оценочной задачи сводится к процедуре приведения матрицы расстояний. Экономная ее реализация может существенно сократить время решения задачи.

Остановимся на некоторых простых правилах, позволяющих уменьшить время работы процедуры.

1. При определении очередного значения константы приведения вычитание ее из элементов строки или столбца производится, если константа положительная и ее прибавление к оценке не приводит к отсеву подзадачи. Если прибавление положительной константы приводит к отсеву подзадачи, то выполнение процедуры приведения прекращается.

2. Реализацию процедуры приведения целесообразно начинать со строк (или столбцов), в которых появились числа M при ветвлении подзадачи на две. Появление чисел M в строках или столбцах, как правило, дает ненулевые значения констант приведения, при этом увеличиваются значения оценок.

7 И.Х. Сигал, А.П. Иванова
98

Разд. II. Комбинаторные методы решения задач
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100