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

 

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

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

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


5.4.3. Замечания о полиномиальной трудоемкости алгоритма. В дальнейшем Ю.Ю. Финкельштейном было показано, что г-оптимальный алгоритм Ae при фиксированных m и є имеет полиномиальную по п оценку числа ветвлений*). Степень многочлена была оценена и оказалось, что она зависит от 1/г.

В классической работе JI. Г. Хачияна**) предложен полиномиальный алгоритм для задачи линейного программирования с целыми коэффициентами, т.е. показано, что задачу линейного программирования можно решить на детерминированной машине Тьюринга за полиномиальное от длины входа L время. (Под длиной входа подразумевается число символов 0 и 1, достаточное для записи в двоичной системе всех коэффициентов задачи.) Объединяя этот результат JI. Г. Хачияна и указанный выше результат Ю. Ю. Финкелынтейна, получим, что

*) Финкелъштейн Ю.Ю. є-подход к многомерной задаче о ранце: полиномиальный рост дерева ветвления // Ж. вычисл. матем. и матем. физ. — 1977. — Т. 17, № 5. — С. 1040-1042.

**^Хачиян JI. Г. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. — 1979. — Т. 244, № 5. — С. 1093-1096.

= 1 ^ 1 <

jele jelL jelL

10*
148

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

существует машина Тьюринга, позволяющая находить г-оптимальное решение задачи о ранце с целыми коэффициентами с полиномиальной трудоемкостью *).

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

Отметим, что вычислительная реализация г-оптимального алгоритма не является тривиальной задачей, при этом сохраняются все проблемы, возникающие при реализации алгоритма нахождения точного решения. Реальное решение задач по г-оптимальному алгоритму уже при п = 50иш = 5-і-10 может потребовать значительных вычислительных ресурсов.

Тем не менее, приведенные здесь результаты JI. Г. Хачияна и Ю.Ю. Финкелынтейна имеют большое теоретическое значение. Указан класс задач, для которого переход от нахождения точного решения к г-оптимальному позволяет перейти от задачи класса NP к задаче класса Р. Предложен г-оптимальный алгоритм и оценены его параметры.

5.4.4. Примеры.

1) Рассмотрим пример 2.1 из гл. 2, для которого т = 1, п = 10. Для оценки параметров г-оптимального алгоритма необходимо выполнить перенумерацию переменных в соответствии с (5.4.8). Старая и новая нумерации и значения Cj приведены в первых трех строках табл. 5.1.

Таблица 5.1

Cj = dj 6 5 2 3 4 5 4 8 7 3
Старые номера 1 2 3 4 5 6 7 8 9 10
Новые номера 3 4 10 9 6 5 7 1 2 8
dj/f(x') 0,23 0,19 0,07 0,11 0,15 0,19 0,15 0,31 0,26 0,11
mHne) 7 9 23 15 11 9 11 5 6 15

Определим значения rj = min (j + т — I; п) = min (j; п) = j. Так

гз

как г j = j, то dj = Y ср — cj • В качестве начального решения (в

p=j

*) Финкелъштейн Ю.Ю. О полиномиальном алгоритме є-оптимизации в многомерной задаче о ранце // Ж. вычисл. матем. и матем. физ. — 1980. — Т. 20, № 3. — С. 800-802.
Гл. 5. Постановка задачи о поиске приближенного решения 149

новой нумерации) возьмем из гл. 2 вектор х' = (I; I; I; 1; 0; 0; 0; 0; 0; 0),

10 26 /(V) = 26. Вычислим сз =47, поэтому 7 = — = 0,5532 >

j=і

> 0, 5. В четвертой строке табл. 5.1 приведены значения / , в пятой

fyx')

строке — значения

т_ _ I _ YscJ _ 47 _ 47

7 ? fix') . dj dj dj Cj ’

EcJ f(x')

/7 •

в табл. 5.1 приведены целые части этих значений, є =

/о»') ’

TYl

Из анализа табл. 5.1 видно, что для ряда значений п дробь —

7 є

больше п, это означает, что для соответствующих значений г-сущест-венными могут быть все переменные. При є < 0,19 существенными в силу необходимого условия (5.4.10) (теорема 5.4) могут быть пять переменных с номерами 10,9,6,7,8; по оценке (5.4.13) их число не более 9. При є < 0, 23 в силу необходимых условий существенными могут быть семь переменных с номерами 10, 9, 6, 7, 8,4, 5, по оценке из пятой строки их также не более 7, т.е. необходимое условие (5.4.10) и условие (5.4.13) дают одинаковый результат. При ? < 0,26 по необходимым условиям получаем, что существенными могут быть восемь переменных, а на самом деле не более пяти. Наконец, при ? < 0,31 существенными могут быть по необходимым условиям девять переменных, а на самом деле их не более пяти.

2) Рассмотрим пример 2.6 из гл. 2, в котором т = 3, п = 10.

гз

Вычислим по табл. 5.1 значения dj = ср. Так как

p=j

Tj = min (j + т — I; п) = min(j + 2; п),

то

П =3, T2 = 4, г3 =5, T4 = 6, г5 = 7, г6 =8, г7 = 9, г8 = г9 = по = Ю.

Тогда

з

di = Cp = Ci + C2 + C3 = 21, d2 = C2 + C3 + C4 = 18,

P= 1

6? = C3 + C4 + C5 = 16, d4 = C4 + C5 + C6 = 14,

db = C5 + C6 + C7 = 13, d6 = C6 + C7 + C8 = 11,

d7 = C7 + C8+C9 = 10, d8 = C8 + C9 + сю = 8,

d9 = C9 + сю = 5, diQ = сю = 2.

В качестве начального решения возьмем ж' = (I; 1; 0; 0; 0; 0; 1; 0; 0; 0) из гл. 2, f(xf) = 19, 7 = ^ = 0,4042 < 0,5. В табл. 5.2 приве-
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100