В нашем примере стоимость преобразования равна

3 • стоимость переноса + стоимость замены + + стоимость удаления + 4 • стоимость добавления + + стоимость транспозиции + стоимость удаления остатка.

Пусть даны последовательности ж[1..га] и у[1..га]. Тогда стоимость редактирования (edit distance) есть наименьшая стоимость цепочки преобразований, переводящей х в у. Разработайте алгоритм, основанный на динамическом программировании, который вычисляет стоимость редактирования и находит оптимальную цепочку преобразований. Оцените время работы и объём используемой памяти.

16-4 Вечеринка в фирме

Профессору поручено устроить вечеринку в фирме «ТОО КЛМН». Структура фирмы иерархична: отношение подчинённости задано деревом, корень которого- директор. Отдел кадров знает рейтинг каждого сотрудника (действительное число). Чтобы всем было весело, директор распорядился, чтобы никто не оказался на вечеринке вместе со своим непосредственным начальником.

а.Разработайте алгоритм, составляющий список приглашённых с наибольшим суммарным рейтингом.

б.Та же задача с дополнительным ограничением: директор должен быть в списке приглашённых.

16-5 Алгоритм Витерби

Динамическое программирование может быть применено к задаче распознавания речи. В качестве модели рассмотрим ориентированный граф G = (V, Е) и отображение а, сопоставляющее с каждым ребром (и, v) звук сг(и, v) из множества возможных звуков Е. В графе выделена некоторая вершина г>о- Каждому пути, начинающемуся в vo, соответствует последовательность звуков (элементов £).

а. Разработайте эффективный алгоритм, восстанавливающий путь в графе по последовательности s = (<7i, а2, , сгп) элементов £ (если требуемого пути не существует, алгоритм должен выдать соответствующее сообщение). Оцените время работы алгоритма. (Указание: вам могут пригодиться некоторые идеи из главы 23).

Пусть теперь для каждого ребра (и, v) £ Е известна вероятность пройти по ребру из и в v (издать соответствующий звук); обозначим эту вероятность p(u,v). Мы предполагаем, что для любой вершины и сумма вероятностей р(и, v) по всем рёбрам, выходящим

из этой вершины, равна единице. Вероятностью пути считаем произведение вероятностей, соответствующих его рёбрам (т.е. последовательные выборы считаем независимыми).

б.. Модифицируйте построенный в (а) алгоритм так, чтобы он находил наиболее вероятный путь, соответствующий данной последовательности звуков. Оцените время работы модифицированного алгоритма.

Замечания

Систематическое изучение динамического программирования было начато Р. Беллманом в 1955 году [21], хотя некоторые приёмы такого рода были известны и ранее. Кстати, слово «программирование» (programming) в словосочетаниях «динамическое программирование» (dynamic programming), а также «линейное программирование» (linear programming) не означает составление программ для компьютера.

Ху и Шинг [106а, 106Ь] придумали работающий за время О (га log га) алгоритм для задачи о порядке перемножения матриц; они же указали соответствие между этой задачей и задачей об оптимальной триангуляции.

Алгоритм для нахождения наибольшей общей подпоследовательности за время 0(тп) относится, видимо, к фольклору. В работе [43] Кнут поставил вопрос, возможен ли для этой задачи субквадратичный алгоритм. Масек и Патерсон [143] показали, что возможен, найдя алгоритм, работающий за время 0(тп/ log га) при га то и фиксированном размере множества, из которого берутся члены последовательностей. Для случая, когда в последовательностях нет повторений, алгоритм с оценкой 0((п + то) log(ra + то)) построен в статье Шимански [184]. Многие из этих результатов обобщаются на задачу о стоимости редактирования (задача 16-3).

17Жадные алгоритмы

Для многих оптимизационных задач есть более простые и быстрые алгоритмы, чем динамическое программирование. В этой главе мы рассматриваем задачи, которые можно решать с помощью жадных алгоритмов (greedy algorithms). Такой алгоритм делает на каждом шаге локально оптимальный выбор, - в надежде, что итоговое решение также окажется оптимальным. Это не всегда так - но для многих задач такие алгоритмы действительно дают оптимум. Наш первый пример - простая, но не вполне тривиальная задача о выборе заявок (раздел 17.1). Далее (раздел 17.2) мы обсуждаем, для каких задач годятся жадные алгоритмы. В разделе 17.3 рассказывается о сжатии информации с помощью кодов Хаффмена, которые строятся жадным алгоритмом. Раздел 17.4 посвящен так называемым матроидам - комбинаторным объектам, связанным с жадными алгоритмами. Наконец, в разделе 17.5 мы применяем матроиды к задаче о расписании для заказов равной длительности со сроками и штрафами.

В следующих главах мы не раз встретимся с жадными алгоритмами (задача о минимальном покрывающем дереве, алгоритм Дейкстры поиска кратчайших путей из данной вершины, жадная эвристика Хватала для задачи о покрытии множества и другие). Минимальные покрывающие деревья - классический пример использования жадного алгоритма, так что параллельно с этой главой можно читать главу 24.

17.1. Задача о выборе заявок

Пусть даны п заявок на проведение занятий в одной и той же аудитории. Два разных занятия не могут перекрываться по времени. В каждой заявке указаны начало и конец занятия (s8- и /г-для г-й заявки). Разные заявки могут пересекаться, и тогда можно удовлетворить только одну из них. Мы отождествляем каждую заявку с промежутком [s8,/8), так что конец одного занятия может совпадать с началом другого, и это не считается пересечением.