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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 55 56 57 58 59 60 < 61 > 62 63 64 65 66 67 .. 84 >> Следующая


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

Простая модификация описанной выше эвристической процедуры состоит в переупорядочении неокрашенных вершин после окраски каждой очередной вершины; оставшиеся неокрашенные вершины записываются в порядке невозрастания их «относительных» степеней, т.е. степеней в таком графе, который получается из данного после удаления окрашенных вершин (вместе с ребрами, инцидентными удаленным вершинам).

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

- А2)

осуществлять с помощью двухшаговых степеней Cli вершин г, имеющих одинаковые степени (одинаковые одношаговые степени), где определяется как число маршрутов*) длины 2, исходящих из і. Эти

вершины могут быть размещены тогда в соответствии с величинами

(2)

степеней d\ . Если все-таки найдутся вершины, у которых совпадают и степени di, и степени d\2\ то можно вычислять трехшаговые степени d^ (определяемые аналогичным образом) и размещать вершины

- л(з)

с учетом степеней а\ J и т.д.

Можно действовать иначе: размещать вершины сразу в соответ-

A2) А3)

ствии с их степенями а\ или степенями а\ и применять тот же

самый последовательный метод раскраски. Таким образом, описанный выше метод раскрашивания очерчивает целый класс последовательных методов, каждый из которых связан с определенным способом упорядочивания вершин — либо статическим (т.е. фиксированным сразу для всей процедуры), либо динамическим (т.е. изменяющимся в процессе раскраски). Способ упорядочения может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик. Показано (см. [20]), что можно построить графы, для которых любой из эвристических методов дает сколь угодно плохие оценки хроматического числа.

*) Если А — матрица смежности графа G с диагональными элементами,

п

равными 0, то di = Yl aij • Двухшаговая степень определяется тогда по фор-

<42) = E ^di,

J = 1

и вообще к-шаговая степень определяется по рекуррентной формуле

АЮ _ f „....,,(«-і)
176

Разд. III. Приближенные методы и алгоритмы

7.3. Комбинированные алгоритмы для задачи коммивояжера

Комбинированные алгоритмы указанного типа для задачи (1.1.1) состоят из следующих основных этапов:

а) построение (или задание) начального решения;

б) улучшение начального решения.

Для задачи о ранце комбинированные алгоритмы описаны в гл. 2. Рассмотрим здесь комбинированные алгоритмы для задачи коммивояжера.

7.3.1. Построение начального решения. Для нахождения этого решения используются следующие алгоритмы:

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

— алгоритмы типа многоугольника для задачи на плоскости;

— алгоритмы движения «вправо» в известном (классическом) алгоритме решения задачи коммивояжера [21], описанном в гл. 3.

Начальное решение может быть задано в режиме диалога.

7.3.2. Улучшение начального решения. Для улучшения начального решения, полученного на первом этапе, применяются следующие алгоритмы:

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

— алгоритмы устранения пересечений для задач на плоскости.

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

7.3.3. Вычисление нижней оценки для задачи коммивояжера. Пусть /о — значение целевой функции для оптимального решения задачи о назначении; /(Ti) — длина кратчайшего 1-дерева Ti для симметричной задачи; l(zi) — длина начального маршрута \ lfa) — длина улучшенного маршрута z2; Io — нижняя оценка для длины Ifa) оптимального маршрута z$. Для несимметричной задачи Iq = /о, для симметричной задачи Iq = шах (/о,/(Ti)). Тогда

I0 < I fa) < I fa) < I fa).

7.3.4. Постановка задачи о формировании комбинированного алгоритма*). Пусть А = (ai, а2,..., ар) — множество алгоритмов локальной оптимизации для решения задачи (5.1.1) и х* — начальное приближение, которое можно найти с применением описанных ранее алгоритмов. Обозначим через ai(x) результат применения

*) Сигал И.Х. Последовательность применения алгоритмов приближенного решения в комбинированном алгоритме решения задачи коммивояжера // Ж. вы-числ. матем. и матем. физ. — 1989. — Т. 29, № 11. — С. 1714-1721.
Гл. 1. Локальная оптимизация

177

алгоритма CLi Є А к точке х Є G. Каждой последовательности алгоритмов

7Г = {CLi1 Ч аІ2 5---5 aIs } 5 ait Ф ait +1 5 t = I, 2,..., s — I;

I < s <k, k > 2, ставится в соответствие последовательность точек ж*, ж1,..., Xs из G:

х*, Ж1 = Qi1 (ж*), X2=^2(X1)5 ..., ж5 = CLis (^5-1) ,

для которых / (ж*) > / (ж1) >...>/ (ж5). Множество последовательностей указанного типа обозначим через П. Каждой последовательности 7Г Є П и начальному приближению ж* Є G поставим в соответствие значение F(tt,x*) = f(xs).

Ставится задача определения последовательности 7Го Є П такой, что
Предыдущая << 1 .. 55 56 57 58 59 60 < 61 > 62 63 64 65 66 67 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100