Блог пользователя Murtazo.Ali

Автор Murtazo.Ali, история, 9 лет назад, По-русски

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

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

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

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

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

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

Общих методов конечно нет. Но для жадных алгоритмов существует теория матроидов, которая позволяет многое доказать (хотя часто намного проще доказать без матроидов). А ДП с точки зрения математики это просто мат. индукция: есть база для которой ответ считается на листочке (в редких случаях база это отдельная задача, которая например может быть решена динамикой) и переходы.

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

Тут тоже были обсуждения на эту тему.