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

 

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

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

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


к

YlPs = K.

5=1

Если Ti{ps) = 0(р|), то из (7.2.3) получаем*)

Из (7.2.2) получим

(7.2.3)

= S1 Г0 = 2>Ы = Е(о(Й%о(?). (7.2.4)

Ps

К

S= 1 5=1

Если T2 (ps) = О (P2s)j то из (7.2.3) получим

2ps = -X, Ps = ".

Из (7.2.2) получаем

p. = р ^ = = рзд

5=1 5=1 4 7 47

Для T3 (р5) = Т4 (ps) = О (р51пр5) из (7.2.3) получим

Inp5 + 1 = —А.

Из (7.2.2) получим

„ = =. r0 = tw = Eo(i‘"f) = o(»>»S' <7'26»

5=1 5=1

Во всех случаях ps = п/к, т.е. все множества Ps имеют одинаковую мощность. Если п делится на к, то получено решение задачи, а если не делится, то для (7.2.1) получена верхняя оценка.

Сравним полученные результаты эффективности декомпозиционного алгоритма (7.2.4), (7.2.5) и (7.2.6) с оценками эффективности алгоритмов, в которых декомпозиция не применяется. Сравнивая оценку (7.2.4) с оценкой Ti(n) = 0(п3), получаем ускорение в к2 раз. Для

дТ

> При вычислении частных производных —— значения констант опущены.

Ops
Гл. 1. Локальная оптимизация

173

оценки (7.2.5) в сравнении с T2(п) = 0(п2) получаем ускорение в к раз. Для оценки (7.2.5) в сравнении с оценкой Хз(п) = O(nlnn) (и также TAn)), получаем, что ускорение равно ----—-. Следует иметь в

In п — In к

виду, что во всех этих оценках для ускорения неявно присутствуют неизвестные константы, т.е. более корректно записывать их соответственно в виде О (к2), О (к), О (:-5-^—последняя оценка имеет

V In п — In к J

вид 0(1), если к <С п.

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

Если точки исходного множества распределены равномерно, то основной эффект декомпозиции достигается на первом шаге. Алгоритм оказывается бесполезным, если все точки исходного множества лежат на его оболочке.

Алгоритм легко обобщается для пространства любой размерности, для размерности 3 реализация алгоритма описана в одной из наших работ *).

7.2.2. Задачи теории графов.

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

Cl С2 Сз С4 С5

Рис. 7.3

*) Меламед И. ИСигал И. X. Задачи комбинаторной оптимизации с двумя и тремя критериями // ДАН. — 1999. — Т. 366, № 2. — С. 170-173.
174

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

В соответствии с описанной эвристикой выбирается множество вершин а\, а2, аз и затем с\, C2, сз, C4, C5. Полученное покрытие состоит из восьми вершин. Оптимальное покрытие содержит только пять вершин Ьі, 62, 63, 64, 65. Если обобщить этот пример и взять граф с п вершинами типа а*, п + 2 вершинами типа bj и п + 2 вершинами типа C7-(и ребрами (Cj^bj) и (di,bj) для всех i,j), то в новом графе описанный алгоритм найдет покрытие из Ii = 2п + 2 вершин (ai, а2,..., ап; Cl, с2,..., сп+2), а оптимальное покрытие содержит Iq = п + 2 вершин (Ьі, Ь2,... ,Ьп+2). Тогда

/і — /о _ гг /о 77. H- 2

и с ростом п ошибка может стать сколь угодно близкой к 100 %. Можно показать, что для описанного эвристического алгоритма имеет место оценка 7 7

п — ЬО / 1

—-— < In п,

Io

Io — число вершин в оптимальном покрытии; 11 — число вершин в покрытии, полученном по описанному алгоритму; п — число вершин (см. [30]).

Задача о вершинной раскраске. Каждая вершина окрашивается в некоторый цвет. Необходимо найти минимальное количество цветов, чтобы все смежные вершины имели разные цвета.

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

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

Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней), и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т.д., пока не будут окрашены все вершины. Число использо-
Гл. 1. Локальная оптимизация

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