Реферат Курсовая Конспект
Работа сделанна в 2002 году
Когда применим жадный алгоритм - Курсовая Работа, раздел Программирование, - 2002 год - "Математико" Когда Применим Жадный Алгоритм. Как Узнать, Даст Ли Жадный Алгоритм Оптимум П...
|
Когда применим жадный алгоритм. Как узнать, даст ли жадный алгоритм оптимум применительно к данной задаче Общих рецептов тут нет, но существует две особенности, характерные для задач, решаемых жадными алгоритмами.
Это принцип жадного выбора и свойство оптимальности для подзадач. 4. Принцип жадного выбора Говорят, что к оптимизационной задаче применим принцип жадного выбора greedy-choice property, если последовательность локально оптимальных жадных выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так на каждом шаге жадный алгоритм берет самый жирный кусок, а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.
Как доказать, что жадный алгоритм дает оптимальное решение Это не всегда тривиально, но в типичном случае такое доказательство следует схеме, использованной в доказательстве теоремы 1. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению для всякого решения есть другое, согласованное с жадным выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции. 5.
– Конец работы –
Эта тема принадлежит разделу:
Очень широко компьютер используется в логических играх, так как он дает возможность Компьютер дает возможность быстро и главное безошибочно… Итак, совершенно очевидно, что компьютер должен использоваться в логических… Изучая разного рода литературу по этому вопросу, можно отметить наличие широкого выбора оптимизационных алгоритмов.
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Когда применим жадный алгоритм
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов