Разработка алгоритма

Ключом к построению эффективного алгоритма является массив M. В нем закоди- рована идея о том, что мы используем значение оптимальных решений подзадач для интервалов {1,2, ..., j} по всем j, и он использует (6.1) для определения значе- ния M [ j ] на основании значений предшествующих элементов массива.
Как только мы получаем массив M, задача решена: M[n] содержит значение оптимального решения для всего экземпляра, а процедура Find-Solution может использоваться для эффективного обратного отслеживания по M и возвращения оптимального решения.

Важно понять, что элементы M можно напрямую вычислять итеративным алгоритмом вместо рекурсии с мемоизацией. Просто начнем с M [0] = 0 и будем увеличивать j; каждый раз, когда потребуется определить значение M [ j ], ответ предоставляется (6.1). Алгоритм выглядит так:

Iterative-Compute-Opt

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий
  18. Правило разработки графических схем
  19. Правило разработки графических схем
  20. Правило разработки веера версий