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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 71 72 73 74 75 76 < 77 > 78 79 80 81 82 83 .. 84 >> Следующая


/^s ^ 2(n S^min)^maxj 2 S к 1,

/г —1 к — 1

^ ^ /? ^ 2nmax ^ ^ (?? S^min) — s=2 5=2

-О ( (U o^ (Ar — 2) (А: + 1)Л _

— 2nmax I п [к 2) ^min 2 J —

= 2nmax (к -2) (п- TimilJj .

к-1

Пусть nmax = птт + Пі. Поскольку kmin < п, то ^ fis = О (n2),

s=2

к-1

и получаем окончательную оценку T= /? = О (^2).

S=I

При построении начального решения открытой задачи в координатной форме для агрегатов подмножеств используется также комбинированный алгоритм типа ветвей и границ. Начальная последовательность агрегатов для задачи в координатной форме может быть задана в режиме диалога.

10.4.2. Улучшение последовательности подмножеств. Для

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

10.4.3. Формирование решений. Пусть p[r\ P^rJ ..., PnJ —

приближенные решения задач коммивояжера для подмножеств S[r\

,..., Snr на максимальном уровне г = rmax (для задачи в матричной форме rmax = 1). По описанному в п. 10.4.1. алгоритму найдем последовательность, в которой объединяются решения подзадач в указанной последовательности на уровне г = rmax.

В процессе объединения возможно улучшение полученных частичных решений по алгоритмам, описанным в п. 10.3.2. Если rmax =
Гл. 10. Алгоритмы решения задачи коммивояжера 219

= 1, то процесс объединения окончен, если rmax > 1, то, полагая г равным г — 1, продолжаем процесс объединения; на уровне г — 1 уже известно решение задачи для агрегатов (это решение для точек на уровне г).

Процесс объединения завершается после его окончания на уровне г = I. К полученным решениям задач коммивояжера на всех уровнях для агрегатов и подмножеств могут применяться алгоритмы устранения пересечений и улучшения решений.

Показано (см. п. 10.4.4), что трудоемкость процедуры объединения максимальна, если число точек в каждом из подмножеств равно п/к. При этом на уровне г = 1 должно быть вычислено 2п2(1 — 1/к) значений Cij.

10.4.4. Алгоритм объединения решений подзадач и оценка его трудоемкости. Пусть Pi, P2, • • • , Pk — приближенные решения подзадач (замкнутые маршруты) для подмножеств Si, S2,..., Sk; Ci — длины маршрутов P^. Объединение подмножеств выполняется в указанной последовательности: маршрут Pi объединяется с маршрутом P2; полученный в результате объединения маршрут объединяется с Рз, и т.д. Опишем алгоритм объединения Pi и P2. Пусть Pi = (іі,г2,... ,г*.,г}), Р2 = (?!,?!? • • • JbiD-уДалим из Цикла Pi звено (ij,ij+i) с длиной с(і\,і\+1) и звено (г|,г|+1) с длиной с(г|,г|+1) из цикла P2 и заменим их звеньями (г*, г|) и (г|+1, г*+1) соответственно. В результате такой процедуры из двух циклов Pi и P2 получится один цикл, длина которого /(Pi, P2) может быть определена следующим образом:

I(PitPz) = C1 + C2 - с -с(г42,г?+1) + с(і],%) + с (г*+1,г*+1) .

Вычислим Zo(-Plj Лг) — минимум Z(Pi, P2) по четырем указанным звеньям и объединим циклы Pi и P2 в один в соответствии с этим минимумом. Полученный ЦИКЛ Pi2 С ДЛИНОЙ Zo(Pi, P2) объединим С Рз и т.д.

Остановимся на трудоемкости алгоритма объединения решений замкнутых подзадач для подмножеств в решение замкнутой задачи для объединения подмножеств. Пусть множество S, состоящее из п точек, разбито на к непересекающихся подмножеств Si, S2,..., S^, \Si\ = к

= Xi] г = 1,2,...,&, Y хг — п• Объединение двух замкнутых маршів 1

рутов для подмножеств Si и Sj в один замкнутый маршрут имеет трудоемкость порядка Xi Xj применений процедуры объединения. Поэтому при объединении всех маршрутов в один общая трудоемкость f(x 1, ж2,..., Xk) может быть оценена следующим образом:
220

Разд. IV. Задачи большой размерности

/ (X1,X2, ...,Xk)= X1X2 + (X1 + X2) X3 + . . .

к — 1 к

. . . + (X1 + X2 + ... + Xh--J Xk = Y E XiXi •

і=I j=i+l

Для оценки трудоемкости рассмотрим следующую задачу:

к — I А;

E E —>• max,

i=lj=i+l

к

Xj = п, 0 < Xj < п целые, j = I, 2,..., fc.

j=i

Легко видеть, что A; —I А;

E E

*=i j=j+1

Е*П-

І= 1

Ежм -Еж?

г=1 / г=1

Отбросив условие целочисленности, составим функцию Лагранжа L (X1,X2,...,хк,X) = Mn2 -Ежі ) +А (Exi _п ) •

Необходимое условие экстремума дает = — Xj + Л = 0, Xj =A = Отсюда следует оценка трудоемкости

max. f (X1,X2,...,хк) = і ^n2 -Ex^ = Y (1_ l) ¦

Эта оценка верна, если п делится на к, в этом случае можно отбросить условие целочисленности. Если п не делится на к, то рассмотрим допустимое целочисленное решение

« = “ = «(ї) = І-*(І)-

і = I, 2,..., s; Xj = a + I; j = s + I,..., к,

где s = к (а + 1)— п, е и /3 — целая и дробная части n/fc соответственно, 0 < /3 < 1. Тогда получим

/ (жі,ж2) • • • ,?) = і [n2 + fca(a + I) - n (2а + 1)] =

(‘-їН^-фїИ'-їН

Поэтому оценка для оптимального целочисленного решения имеет вид
Гл. 10. Алгоритмы решения задачи коммивояжера 221
Предыдущая << 1 .. 71 72 73 74 75 76 < 77 > 78 79 80 81 82 83 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100