Главная » Java, Структуры данных и алгоритмы » Каскадный метод

0

Алгоритм Хаффмана для осуществления оптимального кодирования является примером применения алгоритмической проектной модели под названием каскадный метод (greedy method). Эта модель применяется в задачах оптимизации, когда требуется некая структура с минимизацией или максимизацией определенного свойства.

Стандартная конструкция модели greedy-мстода так же проста, как и в силовом методе. Для решения задачи оптимизации с помощью greedy-Me- тода рассматривается последовательность вариантов выбора. Последовательность оценивает некоторые определенные исходные условия. Затем модель запрашивает итеративный выбор еще нескольких вариантов, определяя наилучший. Однако такой подход не всегда ведет к оптимальному решению.

Но существуют задачи, в которых используется и такое решение. Эти задачи, как принято говорить, имеют свойство поглощающего выбора (greedy-choice property). Суть его заключается в достижении всеобщего оптимального условия посредством серии локальных оптимальных решений (то есть на каждой стадии из нескольких возможных вариантов выбирается наиболее выгодный), исходя из правильно поставленных предварительных условий. Задача вычисления префиксного кода с оптимальной переменной длиной — всего лишь один из примеров задач со свойством поглощающего выбора.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии