Что вы всегда хотели узнать, но боялись спросить

Swetlana · Сообщение **Swetlana** » 27 янв 2013, 14:48

так, начну всё с самого начала

"РЮКЗАК" - задача на максимум, величина приближённого решения должна быть как можно больше.
Определение мультипликативной ошибки/относительной погрешности/относительной гарантированной точности (термины из разных источников) дадим для задачи максимизации.

Определение (Silvano Martello, Paolo Toth "Knapsack Problem" University of Bologna, John Wiley& Sons, украдено в институте математики им. Соболева).
Алгоритм $$A$$

называется приближённым алгоритмом с гарантированной относительной точностью $$K$$

, если для любого примера $$I$$

алгоритм находит значение $$A(I)$$

такое, что $\frac{A(I)}{Opt(I)} \geq K$ для всех $$I$$

.

Слова для всех $$I$$

не надо понимать буквально, конечное число наборов всегда можно исключить из рассмотрения. Так как конечное число примеров можно решить особо. А вот бесконечное число примеров исключить нельзя.
Если я хочу доказать, что рассмотренный выше жадный алгоритм не дает гарантированной относительной точности ни для какого $$K$$

(именно этого я и хочу), я должна придумать
1. бесконечную серию примеров, для которых $\frac{A(I)}{Opt(I)} \rightarrow 0$ ;
2. при $Opt(I) \rightarrow \infty$ .
Второй пункт тоже важен, если он не выполняется, то все "плохие" примеры с неограниченной погрешностью оказываются внутри задач ограниченной размерности. То есть начиная с какой-то размерности плохих примеров нет.
Поэтому бесконечная серия "плохих" примеров для любого типа погрешности делается для сколь угодно больших значений $$Opt(I)$$

, т.е. плохие примеры есть для любой, самой большой размерности.
( В скобках замечу, если взять определение мультипликативной ошибки по Кормену
$\frac{Opt(I)}{GA(I)} \leq C$
то $C = \frac{1}{K}$ и если $K \rightarrow 0$ , то $$Ñ \rightarrow \infty$$.)

Доказательство.
Построим, наконец, бесконечную серию "плохих" примеров, для которых $K \rightarrow 0$ или $$Ñ \rightarrow \infty$$.
Это наборы, состоящие из двух предметов $$(2 \ ðóá, \ 1 \ êã)$$ и $$(B \ ðóá, \ B \ êã)$$, где $$B$$

- ограничение на вес рюкзака. Бесконечная серия получается при $B \rightarrow \infty$ .
$$Opt(I) = B, \ GA(I) = 2, \ \frac{2}{B} \rightarrow 0 \ ïðè \ B \rightarrow \infty$$, ч.т.д.

NT, из вашего примера с золотым предметом веса 1 кг можно сделать бесконечную серию примеров, для которых жадный алгоритм работает как точный и находит оптимальное решение. Но.
Погрешность алгоритма меряется по самому плохому случаю, поэтому алгоритмы работают на реальных данных лучше своих теоретических погрешностей.
Самый плохой случай для нашего жадного алгоритма, к сожалению, очень плохой, погрешность ничем не ограничена. Но, к счастью, добавив к этому алгоритму ещё один шаг, мы получим модифицированный алгоритм, у которого $$C = 2$$

(или $K = \frac{1}{2}$ ).

Swetlana · Сообщение **Swetlana** » 27 янв 2013, 17:37

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

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

Пусть $$Cmax$$

- стоимость самого дорогого предмета. Формируем рюкзак согласно вышеописанному жадному алгоритму, стоимость рюкзака $$GA(I)$$

. Затем сравниваем полученную стоимость со стоимостью самого ценного предмета.
В качестве окончательного решения возвращаем $GAM(I) = max \{ Cmax, \ GA(I)\}$ .

Теорема. Модифицированный жадный алгоритм имеет гарантированную относительную точность $K = \frac{1}{2}$ или мультипликативную погрешность $$C = 2$$

