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

 

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

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

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


В результате получаем приближенное решение, удовлетворяющее следующим необходимым условиям оптимальности на плоскости:

в маршруте отсутствуют пересечения переходов;

точки выпуклой оболочки обходятся без возвратных движений.

10.3.2. Улучшение начальных решений. Для улучшения начальных решений используются комбинированные алгоритмы локальной оптимизации, описанные в гл. 7. Комбинированный алгоритм состоит из следующих алгоритмов:

— оптимизация по перестановкам пар точек в маршруте;

— оптимизация по всем перестановкам заданного числа подряд расположенных точек маршрута;

— оптимизация по вставкам фрагментов;

— оптимизация по перестановкам пар переходов в маршруте.
216

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

Последовательность работы алгоритмов может быть задана в режиме диалога или определена по умолчанию.

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

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

10.3.3. Оценка точности приближенных решений. Введем следующие обозначения:

hi — длина выпуклой оболочки;

/і2 — значение целевой функции для оптимального решения задачи о назначении *);

Hs — длина кратчайшего дерева;

/14 — длина кратчайшего 1-дерева, /14 > /13;

w — нижняя оценка.

Для вычисления значения w воспользуемся табл. 10.1, где 1 — соответствует замкнутой задаче; а 2 — открытой задаче.

T а б л и ц а 10.1

Задача в координатной форме Задача в матричной форме
1 2 Симметричная Несимметричная
1 2 1 2
w = max (hi, /12, h±) CO Il w = max (/12, /14) CO Il Il SJ- ю —

Пусть z* — приближенное решение, тогда w < l(z°) < l(z*).

10.3.4. Диалоговые процедуры. Эффективность описанных алгоритмов при решении задач может быть существенно повышена, если при их реализации применять диалоговые процедуры. Отметим наиболее часто применяемые процедуры этого типа:

— задание начального решения;

— задание списка алгоритмов для вычисления нижних оценок и формирования приближенных решений;

— задание правила, по которому оценивается близость точек при разбиении множества точек на подмножества в симметричной задаче большой размерности;

— задание способа разбиения точек на подмножества при решении задач большой размерности;

— задание способа вычисления расстояния между точками;

*)Грибов А.Б. Рекурсивное решение транспортных задач линейного программирования // Вестник ЛГУ. — 1978. — Вып. 4, № 19. — С. 11-19.
Гл. 10. Алгоритмы решения задачи коммивояжера 217

— изменение последовательности работы некоторых из алгоритмов локальной оптимизации в процессе решения задачи;

— продолжение или прекращение работы оптимизационных алгоритмов в зависимости от полученных результатов;

— изменение значений параметров, определяющих «мощность» и способ формирования окрестности в алгоритмах локальной оптимизации в процессе решения задачи;

— задание параметров, определяющих форму представления результатов, полученных при решении задачи.

10.4. Формирование приближенного решения задачи из решений подзадач

10.4.1. Построение начальной последовательности подмножеств, оценка трудоемкости. Пусть Si, S2,..., Sk — полученное разбиение, Si = I Si I. Предположим, что уже определена начальная последовательность подмножеств Si1, Si2,, Sit, число элементов которой меньше к. Обозначим через L = (і\, i2,..., ц) — множество индексов, \L\ < к.

Рассмотрим две задачи для определения очередного элемента последовательности подмножеств:

а) вычислим к — \L\ чисел т (Sj) = maxcrj, г ? Sii, j ?. L, и найдем подмножество Sj0, для которого т (Sj0) = min г (Sj) = min max crj\

j j

б) вычислим к — \L\ чисел т (St) = maxcrt, г Є Sil, t ?. L, и найдем подмножество St0, для которого т (St0) = min г (St) = mm max C7^.

Если r(Sj0) < r(St0), то получим последовательность подмножеств Si15Si2,... ,SinSj0; тогда L = (h,i2, • • -,iijo)-

При T(Sj0) > T(St0) получим последовательность подмножеств St0, Si1, Si2,..., Sil; тогда L = (t0, ч, %2,..., ц), в этом случае \Ь\ = = I + 1. При \L\ = к построение последовательности подмножеств окончено; если \Ь\ < к, то процесс продолжается. В качестве начальной частичной последовательности на первом шаге берется последовательность %\,г2, для которой

Pi1 i2 = min max Cuv, і ф j.

і,3 ueSi veSj

Оценим трудоемкость T данного алгоритма. Как видно из его описания, на первом шаге определяются два элемента последовательности; на всех последующих шагах к полученной последовательности

добавляется один новый элемент. Пусть ц8 — трудоемкость на шаге s,

к-1

I < s < к — 1; тогда T= Y IjlS-

S = 1
218

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

Для определения /іі необходимо решить следующую задачу:

к к

цI = EE SiS3 max’

і=I j=i+l

к

= Si > 0 целые, і = I, 2,..., к.

Как показано далее в этом параграфе (см. п. 10.4.4), для /і і полу-

чена оценка /Ji < ^l — і У Очевидно, что
Предыдущая << 1 .. 70 71 72 73 74 75 < 76 > 77 78 79 80 81 82 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100