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

 

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

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

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


«Золотое сечение» — одна из универсальных мировых констант наряду с числами е, 7г и другими. «Золотое сечение» возникает при решении многих задач, как, например, при построении оптимального алгоритма поиска экстремума унимодальной функции одной переменной *).

*) Уайлд Д.Дж. Методы поиска экстремума. — М.: ГРФМЛ, 1967.
198

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

Если рассмотреть ряд Фибоначчи

Fo — Fi — I5 Fj, = Fk-1 + Fk-2-, к = 2,3,,

то уравнение Люкаса связывает числа Фибоначчи с параметром г =

vt+i

г

Fn — і п — 0,1,...

«Золотое сечение» известно еще в древности, впервые оно встречается в «Началах» Эвклида. Термин «золотое сечение» введен Леонардо да Винчи. Принципы «золотого сечения» легли в основу построения многих произведений мирового искусства, главным образом произведений архитектуры.

Задачи, не являющиеся задачами большой размерности. Перейдем к исследованию задачи (1.1.1), не являющейся задачей большой размерности. Рассмотрим два случая.

а) 1/2 < а < 1. Из условия 0 < р < 2а — 1 получаем ро < 1 — s

< ------(2а — 1). Аналогично предыдущему можно записать

Po < - (2а - I) < (2а - I) < ^ (2а - 1),

а а — s г

т.е.

9 п/ — 1

О <Ро < ——- < 1. (9.3.11)

OL

Более сильное условие можно легко получить непосредственно из неравенства (9.3.3):

.Ol-S . Ol-S

Po < ------ < ----,

а — s г

т.е.

О < ро < 1. (9.3.12)

1 Ol Ol

б) 0 < а < -. Для s < — получена оценка 0 < р < -----, отсю-

2 2 2 -а

да ро < ------ тг~—• Используя стандартную технику, неоднократно

г 2 — OL

применяемую ранее, имеем

a I^ a 1 — s / а 1 — s Po < -Z------< -Z-----------< -Z-----------,

I — OL OL I — OL OL — S I-OL Г

т.е.

О < Po < < 1. (9.3.13)

Из (9.3.13) следует, что с увеличением а уменьшается длина интервала, в котором задача (1.1.1) не является задачей большой размерности, т.е. увеличение вычислительного ресурса позволяет расширить множество задач, которые могут быть решены.

Оценка (9.3.13) согласована с оценкой (9.3.10), так как при 0 <

< а < 1 всегда --------- < 1 + а. Интервал ( --------, 1 + а) естествен-

2 — OL V 2 — OL J
Гл. 9. Вычислительная модель и параметризация

199

но считать интервалом неопределенности. Обозначим через z(a) его длину и оценим ее минимальное и максимальное значения:

/ \ I I + а — a2 dz (а — 1)(а — 3) ~

z (а) = 1 + а - --- = — -------, — = -—. —- > О,

2-а 2-а da (2 — а)2

если 0 < а < 1.

Поэтому минимальное (недостижимое) значение есть z(0) = 1/2,

Vb-I , , 2

а максимальное значение при а = а0 = —-— есть z (ао) = —р, т.е.

2 V5

длина d интервала неопределенности удовлетворяет условию

1 / j / 2 2 1

TT < d < — — <0,4.

2 - - л/5 ’ л/5 2

17 Z1 /І Л 5 1/,/5

Если учесть, что а < -, то z = g? этом слУчае

1 2 1 п Л

з<7! 2<0, ’

т.е. длина интервала неопределенности уменьшается.

Если же s < а2, то получена оценка 0 < р < —; отсюда ро <

а + 1

< ----- • ———, и аналогично, (9.3.13) получим

г 1 + а

о < Po < < 1. (9.3.14)

Оценка (9.3.14) согласована с оценкой (9.3.9), так как —<

< а + 1, и согласована с (9.3.8), так как —< 1.

Отметим, что для задачи, не являющейся задачей большой размерности, выполнено условие 0 < ро < 1 (или 0 < Po < !)• Этот результат может представлять чисто теоретический интерес, так как нам не известны в настоящее время задачи типа (1.1.1), для которых трудоемкость вычисления оценки ниже трудоемкости вычисления значения функции.

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

9.3.2. О применении полученных результатов при решении задач. Рассмотрим задачу коммивояжера, в этом случае до (п) =

= О (п) = соп. Вычислим значения параметра ро = для раз-

9о (п)

личных алгоритмов вычисления значений нижних оценок. Если для

вычисления оценок применять алгоритм приведения [21], то gi (п) =

2

= О (п2) = С3П2; в этом случае ро = ----- = О (п). Если для вычисле-

v у СоП
200

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

ния оценок применять алгоритм решения задачи о назначениях *) с

з

трудоемкостью gi (п) = 0(п3) = с\п3 (см. [30]), то ро = = О (п2).

CqTI

Для симметричной задачи нижней оценкой является длина кратчайшего 1-дерева [20], которое строится с применением алгоритма типа

2

Прима [20] с трудоемкостью (п) = с2п2 операций, р0 = —— = О (п).

CqTL

Во всех этих формулах для вычисления ро, до (п) и gi(n) величины Co, Cl, с2, сз — неизвестные константы.

Рассмотрим задачу об одномерном булевом ранце

п

Y CjXj —>• шах,

j=n

п

E азхз < ь> (9.3.15)

Xj Є {0,1}, j = 1,2,...,п,

Cj > Oj 0 < CLj <b, j = 1,2,... ,п.

В этом случае go (п) = О (п) = Co п. Для вычисления верхней оценки используем алгоритм Данцига из гл. 2. Пусть b и все aj принимают целочисленные значения. Тогда для получения решения по алгоритму Данцига необходимо не более b раз найти наибольшее из чисел Xj = Cj/dj, поэтому gi(n) = 0(пЬ) = с\пЪ, ро = Cb.
Предыдущая << 1 .. 63 64 65 66 67 68 < 69 > 70 71 72 73 74 75 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100