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

 

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

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

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


То iVo T0 N0 т _ q АТ > ~lvF > > "ТТэ Т0 > s0N0i

T(G) N' S0N N' т.е. все выделенное время для решения задачи Tq используется не только для вычисления всех значений /(ж), X Є Go-

Для задачи, не являющейся задачей большой размерности, из

(9.1.1) необходимо получаем

T(G0) + T(G\G0) < T0 = aT(G). (9.2.7)

Переписав это условие в виде soNo + S1 (N — No) < asoN, получаем

О < о S 1?1 = Trf <9-2-8>

отсюда снова получаем, что а > s. Оценки (9.2.6) и (9.2.8) содержат неизвестный параметр s. Предположим, что TVq < N-Nq, т.е.

s < -. Такое предположение вполне естественно: логично предположить, что значения функции f(x) вычисляются во всех точках множества, мощность которого не больше половины мощности G. Функция p(s) = ^—- монотонно убывает с ростом s, 0 < s < -, так как

1 — s 2

^ = < 0.

ds (I - s)

Поэтому максимальное значение а получается при S = O (но не достигается), а минимальное значение 2а — 1 достигается при s = 1/2.
Гл. 9. Вычислительная модель и параметризация

193

Если а > 1/2, то

О < 2а - I < J=-I < I < а < 1. (9.2.9)

тт а — sl .1 3ЛГ

Из условия ------- < - с учетом s < - получаем а < -. Усло-

вие (9.2.6) заведомо выполнено, если выполнено условие

\<р<а. (9.2.10)

Условие (9.2.8) выполнено, если выполнено условие

0 < р < 2а — 1. (9.2.11)

Оценки (9.2.10) и (9.2.11) являются более грубыми (менее точными) по сравнению с (9.2.6) и (9.2.8) соответственно, но они содержат лишь известный параметр задачи а. Поскольку интервалы (0, 2а — 1)

и не могут перекрываться, то 2а — 1 < і, отсюда а <

1 3

Условия (9.2.10) и (9.2.11) выполняются при - < а < -. При этом в

интервале I -, aJ изменения параметра р с длинои а — - < - задача

(1.1.1) является задачей большой размерности; в интервале (0, 2а — 1) с длиной 2а — 1 < а задача таковой не является. Отрезок ^2а — 1, і 3 1

длины 2 — 2а < — является отрезком неопределенности. Последнее

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

Рассмотрим более содержательный случай 0 < s < а < -. При этом

2а- 1 < 0 < < а < (9.2.12)

В этом случае в диапазоне а < р < і изменения параметра р с длиной

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

В условии (9.2.9) максимальное значение дроби ограничено значением 0, 5. Если это неравенство записать в виде

0 < 2а - I < J-=J <а<1, (9.2.9')

то для задачи большой размерности получим, что

а < р < 1. (9.2.10')

13 И.Х. Сигал, А.П. Иванова
194

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

В этом случае неравенство 2а — 1 < а выполнено всегда, отрезки [О, 2ol — 1] и [а, 1] не могут перекрываться, а интервал неопределенности (2а — 1, а) имеет длину 0 < 1 — а < 0, 5, так как а > 0, 5.

Более интересный результат получим, предполагая, что s < —;

такое предположение представляется вполне естественным. В этом

Ol Ol — s ( Ol

случае ------ < -----, поэтому в диапазоне 0, -—

2 — а І-s V 2 — (

а

с длинои

OL J 2 — OL

изменения параметра

О < р < —— (9.2.13)

2 — OL

задача (1.1.1) не является задачей большой размерности. Диапазон

неопределенности имеет длину I (а) = а — — = —— • Поскольку

dl о? — 4а + 2 1

. — чо >0 при 0 < а < -,то 1(a) монотонно возрастает

аа (2 — а)1 2

как функция а, при а = 1/2 значение 1(a) максимально и равно 1/6 = = 0,16666 ... Минимальное нулевое значение при а = 0 недостижимо. Можно рассмотреть и другие зависимости s от параметра a. Ec-

п ^ ^ /1 а ^a — s

ли считать, что 0<s<a<a<-,TO --------------- < ---, поэтому в диа-

2 I + a I — s

пазоне , —j с длиной — задача (1.1.1) не является задачей

большой размерности,

0 <P<Y^- (9.2.14)

Длина интервала неопределенности есть I (а) = а — ——— = —^-—.

I + а 1 + а

Так как = а) > 0, то при 0 < а < і функция 1(a) монотонно

аа (1+а) 2

возрастает и при а = - значение 1(a) максимально и равно 1/6 =

= 0,16666 ... Минимальное нулевое значение при а = 0 недостижимо.

Неравенство —^-— < ——— выполнено при любом значении 0 < а < -. F 2 - a - I + a F ~2

Если a < -, то из условия s < а2 следует, что s < а2 < при этом

a ^ a ^a-S 2-а ~ I + а ~ I — s’

В этом случае верно условие (9.2.14), которое является более сильным по сравнению с (9.2.13). Если же s < а/2, то из этого не следует, что s < а2] возможно, что а2 < s < а/2. Тогда

a ^ а — s ^ а

2-а 1 — s I + a ’

и в этом случае верна оценка (9.2.13). Оценка (9.2.13) верна в обоих случаях: s < а2 < а/2 и а2 < s < а/2, но в первом случае ее можно улучшить до оценки (9.2.14).
Гл. 9. Вычислительная модель и параметризация

195

Окончательный результат состоит в том, что, как это следует из (9.2.9) и (9.2.12), функция p(s) = у—- ПРИ О < s < а < 1 полностью

определяет характер задачи. Исследование этой функции позволило определить границы областей изменения параметра р для задач обоих типов, зависящие лишь от параметра а.
Предыдущая << 1 .. 61 62 63 64 65 66 < 67 > 68 69 70 71 72 73 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100