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

 

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

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

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


2т/Ы)-Про п) > (9.3.24)

а для задачи другого типа

2т/Ьє)~пр0 (уп, п) < а.

Условия (9.3.24) и (9.3.25) позволяют определить точность решения задачи є в зависимости от ресурса а при известном значении параметра 7. Поскольку go (п) = О (п) и gi (ш, п) растет быстрее, чем

О (п) (см., например, [41]), то ро (m,n) > 1. Если выполнено (9.3.19), то 2m/(7?)_n < 1, откуда 2m/(7?)_n < ро(т,п). Условие т/(^є) < п следует также из (9.3.23), так как ро (ш,п) > 1.

Описанный в п. 9.3.3 подход получил дальнейшее развитие в работе: Сигал И.Х. Параметризация г-приближенных алгоритмов решения некоторых классов задач дискретной оптимизации большой размерности // Известия РАН. Теория и системы управления. — 2002.

— № 6. — С. 63-72. (Эта работа опубликована после выхода в свет первого издания книги.)
Глава 10

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

10.1. Постановка задачи и общие сведения об алгоритмах ее решения

10.1.1. Постановка задачи. Пусть P = {1,2,..., гг} — конечное множество точек. Каждой паре і Є P и j Є P (і Ф j) поставлено в соответствие число Cij > 0, называемое расстоянием. Числа сц могут быть элементами матрицы расстояний С = (cij)nxn- В этом случае задача поставлена в матричной форме. Если числа сц определяются координатами точек (Хі,Уі) и (Xj,yj) на плоскости, то задача поставлена в координатной форме. В этом случае рассматриваются лишь метрические задачи.

Пусть ^ = (гі, г2,..., гп) — произвольная перестановка номеров (1, 2,... ,п) точек, называемая в дальнейшем маршрутом коммивояжера. Каждому маршруту z поставим в соответствие его длину:

здесь гп+1 = i\. Для незамкнутой (открытой) задачи в выражении для l(z) вместо п берется п — 1.

Обозначим через Zq множество всех возможных маршрутов. Ставится задача о минимизации l(z) на множестве Zq:

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

10.1.2. Декомпозиционный подход. При решении реальных задач предполагается (см. гл. 9), что применение алгоритмов поиска точного решения не представляется возможным. В этом случае может

п

к=1

I (z) —> min, z Є Zq.
Гл. 10. Алгоритмы решения задачи коммивояжера 205

быть использован декомпозиционный подход. Основные его элементы следующие:

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

— решение подзадач;

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

Для решения задачи о разбиении применяются различные алгоритмы кластеризации [22, 33, 37, 39].

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

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

Если ограничиться применением лишь первых двух элементов данного подхода, то получаем решение задачи нескольких коммивояжеров.

Целью декомпозиции является разбиение точек множества P на непересекающиеся подмножества близких точек, при этом число точек в каждом из таких подмножеств существенно меньше, чем число точек в множестве Р. Точки, принадлежащие одному подмножеству, являются близкими в смысле заданной симметричной функции расстояния. Как уже отмечалось в п. 10.1, для решения задачи декомпозиции (разбиения) применяются алгоритмы кластеризации.

Все рассматриваемые здесь алгоритмы решения задачи декомпозиции состоят из двух основных элементов: задание или построение начального разбиения; улучшение (оптимизация) этого разбиения. Описание декомпозиционных процедур приводится в этом параграфе.

10.2.1. Постановка задачи разбиения. Рассмотрим задачу

о разбиении точек множества P на непересекающиеся подмножества Si, S2,..., Skj к > 2: ,

Si П Sj — 0, і ф j, і, j — 1, 2,..., к;

0 ^min ^ I Si I ^ ^maxj ^ — 1,2, ...,&.

Число подмножеств к определяется так, чтобы выполнялось условие к X Tlmin ^ TL ^ к X ТТ/тах-Предполагается также, что параметры птт и nmax являются величинами одного порядка. Последнее предположение никак не влияет

10.2. Декомпозиция

і=1
206

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

на построение алгоритмов кластеризации и используется лишь при получении оценок трудоемкости некоторых из этих алгоритмов.

Каждому разбиению S = (Si, S2, • • •, Sk), удовлетворяющему указанным условиям, ставится в соответствие значение функции ip(S) = = </?(Si, S2, • • •, Sk), характеризующей качество разбиения. Необходимо найти разбиение 5° = (Si, S2,..., Sjj!), при котором tp(S) принимает минимальное значение:

V (S0) =пипу>(5).

Рассмотрим способы вычисления значений функции ip(S). Предположим, что известны функции Qp(Si)1 характеризующие близость точек, принадлежащих подмножеству Si. В качестве функций (fp(S)

при фиксированном значении р рассмотрим одну из двух функций:

к

^Pp (Si, S2, • • • , Sk) = Yj 9р (^г)ч
Предыдущая << 1 .. 65 66 67 68 69 70 < 71 > 72 73 74 75 76 77 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100