глянула Кормена, как там определяется погрешность приближённого алгоритма задачи минимизации (см. опр. **), попроще чем в Гэри-Джонсоне
Определение *. Алгоритмы, генерирующие квазиоптимальные решения за полиномиальное время, называются приближенными алгоритмами.
(делаем акцент на том, что наши "хорошие" неоптимальные решения будем генерировать за полиномиальное время)
Первый тип оценок погрешности приближенных алгоритмов – это гарантированные оценки точности получаемого решения «в наихудшем случае». Часто для оценки погрешности приближенного алгоритма «в наихудшем случае» используется следующее определение.
Определение **. - алгоритм называется - приближенным, если для любых исходных данных размера он находит допустимое решение со значением целевой функции, отличающимся от оптимума не более чем в раз.
Таким образом, алгоритм является - приближенным, если
, максимум ищется по всем возможным наборам исходных данных .
Величина – мультипликативная ошибка, показывающая во сколько раз величина приближенного решения отличается от оптимума в самом плохом случае.
Мультипликативная ошибка может быть константой или зависеть от параметров входа .
Что вы всегда хотели узнать, но боялись спросить
Что вы всегда хотели узнать, но боялись спросить
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Сообщение отредактировано
Ув. коллеги, давайте вернёмся к двум разным определениям безразмерной погрешности приближённого алгоритма, у Гэри-Джонсона и Кормена.
Поняла, наконец, что мне не нравится, в обоих определениях.
Определение Кормена некорректно, из-за недостаточной строгости.
А Гэри-Джонсон излишне "заложились" (как преферансисты говорят ), их определение можно упростить.
Вот, смотрите сами.
Определение (Кормен). - алгоритм называется - приближенным, если для любых исходных данных размера он находит допустимое решение со значением целевой функции, отличающимся от оптимума не более чем в раз.
Таким образом, алгоритм является - приближенным, если
, максимум ищется по всем возможным наборам исходных данных .
Максимум берётся от левой части неравенства, от , по всем индивидуальным задачам, которых, вообще-то бесконечно.
У бесконечного множества максимум не обязан существовать. Здесь должен быть супремум - наименьшая из всех верхних граней.
Определение (Гэри-Джонсон). Погрешностью приближённого алгоритма решения задачи $$Ï$$ назовём величину :
$$R_A = inf \left\{ r \geq 1: \ R_A(I) \leq r \ äëÿ \ âñåõ \ I \in D_Ï \right \}$$.
Инфинум inf берётся от правой части равенства, не от , а от его мажоранты, которая может быть равна бесконечности... уроборосу :rolleyes:
Зачем здесь инфинум??? достаточно обычного минимума
Ув. коллеги, давайте вернёмся к двум разным определениям безразмерной погрешности приближённого алгоритма, у Гэри-Джонсона и Кормена.
Поняла, наконец, что мне не нравится, в обоих определениях.
Определение Кормена некорректно, из-за недостаточной строгости.
А Гэри-Джонсон излишне "заложились" (как преферансисты говорят ), их определение можно упростить.
Вот, смотрите сами.
Определение (Кормен). - алгоритм называется - приближенным, если для любых исходных данных размера он находит допустимое решение со значением целевой функции, отличающимся от оптимума не более чем в раз.
Таким образом, алгоритм является - приближенным, если
, максимум ищется по всем возможным наборам исходных данных .
Максимум берётся от левой части неравенства, от , по всем индивидуальным задачам, которых, вообще-то бесконечно.
У бесконечного множества максимум не обязан существовать. Здесь должен быть супремум - наименьшая из всех верхних граней.
Определение (Гэри-Джонсон). Погрешностью приближённого алгоритма решения задачи $$Ï$$ назовём величину :
$$R_A = inf \left\{ r \geq 1: \ R_A(I) \leq r \ äëÿ \ âñåõ \ I \in D_Ï \right \}$$.
Инфинум inf берётся от правой части равенства, не от , а от его мажоранты, которая может быть равна бесконечности... уроборосу :rolleyes:
Зачем здесь инфинум??? достаточно обычного минимума
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
... отбрасываем первое определение как некорректное (или пусть мне докажут его корректность), которым сейчас пользуются все , и продолжаем обсуждать определения Гэри-Джонсона.
Очевидно, что погрешность алгоритма не может быть равна 1 - иначе бы для всех индивидуальных задач выполнялось бы , и алгоритм был бы точным алгоритмом.
А вот асимптотическая погрешность может быть равна 1, не для всех индивидуальных задач, а только для задач с достаточно большой величиной решения.
Определение 6. Для оптимизационной задачи $$Ï$$ назовём асимптотически наилучшей достижимой относительной погрешностью величину $$R_{MIN}(Ï):$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">R_{MIN}(Ï) = inf \left \{ r \geq 1: \ äëÿ \ ðåøåíèÿ \ çàäà÷è \ Ï \ $$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">ñóùåñòâóåò \ òàêîé \ ïðèáëèæ¸ííûé \ ïîëèíîìèàëüíûé \ àëãîðèòì \ A, \ $$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">÷òî \ R_A^{\infty} = r \left \} $$
Перечислим три основных типа оценок погрешности приближённых алгоритмов.
$$R_{MIN}(Ï) = \infty$$" title="$$. $$" align="middle" style="border: 0; vertical-align: middle">2.$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">1 < R_{MIN}(Ï) < \infty$$" title="$$. $$" align="middle" style="border: 0; vertical-align: middle">3.$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">R_{MIN}(Ï) = 1$$.
Если $$R_{MIN}(Ï) = 1$$, то можно выделить ещё 4 важных подслучая.
Задача $$Ï$$ может быть решена:
полиномиальной приближенной схемой (PTAS);
вполне полиномиальной приближенной схемой (FPTAS);
приближенным полиномиальным алгоритмом с асимптотической погрешностью ;
приближенным полиномиальным алгоритмом , для которого при некотором фиксированном выполнено неравенство $$|A(I) OPT(I)| \leq K$$ для любого входа .
Очевидно, что погрешность алгоритма не может быть равна 1 - иначе бы для всех индивидуальных задач выполнялось бы , и алгоритм был бы точным алгоритмом.
А вот асимптотическая погрешность может быть равна 1, не для всех индивидуальных задач, а только для задач с достаточно большой величиной решения.
Определение 6. Для оптимизационной задачи $$Ï$$ назовём асимптотически наилучшей достижимой относительной погрешностью величину $$R_{MIN}(Ï):$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">R_{MIN}(Ï) = inf \left \{ r \geq 1: \ äëÿ \ ðåøåíèÿ \ çàäà÷è \ Ï \ $$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">ñóùåñòâóåò \ òàêîé \ ïðèáëèæ¸ííûé \ ïîëèíîìèàëüíûé \ àëãîðèòì \ A, \ $$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">÷òî \ R_A^{\infty} = r \left \} $$
Перечислим три основных типа оценок погрешности приближённых алгоритмов.
$$R_{MIN}(Ï) = \infty$$" title="$$. $$" align="middle" style="border: 0; vertical-align: middle">2.$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">1 < R_{MIN}(Ï) < \infty$$" title="$$. $$" align="middle" style="border: 0; vertical-align: middle">3.$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">R_{MIN}(Ï) = 1$$.
Если $$R_{MIN}(Ï) = 1$$, то можно выделить ещё 4 важных подслучая.
Задача $$Ï$$ может быть решена:
полиномиальной приближенной схемой (PTAS);
вполне полиномиальной приближенной схемой (FPTAS);
приближенным полиномиальным алгоритмом с асимптотической погрешностью ;
приближенным полиномиальным алгоритмом , для которого при некотором фиксированном выполнено неравенство $$|A(I) OPT(I)| \leq K$$ для любого входа .
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Определение (Гэри-Джонсон). Погрешностью приближённого алгоритма решения задачи $$Ï$$ назовём величину : $$R_A = inf \left\{ r \geq 1: \ R_A(I) \leq r \ äëÿ \ âñåõ \ I \in D_Ï \right \}$$.
эта... пусть множество $$M = \{ R_A(I), \ I \in \D_Ï \}$$
для каждого элемента множества M берём мажоранту
получаем множество верхних граней множества
затем из всех верхних граней надо выбрать минимальный элемент
зачем здесь инфинум???
открывая эту тему, планировала внести хоть и малозначимый, но свой, вклад в борьбу с невежеством и мракобесием
вот сейчас, наконец, стало ясно, что эту борьбу надо начинать с себя
----------------------------------------------------------------------------------------------------------------------------
Полиномиальные апроксимационные схемы, PTAS
(читается питас)
Полиномиальная апроксимационная схема - это набор или серия полиномиальных алгоритмов.
Идея апроксимационной схемы очень проста: для каждого фиксированного получаем полиномиальный алгоритм с погрешностью, не превосходящей .
Время работы такого алгоритма зависит от погрешности - чем меньше погрешность, тем дольше будет работать алгоритм.
Определение 7. Назовём апроксимационной схемой для оптимизационной задачи $$Ï$$ алгоритм , который, начиная работать на входе, состоящем из двух объектов - индивидуальной задачи $$I \in D_Ï$$ и заданной погрешности , выдаёт такое допустимое решение $$\sigma \in S_Ï(I)$$, что , или (для задачи минимизации).
Определение 8. Приближённая схема называется приближённой полиномиальной (апроксимационной) схемой (PTAS), если для каждого фиксированного соответствующий алгоритм имеет полиномиальную временную сложность.
Определение 9. Приближённая схема называется вполне полиномиальной приближённой схемой (FPTAS), если её временная сложность ограничена полиномом от и .
всё это, разумеется, непонятно, без примеров
как все псевдополиномиальные алгоритмы получаются из динамического программирования, так почти все полиномиальные апроксимационные схемы получаются масштабированием (с последующим округлением) исходных данных в псевдополиномиальных алгоритмах
примеры будут, чуть позже
эта... пусть множество $$M = \{ R_A(I), \ I \in \D_Ï \}$$
для каждого элемента множества M берём мажоранту
получаем множество верхних граней множества
затем из всех верхних граней надо выбрать минимальный элемент
зачем здесь инфинум???
открывая эту тему, планировала внести хоть и малозначимый, но свой, вклад в борьбу с невежеством и мракобесием
вот сейчас, наконец, стало ясно, что эту борьбу надо начинать с себя
----------------------------------------------------------------------------------------------------------------------------
Полиномиальные апроксимационные схемы, PTAS
(читается питас)
Полиномиальная апроксимационная схема - это набор или серия полиномиальных алгоритмов.
Идея апроксимационной схемы очень проста: для каждого фиксированного получаем полиномиальный алгоритм с погрешностью, не превосходящей .
Время работы такого алгоритма зависит от погрешности - чем меньше погрешность, тем дольше будет работать алгоритм.
Определение 7. Назовём апроксимационной схемой для оптимизационной задачи $$Ï$$ алгоритм , который, начиная работать на входе, состоящем из двух объектов - индивидуальной задачи $$I \in D_Ï$$ и заданной погрешности , выдаёт такое допустимое решение $$\sigma \in S_Ï(I)$$, что , или (для задачи минимизации).
Определение 8. Приближённая схема называется приближённой полиномиальной (апроксимационной) схемой (PTAS), если для каждого фиксированного соответствующий алгоритм имеет полиномиальную временную сложность.
Определение 9. Приближённая схема называется вполне полиномиальной приближённой схемой (FPTAS), если её временная сложность ограничена полиномом от и .
всё это, разумеется, непонятно, без примеров
как все псевдополиномиальные алгоритмы получаются из динамического программирования, так почти все полиномиальные апроксимационные схемы получаются масштабированием (с последующим округлением) исходных данных в псевдополиномиальных алгоритмах
примеры будут, чуть позже
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Большая размерность
возьмём для примера модельную задачу "Сумма размеров", но в реальной размерности
реальная задача об оперативном планировании отгрузки готовой листопрокатной продукции многокритериальная, выделим только один параметр - вес, и один критерий - набрать заданный вес с минимальным отклонением по модулю
Типичный вариант отгрузки - десять вагонов готовой продукции - составляет примерно пачек, массы пачек заданы в кг, масса отгружаемой продукции $$B = 620000êã$$, допустимое отклонение $$\pm 2000 êã$$.
Для ДП эта размерность слишком велика, более того, оперативное планирование отгрузки должно занимать секунды.
Попробуем применить метод масштабирования для динамического программирования.
Метод заключается в уменьшении всех заданных величин и в раз, где – коэффициент масштабирования, и последующим округлением до целого путем отбрасывания дробной части. Величина погрешности полученного таким образом решения не превосходит .
Применим метод масштабирования к типичному варианту отгрузки. В задаче об отгрузке погрешность набора веса является исходным данным и не должна превосходить $$2000 êã$$, отсюда . Для нашего примера получаем , откуда , что не дает существенного выигрыша в быстродействии.
Время работы алгоритма .
возьмём для примера модельную задачу "Сумма размеров", но в реальной размерности
реальная задача об оперативном планировании отгрузки готовой листопрокатной продукции многокритериальная, выделим только один параметр - вес, и один критерий - набрать заданный вес с минимальным отклонением по модулю
Типичный вариант отгрузки - десять вагонов готовой продукции - составляет примерно пачек, массы пачек заданы в кг, масса отгружаемой продукции $$B = 620000êã$$, допустимое отклонение $$\pm 2000 êã$$.
Для ДП эта размерность слишком велика, более того, оперативное планирование отгрузки должно занимать секунды.
Попробуем применить метод масштабирования для динамического программирования.
Метод заключается в уменьшении всех заданных величин и в раз, где – коэффициент масштабирования, и последующим округлением до целого путем отбрасывания дробной части. Величина погрешности полученного таким образом решения не превосходит .
Применим метод масштабирования к типичному варианту отгрузки. В задаче об отгрузке погрешность набора веса является исходным данным и не должна превосходить $$2000 êã$$, отсюда . Для нашего примера получаем , откуда , что не дает существенного выигрыша в быстродействии.
Время работы алгоритма .
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Масштабирование для задачи о рюкзаке
...продолжаем упражняться в масштабировании полиномиальных и псевдополиномиальных алгоритмов
На этот раз в качестве модельной задачи возьмём задачу "Рюкзак".
Дано конечное множество предметов , каждый предмет имеет целый положительный вес и стоимость , задано целое положительное число - ограничение на вес рюкзака. Требуется упаковать в рюкзак выборку предметов максимальной ценности, удовлетворяющую ограничению на вес рюкзака.
В скобках замечу, что если положить, что вес предмета равен его стоимости (), то из "Рюкзака" получим задачу "Сумма размеров", где - максимальная возможная стоимость, которую мы пытаемся набрать.
В качестве алгоритма её решения возьмём псевдополиномиальный алгоритм ДП.
Будем считать, что очень большими в этой задаче могут быть стоимости.
Разделим все стоимости на , где – коэффициент масштабирования, и округлим до целого путем отбрасывания дробной части.
Стоимость любого предмета в модифицированной задаче отличается от исходной стоимости не более чем на . В оптимальном решении может быть не более, чем предметов, поэтому величина суммарной погрешности не превосходит .
Пусть - стоимость оптимального рюкзака,
- стоимость оптимального рюкзака масштабированной задачи.
Умножаем оптимальную стоимость масштабированного рюкзака на коэффициент масштабирования и получаем величину приближённого решения .
Величина оптимального решения отличается от величины приближённого не более чем на : . (задача на максимум, оптимальная стоимость больше приближённой)
Коэффициент масштабирования можно взять так, как нам удобно.
Пусть , где - фиксированное целое положительное число, теперь величина приближённого решения зависит от .
Получаем или
.
Отсюда коэффициент относительной погрешности равен, после несложных преобразований:
.
Вычислительная сложность алгоритма ДП для исходной задачи равна или .
Вычислительная сложность решения отмасштабированной задачи равна
.
Теперь вспоминаем определение вполне полиномиальной приближённой схемы
Приближённая схема называется вполне полиномиальной приближённой схемой (FPTAS), если её временная сложность ограничена полиномом от и .
Мы получили вполне полиномиальную приближённую схему, для задачи о рюкзаке, и для задачи "Сумма размеров".
...продолжаем упражняться в масштабировании полиномиальных и псевдополиномиальных алгоритмов
На этот раз в качестве модельной задачи возьмём задачу "Рюкзак".
Дано конечное множество предметов , каждый предмет имеет целый положительный вес и стоимость , задано целое положительное число - ограничение на вес рюкзака. Требуется упаковать в рюкзак выборку предметов максимальной ценности, удовлетворяющую ограничению на вес рюкзака.
В скобках замечу, что если положить, что вес предмета равен его стоимости (), то из "Рюкзака" получим задачу "Сумма размеров", где - максимальная возможная стоимость, которую мы пытаемся набрать.
В качестве алгоритма её решения возьмём псевдополиномиальный алгоритм ДП.
Будем считать, что очень большими в этой задаче могут быть стоимости.
Разделим все стоимости на , где – коэффициент масштабирования, и округлим до целого путем отбрасывания дробной части.
Стоимость любого предмета в модифицированной задаче отличается от исходной стоимости не более чем на . В оптимальном решении может быть не более, чем предметов, поэтому величина суммарной погрешности не превосходит .
Пусть - стоимость оптимального рюкзака,
- стоимость оптимального рюкзака масштабированной задачи.
Умножаем оптимальную стоимость масштабированного рюкзака на коэффициент масштабирования и получаем величину приближённого решения .
Величина оптимального решения отличается от величины приближённого не более чем на : . (задача на максимум, оптимальная стоимость больше приближённой)
Коэффициент масштабирования можно взять так, как нам удобно.
Пусть , где - фиксированное целое положительное число, теперь величина приближённого решения зависит от .
Получаем или
.
Отсюда коэффициент относительной погрешности равен, после несложных преобразований:
.
Вычислительная сложность алгоритма ДП для исходной задачи равна или .
Вычислительная сложность решения отмасштабированной задачи равна
.
Теперь вспоминаем определение вполне полиномиальной приближённой схемы
Приближённая схема называется вполне полиномиальной приближённой схемой (FPTAS), если её временная сложность ограничена полиномом от и .
Мы получили вполне полиномиальную приближённую схему, для задачи о рюкзаке, и для задачи "Сумма размеров".
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Swetlana писал(а):Source of the post
Коэффициент масштабирования можно взять так, как нам удобно.
Пусть , где - фиксированное целое положительное число...
В момент масштабирования величину оптимального решения мы не знаем, увы
поэтому
Вместо нужно взять величину приближённого решения , полученную известным "жадным" (greedy) алгоритмом.
Про него (greedy algorithm) известно, что величина решения не более чем в раза отклоняется (меньше) от величины оптимального решения, а коэффициент уйдёт в константу О_большое.
Теперь надо про этот greedy algorithm для рюкзака рассказать, и заодно и его отмасштабировать, другим разом...
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Задача о рюкзаке. Жадные алгоритмы. Оценки относительной погрешности.
Жадный алгоритм.
1. Отсортируем предметы в порядке убывания их относительной стоимости (стоимости 1 кг):
.
2. Начнём с пустого рюкзака. Будем добавлять к нему предметы в порядке возрастания номеров. Если предмет проходит ограничение на вес рюкзака, он добавляется, иначе - отбрасывается.
Покажем, что мультипликативная погрешность такого алгоритма не ограничена сверху,
т.е. не существует , такой, что для всех индивидуальных задач
Жадный алгоритм.
1. Отсортируем предметы в порядке убывания их относительной стоимости (стоимости 1 кг):
.
2. Начнём с пустого рюкзака. Будем добавлять к нему предметы в порядке возрастания номеров. Если предмет проходит ограничение на вес рюкзака, он добавляется, иначе - отбрасывается.
Покажем, что мультипликативная погрешность такого алгоритма не ограничена сверху,
т.е. не существует , такой, что для всех индивидуальных задач
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Не понял, а если вместимость рюкзака 1 кг, всего предметов 10.Swetlana писал(а):Source of the post Покажем, что мультипликативная погрешность такого алгоритма не ограничена сверху,
т.е. не существует , такой, что для всех индивидуальных задач
И них самый дорогой и самый тяжелый акурат - брусок золота весом 1 кг.
То как тогда с С?
Последний раз редактировалось NT 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
<dummy>
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Computer Science»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 7 гостей