Оптимальность жадного алгоритма

Question

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

Например, у вас есть набор номеров $ \ mathcal {m}={1,2,3,4 \} $ и вы хотите разработатьАлгоритм для получения минимального количества целых чисел, необходимых для получения суммы 5. В этом случае $ 1,4 $ или $ 2,3 $ могут производить 5, и оба являются оптимальными решениями, поскольку минимальное требуемое число - это два.

Как доказать оптимальность алгоритма?

Я пытался противоречить, предположим, что существует оптимальное решение $ P ^ * $ и мой алгоритм не дает оптимального решения $ p \ neq p ^ * $ .Но я не знаю, как продолжить аргумент.

Answer 1

Это Изменение проблемы с изменением .Для некоторых наборов деноминаций (например, мощности некоторой базы $ B $ , монеты США или почти все системы монет в мире) жадный алгоритм дает минимальное количествоМонеты.Общий случай является NP-Complete, практическое решение требует динамического программирования (см. Статью понравившейся википедии).Для проверки, есть алгоритм многочлена времени для проверки, если данный набор деноминаций делает жадный алгоритм оптимальным или нет, см.3243 & pdf= rep1 & type= pdf "rel=" nofollow noreferrer "> Pearson (1994) " алгоритм полиномиального времени для проблемы с изменением" , doi 10.1.1.57.3243.

Answer 2

Если жадный алгоритм не всегда оптимален, то контрпример является достаточным доказательством этого.

В этом случае возьмите $ \ mathcal {m}={1,2,4,5,6 \} $ .Тогда для суммы 9 $ жадный алгоритм производит 6 + 2 + 1 $ Но это не оптимальноПоскольку 5 + 4 $ имеет меньше слагаемых.

Answer 3

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

Пусть установить $ s $ Быть оптимальным решением для некоторой проблемы, и наш жадный алгоритм дает набор $ P $ < / span>. Если оба $ p $ и $ S $ не выполняются. Предположим, что оба $ p $ и $ s $ разные, в этом случае жадный алгоритм будет выбрать Элемент в промежуточном этапе (локальный раствор), который менее оптимален, который привел к $ p $ , а не оптимальный набор $ S $ < / span>. Но в соответствии с жадным алгоритмом мы всегда выбираем локальное оптимальное решение. Следовательно, аргумент подтверждается доказательством противоречия.