.
Доказательство. Рассмотрим ещё один (уже третий) алгоритм, который работает следующим образом.
1. Сортируем предметы по удельной стоимости.
2. Укладываем предметы в рюкзак согласно первому жадному алгоритму $$GA$$

, пока не встречаем первый предмет, который не проходит ограничение на вес. Запоминаем его. Пусть это будет предмет с номером $$p$$

. Продолжаем формировать рюкзак жадным алгоритмом.
3. Когда рюкзак сформирован, укладываем туда ещё и отброшенный $$p$$

- й предмет.
Возвращаем стоимость решения $$GA(I) + s_p$$

(стоимость "жадного" рюкзака + стоимость первого предмета, который должны были отбросить).

Покажем, что $GA(I) + s_p \geq Opt(I)$ .
Рассмотрим только первые $$p$$

предметов, находящиеся в рюкзаке. Сравним их с "оптимальным" рюкзаком. Любой предмет из "оптимального" рюкзака либо находится среди первых $$p$$

предметов, либо его удельная стоимость не превосходит удельной стоимости любого из первых $$p$$

предметов.
Вес "оптимального" рюкзака меньше суммарного веса первых $$p$$

предметов, стоимость 1 кг любого предмета из "оптимального" рюкзака, не вошедшего в число первых $$p$$

предметов, не превосходит стоимости 1 кг любого из первых $$p$$

предметов.
Отсюда
$Opt(I) \leq \sum_{i=1}^p s_i \leq GA(I) + s_p \leq GA(I)+Smax \leq GAM(I)+GAM(I)$
(вспоминаем, что для модифицированного алгоритма $GAM(I) = max \{GA(I), \ Smax \}$ ).
$Opt(I) \leq 2GAM(I)$ ;
$\frac{Opt(I)}{GAM(I)} \leq 2$ , ч.т.д.

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

[img]/modules/file/icons/application-octet-stream.png[/img] ______.rar

Swetlana · Сообщение **Swetlana** » 27 янв 2013, 18:35

