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

 

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

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

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

Рассмотрим алгоритм. Он состоит из следующих шагов.

1. Найти минимальное остовное дерево T для матрицы расстояний dij.

2. Выделить в T вершины нечетной степени (их количество четно) и найти кратчайшее совершенное паросочетание M (т.е. паросочетание, покрывающее все вершины) в полном графе с вершинами с нечетными степенями. Пусть G — мультиграф с вершинами {1,..., п}, в который входят все ребра из T и М.

3. Найти эйлеров маршрут и выделить из него маршрут z коммивояжера.

Для иллюстрации на рис. 6.3-6.6 приведены все этапы работы алгоритма. На рис. 6.3 — кратчайшее дерево, в котором выделены вершины 1, 2, 3, б, 7, 9 с нечетными степенями. На рис. 6.4 — паро-
Гл. 6. Алгоритмы гарантированного функционирования 157

сочетание M, построенное на вершинах 1, 2, 3, б, 7, 9. На рис. 6.5 — мультиграф, который состоит из T и М. Рис. 6.5 соответствует эйлерову маршруту (1, 2, 3, б, 8, 10, 9, 7, 5, б, 4, 2, 1), который преобразуется в маршрут коммивояжера z = (1, 3, б, 8,10, 9, 7, 5,4, 2,1) (рис. б.б) по правилу из первого алгоритма.

Теорема б.б. Маршрут z, полученный по описанному правилу, является є-оптимальным при є = 1/2.

Доказательство. Докажем сначала, что полученный на шаге 2 граф эйлеров. Если вершина из T имеет четную степень, то и в G она имеет эту же степень. Если вершина имеет нечетную степень в дереве T, то в G ей инцидентно еще одно дополнительное ребро из паросо-четания M. Очевидно так же, что граф G связен, так как он содержит в качестве подграфа остовное дерево Т. Если Z (G) = Y dij и z —

(i,j)EG

получаемый на шаге 3 маршрут, то l(z) < 1(G). Так как G состоит из T и М, то

l(z)<l (G) =I0+ I (M),

I (M) — вес паросочетания.

Если Zo — кратчайший маршрут, то Z о < Z(^o).

Пусть (гі, %2, . . . , І2т) — множество вершин нечетной степени, перечисленных в том порядке, в котором они появляются в оптимальном маршруте Zo. Другими словами, Z0 = (a0i1a1i2,..., a2m-ii2ma2m), где все aj — последовательности вершин из множества {1,2,..., гг}; некоторые из aj, возможно, являются пустыми. Рассмотрим два паросочетания на множестве вершин нечетной степени:

Мі={(гі,г2), (г3,г4),..., (г2 771 — 1 5 ^2га) } 5

М2={(г2,г3), (г4,г5), • • •,

По неравенству треугольника имеем

I(Z0) > Z(Mi)+Z(M2).

Поскольку M — оптимальное паросочетание, то Z(^o) > 21 (M), т.е. Z (M) < Поэтому

l(z) < Z0 + Z(M) < 1(zq) + = -l(zo), < -.
158

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

Вычитая по единице из обеих частей, получим

l(z) - I Qo) 1 I(Z0) - 2’

и теорема доказана.

Описанные г-оптимальные алгоритмы для задачи коммивояжера изложены по [30].

6.3. Задачи о покрытиях графов

Пусть G = (/, U) — конечный граф без изолированных вершин и кратных ребер и петель, I — множество вершин |/| = п > 2; U — множество ребер, (и, v) Є U, и Є /, V Є I. Далее рассматриваются алгоритмы типа «greedy» для задач о вершинном и реберном покрытиях.

6.3.1. Задача о вершинном покрытии. Множество вершин E С I с числом вершин I(E) образует вершинное покрытие графа G, если любое ребро (и, v) Є U инцидентно хотя бы одной вершине множества Е. Покрытие Eq С I называется оптимальным, если оно содержит минимальное число вершин:

Oti (G) = Io = I (E0) = min I (E),

минимум вычисляется ПО всем вершинным покрытиям. Число C^i(G) называется числом вершинного покрытия.

Определение. Алгоритм А, вырабатывающий вершинное покрытие Е, называется е-оптималъным (є > 0), если

I(E)-I(E0)

I(E0)

покрытие E называется е-оптималъным.

Опишем алгоритм построения покрытия С С /, в котором содержится г-оптимальное покрытие E [30].

Шаг 1. Считать множество С пустым.

ПІАГ 2. Выбрать любое ребро (u,v) Є С/, удалить обе вершины из /, добавить их к множеству С.

Шаг 3. Если множество I не является пустым, то перейти к шагу 2.

Теорема 6.7. Описанный алгоритм построения вершинного покрытия является е-оптималъным при е = 1.

Доказательство. Получаемое в результате работы алгоритма множество С является вершинным покрытием. Согласно определению любое вершинное покрытие должно покрывать все ребра, выбираемые данным алгоритмом. Однако эти ребра не имеют общих вершин, поэтому все ребра покрываются разными вершинами из вершинно-
Гл. 6. Алгоритмы гарантированного функционирования 159

го покрытия. Следовательно, любое вершинное покрытие должно содержать хотя бы одну вершину каждого выбранного ребра и поэтому мощность любого вершинного покрытия не может быть меньше, чем половина мощности С. Поэтому для покрытий E и Eq получаем

I (E) > I (E0) > Ш,

так как E0 — оптимальное покрытие. Поскольку E С C1 то I(C) >

> I(E) и

I(C) > I(E) > I(E0) >Щ^-> Щр-.

I (E) I (E)

Отсюда I (Eq) > , < 2. Вычитая по единице из обеих частей

2 I (Eo) неравенства, получаем

I(E)-I(E0)

I (E0) - '

Теорема доказана.

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

* Г 1(Е) о
Предыдущая << 1 .. 48 49 50 51 52 53 < 54 > 55 56 57 58 59 60 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100