Блог пользователя Azret

Автор Azret, 10 лет назад, По-русски

Доброго времени суток!

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

Собственно вопрос: Существует ли общая схема построения доказательства жадных алгоритмов и решений ДП?

Заранее спасибо. :)

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Доказательства должны подчиняться обычной математической логике, следственно общей схемы нет. Основные методы:

  • Индукция (к ней же можно отнести доказательство корректности перехода в динамике)
  • От противного
  • Непосредственный логический вывод из базовых утверждений в задаче
  • Сведение задачи к более известной и уже доказанной
»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +27 Проголосовать: не нравится

Очень часто жадность доказывается следующим способом:

1) Рассмотрим некоторый оптимальный ответ

2) Сделаем несколько его преобразований, не теряя при этом оптимальность

3) Ого, мы доказали, что существует оптимальный ответ у которого выполняется некоторое хорошее свойство, например крайний левый элемент входит в него, значит возьмем этот элемент и рекурсивно решим задачу для меньшего количества элементов.