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

 

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

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

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


7.1.2. Примеры определения окрестности.

Задача о ранце. Рассмотрим задачу (2.2.4)-(2.2.6), и пусть Z0 = = (zj, z\,..., Z^) — допустимое булево решение. Приведем два определения окрестности.

а) Пусть z® = 0, Zj = 1. Под окрестностью вектора Z0 будем

понимать все допустимые векторы, получающиеся из вектора Z0 следующим образом: = I, z® = 0, к ф j, — Cj > 0, к ф j, 1 < к < п,

I < J < При таком определении окрестности евклидово расстояние P между векторами Z1 И z" удовлетворяет условию P(Z11Zn) = л/2-Алгоритмы, основанные на таком определении окрестности, неэффективны, ибо в процессе их работы не изменяется количество нулей и единиц в векторе Z0.

б) Выберем s > 1 компонент (2;^, 2^2,..., Z^s) вектора Z0 таких,

ЧТО Y zI <s- Под окрестностью Z0 будем понимать все допустимі k

мые векторы, получающиеся из Z0 фиксацией всех сочетаний нулей и единиц на местах ii, г2,..., is] число рассмотренных при этом булевых векторов равно C^1. Если рассмотреть все наборы по s компонент, то число булевых векторов будет равно 2sC^. Для любого фиксированного s расстояние p(z',z") удовлетворяет условию

I < P (z!, Zn) < л/s.

Задача коммивояжера. Рассмотрим задачу коммивояжера и приведем примеры определения окрестности. Пусть z = (н,г2,...

..., in) — маршрут коммивояжера.

а) Под окрестностью маршрута z понимаются все маршруты, полученные из z с помощью перестановки любых двух точек %k ф is-

б) Под окрестностью маршрута z понимаются все маршруты, получаемые из z с помощью всех перестановок любых I < s < п подряд расположенных точек, число таких маршрутов равно (п — s + l)s!.
Гл. 1. Локальная оптимизация

163

Можно показать, что если P ф NP, то никакой полиномиальный алгоритм локальной оптимизации с полиномиальной оценкой сложности каждого шага не может быть точным [30].

Конечность алгоритмов локальной оптимизации очевидна, так как конечно множество допустимых решений, но количество шагов и точность, как правило, оценить не удается. Алгоритмы локальной оптимизации легко реализуются, их высокое быстродействие достигается тем, что каждое вычисленное значение функции f(x) реализуется с учетом локальных изменений в векторе х. Отметим, что алгоритмы указанного типа не требуют никакой дополнительной памяти.

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

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

7.2.1. Задача коммивояжера.

Алгоритмы перехода в ближайшую точку. Рассмотрим алгоритмы перехода в ближайшую точку (они часто называются алгоритмами «ближайшего соседа»).

Первый алгоритм состоит в том, что после выбора начальной точки ищется ближайшая к ней, затем ближайшая из оставшихся и т.д.; из последней точки реализуется возврат в начальную. Пусть P = = {1,2,..., гг} — множество точек, сц >0 — «расстояние» между точками і Є P1 j Є P1 н — начальная точка. Найдем точку %2 такую, что Cili2 = HiinCili, і Ф H- Пусть zk = (н,н,---,й) — найденная

часть маршрута. Точка ik+i определяется из условия Cikik+1 = min Cifci,

і Є P\{zk}, zk+1 = (н,.. .,ik,ik+1). Если множество P\{zk+i} ф 0, то найдем точку ik+2 и т.д. Длина l(z) полученного маршрута определяется так: ^ 1

к=і

Очевидно, что трудоемкость описанного алгоритма может быть оценена как 0(п2), для запоминания результата необходим массив

7.2. Эвристические алгоритмы

її*
164

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

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

{іq, если j = і + 1, і = I, 2,. ..,n — I;

А, если j = n, j = I;

p во всех остальных случаях,

где А > р > q. Матрица С не является симметричной, А = Cin ф сп\ = = Vi csk Ф Cks ПРИ 5 = 2,3,... ,п ж к = S-1. Предположим, что правило треугольника не выполнено.

Тогда описанный алгоритм дает маршрут z = (1,2,..., гг), l(z) = = (n — l)q + A. Выбирая величину А, можно сделать маршрут z сколь угодно длинным.

Оптимальное решение Zo имеет вид (1,2,..., п—2, п, п—I), l(zo) = = (п — 3)q + 3р. Получим нижнюю и верхнюю оценки для отклонения решения ^ от оптимального Zo при условии А > р > q.

Верхняя оценка:

I (z) _ (п - I) q + А _ (п - I) q + А (п - I) q + А I (Zo) (п — 3) q + 3^ ng + 3 (р — q) nq ’

так как р — q > 0;

l(z) - I (zp) ^ (re — I) q + A _ ^ _ A - q

I (zo) nq nq

Нижняя оценка:

I (z) _ (re - I) q + A (re - I) q + A _
Предыдущая << 1 .. 50 51 52 53 54 55 < 56 > 57 58 59 60 61 62 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100