так, начну всё с самого начала
"РЮКЗАК" - задача на максимум, величина приближённого решения должна быть как можно больше.
Определение мультипликативной ошибки/относительной погрешности/относительной гарантированной точности (термины из разных источников) дадим для задачи максимизации.
Определение (Silvano Martello, Paolo Toth "Knapsack Problem" University of Bologna, John Wiley& Sons, украдено в институте математики им. Соболева).
Алгоритм называется приближённым алгоритмом с гарантированной относительной точностью , если для любого примера алгоритм находит значение такое, что для всех .
Слова для всех не надо понимать буквально, конечное число наборов всегда можно исключить из рассмотрения. Так как конечное число примеров можно решить особо. А вот бесконечное число примеров исключить нельзя.
Если я хочу доказать, что рассмотренный выше жадный алгоритм не дает гарантированной относительной точности ни для какого (именно этого я и хочу), я должна придумать
1. бесконечную серию примеров, для которых ;
2. при .
Второй пункт тоже важен, если он не выполняется, то все "плохие" примеры с неограниченной погрешностью оказываются внутри задач ограниченной размерности. То есть начиная с какой-то размерности плохих примеров нет.
Поэтому бесконечная серия "плохих" примеров для любого типа погрешности делается для сколь угодно больших значений , т.е. плохие примеры есть для любой, самой большой размерности.
( В скобках замечу, если взять определение мультипликативной ошибки по Кормену
то и если , то $$Ñ \rightarrow \infty$$.)
Доказательство.
Построим, наконец, бесконечную серию "плохих" примеров, для которых или $$Ñ \rightarrow \infty$$.
Это наборы, состоящие из двух предметов $$(2 \ ðóá, \ 1 \ êã)$$ и $$(B \ ðóá, \ B \ êã)$$, где - ограничение на вес рюкзака. Бесконечная серия получается при .
$$Opt(I) = B, \ GA(I) = 2, \ \frac{2}{B} \rightarrow 0 \ ïðè \ B \rightarrow \infty$$, ч.т.д.
NT, из вашего примера с золотым предметом веса 1 кг можно сделать бесконечную серию примеров, для которых жадный алгоритм работает как точный и находит оптимальное решение. Но.
Погрешность алгоритма меряется по самому плохому случаю, поэтому алгоритмы работают на реальных данных лучше своих теоретических погрешностей.
Самый плохой случай для нашего жадного алгоритма, к сожалению, очень плохой, погрешность ничем не ограничена. Но, к счастью, добавив к этому алгоритму ещё один шаг, мы получим модифицированный алгоритм, у которого (или ).
Что вы всегда хотели узнать, но боялись спросить
Что вы всегда хотели узнать, но боялись спросить
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Модифицированный жадный алгоритм для задачи о рюкзаке. Оценка относительной погрешности (мультипликативной погрешности, гарантированной точности)
Проблема предыдущего жадного алгоритма состоит в том, что, польстившись на предмет недорогой, но с высокой удельной стоимостью, он уже не может уложить самый дорогой и большой предмет.
Модифицируем алгоритм следующим образом.
Пусть - стоимость самого дорогого предмета. Формируем рюкзак согласно вышеописанному жадному алгоритму, стоимость рюкзака . Затем сравниваем полученную стоимость со стоимостью самого ценного предмета.
В качестве окончательного решения возвращаем .
Теорема. Модифицированный жадный алгоритм имеет гарантированную относительную точность или мультипликативную погрешность .
Доказательство. Рассмотрим ещё один (уже третий) алгоритм, который работает следующим образом.
1. Сортируем предметы по удельной стоимости.
2. Укладываем предметы в рюкзак согласно первому жадному алгоритму , пока не встречаем первый предмет, который не проходит ограничение на вес. Запоминаем его. Пусть это будет предмет с номером . Продолжаем формировать рюкзак жадным алгоритмом.
3. Когда рюкзак сформирован, укладываем туда ещё и отброшенный - й предмет.
Возвращаем стоимость решения (стоимость "жадного" рюкзака + стоимость первого предмета, который должны были отбросить).
Покажем, что .
Рассмотрим только первые предметов, находящиеся в рюкзаке. Сравним их с "оптимальным" рюкзаком. Любой предмет из "оптимального" рюкзака либо находится среди первых предметов, либо его удельная стоимость не превосходит удельной стоимости любого из первых предметов.
Вес "оптимального" рюкзака меньше суммарного веса первых предметов, стоимость 1 кг любого предмета из "оптимального" рюкзака, не вошедшего в число первых предметов, не превосходит стоимости 1 кг любого из первых предметов.
Отсюда
(вспоминаем, что для модифицированного алгоритма ).
;
, ч.т.д.
ЗЫ. ссылка на страницу института Соболева почему-то битая, прикрепляю документ.
там находится более формальное доказательство через релаксацию линейного программирования, которое не решилась привести, чтобы не связываться ещё и с ЛП.
[img]/modules/file/icons/application-octet-stream.png[/img] ______.rar
Проблема предыдущего жадного алгоритма состоит в том, что, польстившись на предмет недорогой, но с высокой удельной стоимостью, он уже не может уложить самый дорогой и большой предмет.
Модифицируем алгоритм следующим образом.
Пусть - стоимость самого дорогого предмета. Формируем рюкзак согласно вышеописанному жадному алгоритму, стоимость рюкзака . Затем сравниваем полученную стоимость со стоимостью самого ценного предмета.
В качестве окончательного решения возвращаем .
Теорема. Модифицированный жадный алгоритм имеет гарантированную относительную точность или мультипликативную погрешность .
Доказательство. Рассмотрим ещё один (уже третий) алгоритм, который работает следующим образом.
1. Сортируем предметы по удельной стоимости.
2. Укладываем предметы в рюкзак согласно первому жадному алгоритму , пока не встречаем первый предмет, который не проходит ограничение на вес. Запоминаем его. Пусть это будет предмет с номером . Продолжаем формировать рюкзак жадным алгоритмом.
3. Когда рюкзак сформирован, укладываем туда ещё и отброшенный - й предмет.
Возвращаем стоимость решения (стоимость "жадного" рюкзака + стоимость первого предмета, который должны были отбросить).
Покажем, что .
Рассмотрим только первые предметов, находящиеся в рюкзаке. Сравним их с "оптимальным" рюкзаком. Любой предмет из "оптимального" рюкзака либо находится среди первых предметов, либо его удельная стоимость не превосходит удельной стоимости любого из первых предметов.
Вес "оптимального" рюкзака меньше суммарного веса первых предметов, стоимость 1 кг любого предмета из "оптимального" рюкзака, не вошедшего в число первых предметов, не превосходит стоимости 1 кг любого из первых предметов.
Отсюда
(вспоминаем, что для модифицированного алгоритма ).
;
, ч.т.д.
ЗЫ. ссылка на страницу института Соболева почему-то битая, прикрепляю документ.
там находится более формальное доказательство через релаксацию линейного программирования, которое не решилась привести, чтобы не связываться ещё и с ЛП.
[img]/modules/file/icons/application-octet-stream.png[/img] ______.rar
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
а вот это пособие для МФТИ, авторы Кузюрин Н.Н., Фомин С.А."Эффективные алгоритмы и сложность вычислений", там тоже про рюкзак и про жадные алгоритмы и про апроксимационные схемы
мож, кому будет там понятнее
[url=http://discopal.ispras.ru/images/f/f4/Book...-algorithms.pdf]http://discopal.ispras.ru/images/f/f4/Book...-algorithms.pdf[/url]
мож, кому будет там понятнее
[url=http://discopal.ispras.ru/images/f/f4/Book...-algorithms.pdf]http://discopal.ispras.ru/images/f/f4/Book...-algorithms.pdf[/url]
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Полиномиальная апроксимационная схема для задачи о рюкзаке
Получение для задачи о рюкзаке FPTAS (вполне полиномиальной апроксимационной схемы) путём масштабирования псевдополиномиального алгоритма мы уже рассмотрели.
Однако питасы можно получать не только масштабированием алгоритмов ДП.
Рассмотрим получение PTAS для задачи о рюкзаке из рассмотренного выше модифицированного жадного алгоритма GAM.
В модифицированном алгоритме построение начиналось от пустого рюкзака.
Сахни (как утверждают Гэри-Джонсон) предложил в качестве начального множества брать поочерёдно всевозможные подмножества, состоящие из предметов, и для оставшихся предметов запускать модифицированный жадный алгоритм. И затем из полученных решений выбирать наилучшее.
Таким образом, получаем серию алгоритмов для целых .
Сахни показал, что каждый такой имеет оценку относительной погрешности
.
Хотя для каждого фиксированного время работы алгоритма является полиномиальным, количество начальных множеств из предметов быстро растёт, поэтому полином всегда содержит в показателе степени, т.е. предложенная Сахни апроксимационная схема является полиномиальной, но не вполне полиномиальной.
PS. Думаю, что пора заканчивать, с теорией, по крайней мере.
Покажу одну свою производственную задачу, не очень сложную, но и не простую, эвристическую модель склада готовой продукции листопрокатного цеха крупного металлургического предприятия, в хорошей размерности.
оставайтесь с нами...
Получение для задачи о рюкзаке FPTAS (вполне полиномиальной апроксимационной схемы) путём масштабирования псевдополиномиального алгоритма мы уже рассмотрели.
Однако питасы можно получать не только масштабированием алгоритмов ДП.
Рассмотрим получение PTAS для задачи о рюкзаке из рассмотренного выше модифицированного жадного алгоритма GAM.
В модифицированном алгоритме построение начиналось от пустого рюкзака.
Сахни (как утверждают Гэри-Джонсон) предложил в качестве начального множества брать поочерёдно всевозможные подмножества, состоящие из предметов, и для оставшихся предметов запускать модифицированный жадный алгоритм. И затем из полученных решений выбирать наилучшее.
Таким образом, получаем серию алгоритмов для целых .
Сахни показал, что каждый такой имеет оценку относительной погрешности
.
Хотя для каждого фиксированного время работы алгоритма является полиномиальным, количество начальных множеств из предметов быстро растёт, поэтому полином всегда содержит в показателе степени, т.е. предложенная Сахни апроксимационная схема является полиномиальной, но не вполне полиномиальной.
PS. Думаю, что пора заканчивать, с теорией, по крайней мере.
Покажу одну свою производственную задачу, не очень сложную, но и не простую, эвристическую модель склада готовой продукции листопрокатного цеха крупного металлургического предприятия, в хорошей размерности.
оставайтесь с нами...
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
с теорией ещё не закончили
Оценки погрешности приближённых алгоритмов
Поскольку большинство реальных задач возникают всё-таки в больших производственных размерностях, то надо уметь как-то определять, какого типа приближённый алгоритм имеет смысл поискать для данной задачи. А какого типа - не стоит и пытаться.
Во-первых, может возникнуть некая иллюзия относительно полиномиальной сводимости. Как мы уже знаем, полиномиальная сводимость оптимальное решение одной задачи отображает в оптимальное решение другой, вдруг она переводит хороший приближённый алгоритм решения одной задачи в хороший приближённый алгоритм для другой задачи.
Увы, это не так. Полиномиальная сводимость сохраняет оптимальные решения, но не сохраняет отношения величины оптимального решения к величине приближённого.
Рассмотрим две модельных - полных задачи: "Минимальное вершинное покрытие" и "Максимальное независимое множество", которые очень тесно связаны между собой. Для неориентированного графа подмножество вершин является независимым множеством тогда и только тогда, когда дополнительное подмножество является вершинным покрытием в .
Более того, это взаимосвязь переносится и на оптимизационные задачи.
Подмножество вершин является максимальным независимым множеством тогда и только тогда, когда дополнительное подмножество является минимальным вершинным покрытием в .
При этом имеется алгоритм отыскания минимального вершинного покрытия с относительной (мультипликативной) погрешностью и не известен приближённый полиномиальный алгоритм с оценкой для задачи о максимальном независимом множестве.
Пусть имеется граф с вершинами и минимальным вершинным покрытием мощности . С помощью приближённого алгоритма отыскали вершинное покрытие мощности не более чем : .
Максимальное независимое множество состоит из вершин, независимое множество, найденное приближённым алгоритмом состоит из и относительная погрешность составляет .
Оценки погрешности приближённых алгоритмов
Поскольку большинство реальных задач возникают всё-таки в больших производственных размерностях, то надо уметь как-то определять, какого типа приближённый алгоритм имеет смысл поискать для данной задачи. А какого типа - не стоит и пытаться.
Во-первых, может возникнуть некая иллюзия относительно полиномиальной сводимости. Как мы уже знаем, полиномиальная сводимость оптимальное решение одной задачи отображает в оптимальное решение другой, вдруг она переводит хороший приближённый алгоритм решения одной задачи в хороший приближённый алгоритм для другой задачи.
Увы, это не так. Полиномиальная сводимость сохраняет оптимальные решения, но не сохраняет отношения величины оптимального решения к величине приближённого.
Рассмотрим две модельных - полных задачи: "Минимальное вершинное покрытие" и "Максимальное независимое множество", которые очень тесно связаны между собой. Для неориентированного графа подмножество вершин является независимым множеством тогда и только тогда, когда дополнительное подмножество является вершинным покрытием в .
Более того, это взаимосвязь переносится и на оптимизационные задачи.
Подмножество вершин является максимальным независимым множеством тогда и только тогда, когда дополнительное подмножество является минимальным вершинным покрытием в .
При этом имеется алгоритм отыскания минимального вершинного покрытия с относительной (мультипликативной) погрешностью и не известен приближённый полиномиальный алгоритм с оценкой для задачи о максимальном независимом множестве.
Пусть имеется граф с вершинами и минимальным вершинным покрытием мощности . С помощью приближённого алгоритма отыскали вершинное покрытие мощности не более чем : .
Максимальное независимое множество состоит из вершин, независимое множество, найденное приближённым алгоритмом состоит из и относительная погрешность составляет .
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Результаты о несуществовании алгоритмов
(отрицательные результаты тоже результаты )
В самом хорошем случае для - полной задачи $$Ï$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">R_{MIN}(Ï) = 1$$.
Если это так, т.е. $$R_{MIN}(Ï) = 1$$, то задача $$Ï$$ может быть решена:
полиномиальной приближенной схемой (PTAS);
вполне полиномиальной приближенной схемой (FPTAS);
приближенным полиномиальным алгоритмом с асимптотической погрешностью ;
приближенным полиномиальным алгоритмом , для которого при некотором фиксированном выполнено неравенство $$|A(I) OPT(I)| \leq K$$ для любого входа .
Для задачи о рюкзаке мы уже построили FPTAS - вполне полиномиальную апроксимационную схему.
Но лучшее, чего мы можем желать от приближённого алгоритма - это пункт 4, фиксированная оценка абсолютной погрешности. Мало для каких задач существуют такие приближённые алгоритмы. В том числе и для задачи о рюкзаке. Докажем, что для задачи о рюкзаке такого алгоритма не существует.
Определение (Silvano Martello, Paolo Toth "Knapsack Problem" University of Bologna, John Wiley& Sons).
Алгоритм называется приближённым алгоритмом с гарантированной абсолютной точностью , если для любого примера алгоритм находит значение такое, что для всех .
Пусть алгоритм решает задачу о рюкзаке с предметами и вместимостью рюкзака . Обозначим его временную сложность (или трудоёмкость) .
Теорема. Пусть - приближённый алгорит решения задачи о рюкзаке с гарантированной точностью и трудоёмкостью . Тогда алгоритм для любой индивидуальной задачи о рюкзаке позволяет найти точное (оптимальное) решение с той же трудоёмкостью.
(Смысл этой теоремы в следующем.
Если для задачи о рюкзаке приближённый полиномиальный алгоритм с такой оценкой абсолютной погрешности существует, то он будет точно решать задачу о рюкзаке за полиномиальное время, станет равно , а придумщик такого алгоритма получит весь мир и миллион баксов впридачу :rolleyes:)
Доказательство. Рассмотрим любую индивидуальную задачу с весами предметов , стоимостями , ограничением на вес рюкзака , все числа целые положительные.
Построим новую задачу , умножив стоимости всех предметов на :
.
Так как мы не изменяли веса предметов и вместимость рюкзака, то оба примера, и , будут иметь одинаковое множество допустимых решений.
Так как для любого допустимого решения значение целевой функции (стоимости рюкзака) для примера ровно в раз больше стоимости рюкзака для примера , то оптимальные наборы предметов для обоих примеров совпадают.
Для примера согласно утверждению теоремы выполняется .
Поскольку и , получаем:
.
Так как стоимости целые положительные, то разность должна быть целым неотрицательным числом, к тому же меньшим числа . Такое число только одно - и для всех , т.е. является точным алгоритмом, ч.т.д.
оставайтесь с нами...
(отрицательные результаты тоже результаты )
В самом хорошем случае для - полной задачи $$Ï$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">R_{MIN}(Ï) = 1$$.
Если это так, т.е. $$R_{MIN}(Ï) = 1$$, то задача $$Ï$$ может быть решена:
полиномиальной приближенной схемой (PTAS);
вполне полиномиальной приближенной схемой (FPTAS);
приближенным полиномиальным алгоритмом с асимптотической погрешностью ;
приближенным полиномиальным алгоритмом , для которого при некотором фиксированном выполнено неравенство $$|A(I) OPT(I)| \leq K$$ для любого входа .
Для задачи о рюкзаке мы уже построили FPTAS - вполне полиномиальную апроксимационную схему.
Но лучшее, чего мы можем желать от приближённого алгоритма - это пункт 4, фиксированная оценка абсолютной погрешности. Мало для каких задач существуют такие приближённые алгоритмы. В том числе и для задачи о рюкзаке. Докажем, что для задачи о рюкзаке такого алгоритма не существует.
Определение (Silvano Martello, Paolo Toth "Knapsack Problem" University of Bologna, John Wiley& Sons).
Алгоритм называется приближённым алгоритмом с гарантированной абсолютной точностью , если для любого примера алгоритм находит значение такое, что для всех .
Пусть алгоритм решает задачу о рюкзаке с предметами и вместимостью рюкзака . Обозначим его временную сложность (или трудоёмкость) .
Теорема. Пусть - приближённый алгорит решения задачи о рюкзаке с гарантированной точностью и трудоёмкостью . Тогда алгоритм для любой индивидуальной задачи о рюкзаке позволяет найти точное (оптимальное) решение с той же трудоёмкостью.
(Смысл этой теоремы в следующем.
Если для задачи о рюкзаке приближённый полиномиальный алгоритм с такой оценкой абсолютной погрешности существует, то он будет точно решать задачу о рюкзаке за полиномиальное время, станет равно , а придумщик такого алгоритма получит весь мир и миллион баксов впридачу :rolleyes:)
Доказательство. Рассмотрим любую индивидуальную задачу с весами предметов , стоимостями , ограничением на вес рюкзака , все числа целые положительные.
Построим новую задачу , умножив стоимости всех предметов на :
.
Так как мы не изменяли веса предметов и вместимость рюкзака, то оба примера, и , будут иметь одинаковое множество допустимых решений.
Так как для любого допустимого решения значение целевой функции (стоимости рюкзака) для примера ровно в раз больше стоимости рюкзака для примера , то оптимальные наборы предметов для обоих примеров совпадают.
Для примера согласно утверждению теоремы выполняется .
Поскольку и , получаем:
.
Так как стоимости целые положительные, то разность должна быть целым неотрицательным числом, к тому же меньшим числа . Такое число только одно - и для всех , т.е. является точным алгоритмом, ч.т.д.
оставайтесь с нами...
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
...хотя полиномиальная сводимость и не сохраняет величину относительной погрешности, она может помочь при установлении отрицательных результатов - что для такой-то задачи не существует приближённого алгоритма конкретного типа
Теорема. Если , то для задачи о коммивояжере не существует приближённого полиномиального алгоритма с асимптотической погрешностью .
Доказательство. Предположим, что такой приближённый алгоритм существует.
Тогда для некоторого положительного целого числа существовал бы полиномиальный алгоритм с погрешностью . Покажем, что такой алгоритм решал бы задачу о существовании гамильтонова цикла за полиномиальное время, стало бы равно и далее, по рекурсии
Как мы уже видели (и даже доказали), задача $$"ÃÖ"$$ (гамильтонов цикл) полиномиально сводится к задаче $$"ÊÌ"$$ (коммивояжер): $$ÃÖ \propto ÊÌ$$.
Пусть - произвольный неориентированный граф для задачи $$ÃÖ$$. Построим соответствующую ему индивидуальную задачу для $$ÊÌ$$.
Пусть множество вершин графа равно множеству городов, а расстояние между произвольными городами $$u \ è \ v$$ вычисляется следующим образом:
$$\displaystyle A[u,v] = \left \{ \begin{array}{l}
\;\; 1, \ åñëè (u,v) \in E \; \\
\;\; K|V| \ â \ ïðîòèâíîì \ ñëó÷àå. \\
\end{array}$$
Если в графе есть гамильтонов цикл, то минимальный маршрут коммивояжера совпадёт с этим циклом, пройдёт по единичным рёбрам и его стоимость будет в точности равна числу вершин: . Если в гамильтонова цикла нет, то хотя бы одно ребро маршрута будет иметь стоимость и (строго больше).
Теперь воспользуемся погрешностью алгоритма.
По предположению, у нас есть приближённый алгоритм с гарантированной погрешностью или .
Если приближённый алгоритм за полиномиальное время построил маршрут стоимости не превосходящей , то в графе существует гамильтонов цикл, если большей - не существует.
Таким образом, алгоритм решает -полную задачу за полиномиальное время, чего быть не может, если .
Теорема. Если , то для задачи о коммивояжере не существует приближённого полиномиального алгоритма с асимптотической погрешностью .
Доказательство. Предположим, что такой приближённый алгоритм существует.
Тогда для некоторого положительного целого числа существовал бы полиномиальный алгоритм с погрешностью . Покажем, что такой алгоритм решал бы задачу о существовании гамильтонова цикла за полиномиальное время, стало бы равно и далее, по рекурсии
Как мы уже видели (и даже доказали), задача $$"ÃÖ"$$ (гамильтонов цикл) полиномиально сводится к задаче $$"ÊÌ"$$ (коммивояжер): $$ÃÖ \propto ÊÌ$$.
Пусть - произвольный неориентированный граф для задачи $$ÃÖ$$. Построим соответствующую ему индивидуальную задачу для $$ÊÌ$$.
Пусть множество вершин графа равно множеству городов, а расстояние между произвольными городами $$u \ è \ v$$ вычисляется следующим образом:
$$\displaystyle A[u,v] = \left \{ \begin{array}{l}
\;\; 1, \ åñëè (u,v) \in E \; \\
\;\; K|V| \ â \ ïðîòèâíîì \ ñëó÷àå. \\
\end{array}$$
Если в графе есть гамильтонов цикл, то минимальный маршрут коммивояжера совпадёт с этим циклом, пройдёт по единичным рёбрам и его стоимость будет в точности равна числу вершин: . Если в гамильтонова цикла нет, то хотя бы одно ребро маршрута будет иметь стоимость и (строго больше).
Теперь воспользуемся погрешностью алгоритма.
По предположению, у нас есть приближённый алгоритм с гарантированной погрешностью или .
Если приближённый алгоритм за полиномиальное время построил маршрут стоимости не превосходящей , то в графе существует гамильтонов цикл, если большей - не существует.
Таким образом, алгоритм решает -полную задачу за полиномиальное время, чего быть не может, если .
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Вполне полиномиальные апроксимационные схемы
Как уже было сказано, источником всех известных FPTAS'ов являются псевдополиномиальные алгоритмы. Действительно, между ними имеется тесная связь.
Гэри-Джонсон доказали следующую теорему
Теорема 1. Если существует такой полином , зависящий от двух переменных, что для любой индивидуальной задачи $$I \in D_Ï$$ выполнено соотношение
, то из существования вполне полиномиальной приближённой схемы для решения задачи $$Ï$$ следует существование псевдополиномиального оптимизационного алгоритма решения задачи $$Ï$$ в предположении, что величины всех решений - целые положительные числа.
Доказательство. Пусть - вполне полиномиальная схема для решения задачи максимизации $$Ï$$ (аналогичное доказательство можно провести для задачи минимизации). Построим с помощью этой схемы точный псевлополиномиальный алгоритм .
Пусть - некоторая индивидуальная задача с длиной входа и максимальным числовым параметром .
Положим точность и применим к задаче схему с заданной точностью . По определению схемы за время, ограниченное полиномом от и (это время является псевдополиномиальным!) алгоритм найдёт допустимое решение задачи с погрешностью
.
Так как $$Ï$$ - задача максимизации, то
или .
Отсюда .
По условиям теоремы , следовательно, .
Так как значения всех решений - целые положительные числа, то .
Положим . Алгоритм за псевдополиномиальное время находит точное решение для любой задачи , ч.т.д.
В качестве следствия из этой теоремы получаем метод доказательства невозможности существования вполне полиномиальной схемы
Следствие Пусть $$Ï$$ - оптимизационная задача с целочисленными величинами решений, удовлетворяюшая предположениям теоремы 1. Если $$Ï$$ является - трудной в сильном смысле задачей, то (при ) $$Ï$$ не может быть решена вполне полиномиальной приближённой схемой.
End.
----------------------------------------------------------------------------------------------------------------------------
Вот думаю, для задачи о моделировании листопрокатного склада (размещение готовой продукции+отгрузка) завести отдельную тему, или в этой продолжать, пусть господа-модераторы подскажут.
Как уже было сказано, источником всех известных FPTAS'ов являются псевдополиномиальные алгоритмы. Действительно, между ними имеется тесная связь.
Гэри-Джонсон доказали следующую теорему
Теорема 1. Если существует такой полином , зависящий от двух переменных, что для любой индивидуальной задачи $$I \in D_Ï$$ выполнено соотношение
, то из существования вполне полиномиальной приближённой схемы для решения задачи $$Ï$$ следует существование псевдополиномиального оптимизационного алгоритма решения задачи $$Ï$$ в предположении, что величины всех решений - целые положительные числа.
Доказательство. Пусть - вполне полиномиальная схема для решения задачи максимизации $$Ï$$ (аналогичное доказательство можно провести для задачи минимизации). Построим с помощью этой схемы точный псевлополиномиальный алгоритм .
Пусть - некоторая индивидуальная задача с длиной входа и максимальным числовым параметром .
Положим точность и применим к задаче схему с заданной точностью . По определению схемы за время, ограниченное полиномом от и (это время является псевдополиномиальным!) алгоритм найдёт допустимое решение задачи с погрешностью
.
Так как $$Ï$$ - задача максимизации, то
или .
Отсюда .
По условиям теоремы , следовательно, .
Так как значения всех решений - целые положительные числа, то .
Положим . Алгоритм за псевдополиномиальное время находит точное решение для любой задачи , ч.т.д.
В качестве следствия из этой теоремы получаем метод доказательства невозможности существования вполне полиномиальной схемы
Следствие Пусть $$Ï$$ - оптимизационная задача с целочисленными величинами решений, удовлетворяюшая предположениям теоремы 1. Если $$Ï$$ является - трудной в сильном смысле задачей, то (при ) $$Ï$$ не может быть решена вполне полиномиальной приближённой схемой.
End.
----------------------------------------------------------------------------------------------------------------------------
Вот думаю, для задачи о моделировании листопрокатного склада (размещение готовой продукции+отгрузка) завести отдельную тему, или в этой продолжать, пусть господа-модераторы подскажут.
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Computer Science»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 28 гостей