а вот это пособие для МФТИ, авторы Кузюрин Н.Н., Фомин С.А."Эффективные алгоритмы и сложность вычислений", там тоже про рюкзак и про жадные алгоритмы и про апроксимационные схемы
мож, кому будет там понятнее
[url=http://discopal.ispras.ru/images/f/f4/Book...-algorithms.pdf]http://discopal.ispras.ru/images/f/f4/Book...-algorithms.pdf[/url]

Swetlana · Сообщение **Swetlana** » 27 янв 2013, 19:46

Полиномиальная апроксимационная схема для задачи о рюкзаке

Получение для задачи о рюкзаке FPTAS (вполне полиномиальной апроксимационной схемы) путём масштабирования псевдополиномиального алгоритма мы уже рассмотрели.
Однако питасы можно получать не только масштабированием алгоритмов ДП.
Рассмотрим получение PTAS для задачи о рюкзаке из рассмотренного выше модифицированного жадного алгоритма GAM.

В модифицированном алгоритме построение начиналось от пустого рюкзака.
Сахни (как утверждают Гэри-Джонсон) предложил в качестве начального множества брать поочерёдно всевозможные подмножества, состоящие из $$k$$

предметов, и для оставшихся предметов запускать модифицированный жадный алгоритм. И затем из полученных решений выбирать наилучшее.
Таким образом, получаем серию алгоритмов $$A_k$$

для целых $k \geq 1$ .
Сахни показал, что каждый такой $$A_k$$

имеет оценку относительной погрешности
$R_{A_k} \leq 1+ \frac{1}{k}$ .

Хотя для каждого фиксированного $$k$$

время работы алгоритма $$A_k$$

является полиномиальным, количество начальных множеств из $$k$$

предметов быстро растёт, поэтому полином всегда содержит $$k$$

в показателе степени, т.е. предложенная Сахни апроксимационная схема является полиномиальной, но не вполне полиномиальной.

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

Swetlana · Сообщение **Swetlana** » 28 янв 2013, 14:01

с теорией ещё не закончили

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

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

Рассмотрим две модельных $$NP$$

- полных задачи: "Минимальное вершинное покрытие" и "Максимальное независимое множество", которые очень тесно связаны между собой. Для неориентированного графа $$G = < V, E >$$

подмножество вершин $V^{'} \in V$ является независимым множеством тогда и только тогда, когда дополнительное подмножество $V \setminus V^{'}$ является вершинным покрытием в $$G$$

.
Более того, это взаимосвязь переносится и на оптимизационные задачи.
Подмножество вершин $V^{'} \in V$ является максимальным независимым множеством тогда и только тогда, когда дополнительное подмножество $V \setminus V^{'}$ является минимальным вершинным покрытием в $$G$$

.
При этом имеется алгоритм отыскания минимального вершинного покрытия с относительной (мультипликативной) погрешностью $R_{A} \leq 2$ и не известен приближённый полиномиальный алгоритм с оценкой $R_{A} < \infty$ для задачи о максимальном независимом множестве.

Пусть имеется граф с $$1000$$

вершинами и минимальным вершинным покрытием мощности $$490$$

. С помощью приближённого алгоритма отыскали вершинное покрытие мощности не более чем $$980$$

: $\frac{980}{490} \leq 2$ .
Максимальное независимое множество состоит из $$1000-490 = 510$$

вершин, независимое множество, найденное приближённым алгоритмом состоит из $$1000 - 980 = 20$$

и относительная погрешность составляет $\frac{510}{20} = 25.5$ .

Swetlana · Сообщение **Swetlana** » 28 янв 2013, 16:00

Результаты о несуществовании алгоритмов
(отрицательные результаты тоже результаты )

В самом хорошем случае для $$NP$$

- полной задачи $$Ï $$</span> <span class=

$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">R_{MIN}(Ï) = 1$$.
Если это так, т.е. $$R_{MIN}(Ï) = 1$$, то задача $$Ï$$ может быть решена:
 $$1.$$

полиномиальной приближенной схемой (PTAS);
 $$2.$$

вполне полиномиальной приближенной схемой (FPTAS);
 $$3.$$

приближенным полиномиальным алгоритмом $$A$$

с асимптотической погрешностью $R_A^{\infty} = 1$ ;
 $$4.$$

приближенным полиномиальным алгоритмом $$A$$

, для которого при некотором фиксированном $$K$$

выполнено неравенство $$|A(I) OPT(I)| \leq K$$ для любого входа $$I$$

.

Для задачи о рюкзаке мы уже построили FPTAS - вполне полиномиальную апроксимационную схему.
Но лучшее, чего мы можем желать от приближённого алгоритма - это пункт 4, фиксированная оценка абсолютной погрешности. Мало для каких задач существуют такие приближённые алгоритмы. В том числе и для задачи о рюкзаке. Докажем, что для задачи о рюкзаке такого алгоритма не существует.

Определение (Silvano Martello, Paolo Toth "Knapsack Problem" University of Bologna, John Wiley& Sons).
Алгоритм $$A$$

называется приближённым алгоритмом с гарантированной абсолютной точностью $$K$$

, если для любого примера $$I$$

алгоритм находит значение $$A(I)$$

такое, что $|A(I) - Opt(I)| \geq K$ для всех $$I$$

.

Пусть алгоритм $$A$$

решает задачу о рюкзаке с $$n$$

предметами и вместимостью рюкзака $$C$$

. Обозначим его временную сложность (или трудоёмкость) $T_{A}(n,C)$ .
Теорема. Пусть $$A$$

- приближённый алгорит решения задачи о рюкзаке с гарантированной точностью $$K$$

и трудоёмкостью $T_{A}(n,C)$ . Тогда алгоритм $$A$$

для любой индивидуальной задачи о рюкзаке $$I$$

позволяет найти точное (оптимальное) решение с той же трудоёмкостью.

(Смысл этой теоремы в следующем.
Если для задачи о рюкзаке приближённый полиномиальный алгоритм с такой оценкой абсолютной погрешности существует, то он будет точно решать задачу о рюкзаке за полиномиальное время, $$P$$

станет равно $$NP$$

, а придумщик такого алгоритма получит весь мир и миллион баксов впридачу :rolleyes:)

Доказательство. Рассмотрим любую индивидуальную задачу $$I$$

с весами предметов $w_1, \dots, w_n$ , стоимостями $s_1, \dots, s_n$ , ограничением на вес рюкзака $$C$$

, все числа целые положительные.
Построим новую задачу $$I^'$$

, умножив стоимости всех предметов на $$K+1$$

:
$s_{1}^{'} = (K+1)s_1, \dots, s_{n}^{'} = (K+1)s_n$ .
Так как мы не изменяли веса предметов и вместимость рюкзака, то оба примера, $$I$$

и $I^{'}$ , будут иметь одинаковое множество допустимых решений.
Так как для любого допустимого решения значение целевой функции (стоимости рюкзака) для примера $I^{'}$ ровно в $$K+1$$

раз больше стоимости рюкзака для примера $$I$$

, то оптимальные наборы предметов для обоих примеров совпадают.
Для примера $I^{'}$ согласно утверждению теоремы выполняется $Opt(I^{'})-A(I^{'}) \leq K$ .
Поскольку $Opt(I^{'}) = (K+1)Opt(I)$ и $A(I^{'}) = (K+1)A(I)$ , получаем:
$Opt(I) - A(I) \leq \frac{K}{K+1}$ .
Так как стоимости целые положительные, то разность $$Opt(I) - A(I)$$

должна быть целым неотрицательным числом, к тому же меньшим числа $\frac{K}{K+1}$ . Такое число только одно - $$0$$

и

для всех

, т.е.

является точным алгоритмом, ч.т.д.

оставайтесь с нами...

Swetlana · Сообщение **Swetlana** » 29 янв 2013, 09:54

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

Теорема. Если $$P <> NP$$

, то для задачи о коммивояжере не существует приближённого полиномиального алгоритма с асимптотической погрешностью $R_{A}^{\infty} < \infty$ .
Доказательство. Предположим, что такой приближённый алгоритм существует.
Тогда для некоторого положительного целого числа $$K$$

существовал бы полиномиальный алгоритм $$A$$

с погрешностью $R_A \leq K$ . Покажем, что такой алгоритм $$A$$

решал бы задачу о существовании гамильтонова цикла за полиномиальное время, $$P$$

стало бы равно $$NP$$

и далее, по рекурсии

Как мы уже видели (и даже доказали), задача $$"ÃÖ"$$ (гамильтонов цикл) полиномиально сводится к задаче $$"ÊÌ"$$ (коммивояжер): $$ÃÖ \propto ÊÌ$$.
Пусть $$G = <V,E>$$

- произвольный неориентированный граф для задачи $$ÃÖ$$. Построим соответствующую ему индивидуальную задачу для $$ÊÌ$$.
Пусть множество вершин графа равно множеству городов, а расстояние между произвольными городами $$u \ è \ v$$ вычисляется следующим образом:
$$\displaystyle A[u,v] = \left \{ \begin{array}{l}
\;\; 1, \ åñëè (u,v) \in E \; \\
\;\; K|V| \ â \ ïðîòèâíîì \ ñëó÷àå. \\
\end{array}$$
Если в графе $$G$$

есть гамильтонов цикл, то минимальный маршрут коммивояжера совпадёт с этим циклом, пройдёт по единичным рёбрам и его стоимость будет в точности равна числу вершин: $$Opt(I) = |V|$$

. Если в

гамильтонова цикла нет, то хотя бы одно ребро маршрута будет иметь стоимость $$K|V|$$

и

(строго больше).
Теперь воспользуемся погрешностью алгоритма.
По предположению, у нас есть приближённый алгоритм $$A$$

с гарантированной погрешностью $\frac{A(I)}{Opt(I)} \leq K$ или $A(I) \leq K*Opt(I)$ .
Если приближённый алгоритм $$A$$

за полиномиальное время построил маршрут стоимости не превосходящей $$K|V|$$

, то в графе $$G$$

существует гамильтонов цикл, если большей - не существует.
Таким образом, алгоритм $$A$$

решает

-полную задачу за полиномиальное время, чего быть не может, если $$P <> NP$$

.

Swetlana · Сообщение **Swetlana** » 30 янв 2013, 15:32

Вполне полиномиальные апроксимационные схемы

Как уже было сказано, источником всех известных FPTAS'ов являются псевдополиномиальные алгоритмы. Действительно, между ними имеется тесная связь.

Гэри-Джонсон доказали следующую теорему
Теорема 1. Если существует такой полином $$q$$

, зависящий от двух переменных, что для любой индивидуальной задачи $$I \in D_Ï$$ выполнено соотношение
$Opt(I) < q(Length(I), \ Max(I))$ , то из существования вполне полиномиальной приближённой схемы для решения задачи $$Ï$$ следует существование псевдополиномиального оптимизационного алгоритма решения задачи $$Ï$$ в предположении, что величины всех решений - целые положительные числа.
Доказательство. Пусть $$A$$

- вполне полиномиальная схема для решения задачи максимизации $$Ï$$ (аналогичное доказательство можно провести для задачи минимизации). Построим с помощью этой схемы точный псевлополиномиальный алгоритм $A^{'}$ .
Пусть $$I$$

- некоторая индивидуальная задача с длиной входа $$Length(I)$$

и максимальным числовым параметром $$Max(I)$$

.
Положим точность $\epsilon = \frac{1}{q(Length(I), \ Max(I))}$ и применим к задаче $$I$$

схему

с заданной точностью $\epsilon$ . По определению схемы $$A$$

за время, ограниченное полиномом от $$Length$$

и $q(Length(I), \ Max(I))$ (это время является псевдополиномиальным!) алгоритм найдёт допустимое решение задачи $$I$$

с погрешностью
$R_{A_{\epsilon}}(I) \leq 1+ \epsilon$ .
Так как $$Ï$$ - задача максимизации, то
$\frac{Opt(I)}{A_{\epsilon}(I)} \leq 1+ \epsilon$ или $Opt(I) \leq (1+ \epsilon)A_{\epsilon}(I)$ .
Отсюда $Opt(I) - A_{\epsilon} \leq \epsilon*Opt(I)$ .
По условиям теоремы $\epsilon*Opt(I) < 1$ , следовательно, $Opt(I) - A_{\epsilon} < 1$ .
Так как значения всех решений - целые положительные числа, то $A_{\epsilon} = Opt(I)$ .
Положим $A^{'} = A_{\epsilon}$ . Алгоритм $A^{'}$ за псевдополиномиальное время находит точное решение для любой задачи $$I$$

, ч.т.д.

В качестве следствия из этой теоремы получаем метод доказательства невозможности существования вполне полиномиальной схемы
Следствие Пусть $$Ï$$ - оптимизационная задача с целочисленными величинами решений, удовлетворяюшая предположениям теоремы 1. Если $$Ï$$ является $$NP$$

- трудной в сильном смысле задачей, то (при $$P<>NP$$

) $$Ï$$ не может быть решена вполне полиномиальной приближённой схемой.

End.
----------------------------------------------------------------------------------------------------------------------------

Вот думаю, для задачи о моделировании листопрокатного склада (размещение готовой продукции+отгрузка) завести отдельную тему, или в этой продолжать, пусть господа-модераторы подскажут.

yourdomain.com