Алгоритмы - построение и анализ (1021735), страница 88
Текст из файла (страница 88)
Проанализируйте время работы алгоритма. (Указание: могут оказаться полезными концепции, изложенные в главе 22.) Теперь предположим, что каждому ребру (и, е) Е Е также сопоставляется неотрицательная вероятность р(е, а) перехода по этому ребру из вершины и. При этом издается соответствующий звук. Сумма вероятностей по всем ребрам, исходящим из произвольной вершины, равна !. По определению вероятность пути равна произведению вероятностей составляющих его ребер. Вероятность пути, берущего начало в вершине оо, можно рассматривать как вероятность "случайной прогулки", которая начинается в этой вершине и продолжается по случайному пути. Выбор каждого ребра на этом пути в вершине и производится в соответствии с вероятностями ребер, исходящих из этой вершины. б) Обобщите сформулированный в части а) ответ так, чтобы возвращаемый путь (если он существует) был наиболее вероятным из всех путей, начинающихся в вершине оо и имеющих метку ж Проанализируйте время работы этого алгоритма.
15-6. Передвижение по шахматной доске Предположим, имеется шахматная доска размером п х и клеток и шашка. Необходимо провести шашку от нижнего края доски к верхнему. Ходы Часть 1Ч. Усовершенствованные методы разработки н анализа 440 можно делать в соответствии со сформулированным далее правилом. На каждом ходу шашка передвигается в одну из следующих клеток: а) на соседнюю клетку, расположенную непосредственно над текущей; б) на ближайшую клетку, расположенную по диагонали в направлении вверх и влево (если шашка не находится в крайнем левом столбце); в) на ближайшую клетку, расположенную по диагонали в направлении вверх и вправо (если шашка не находится в крайнем правом столбце). Каждый ход из клетки х в клетку у имеет стоимость р (х, у), которая задается для всех пар (х, у), допускающих ход.
При этом величины р (х, у) не обязательно положительны. Сформулируйте алгоритм, определяюший последовательность ходов, лля которой стоимость полного пути от нижнего края доски к верхнему краю будет максимальной. В качестве начальной может быть выбрана любая клетка в нижнем ряду. Аналогично, маршрут может заканчиваться в любой клетке верхнего ряда. Чему равно время работы этого алгоритма? 15-7. Расписание для получения максимального дохода Предположим, что имеется один компьютер и множество, состоящее нз и заданий иы аз, ., а„, которые нужно выполнить на этом компьютере.
Каждому заданию а соответствует время обработки 1з, прибыль р и конечный срок выполнения Н . Компьютер не способен выполнять несколько заданий одновременно. Кроме того, если запущено задание аз, то оио должно выполняться без прерываний в течение времени 1 . Если задание а завершается до того, как истечет конечный срок его выполнения г)1, вы получаете доход р . Если же это произойдет после момента времени йз, то полученный доход равен нулю. Сформулируйте алгоритм, который бы выдавал расписание для получения максимальной прибыли.
При этом предполагается, что любое время выполнения задания выражается целым числом в интервале от 1 до и. Чему равно время работы этого алгоритма? Заключительные замечания Беллман (й. Вейшап) приступил к систематическому изучению динамического программирования в 1955 году. Как в названии "динамическое программирование", так и в термине "линейное программирование" слово "программирование" относится к методу табличного решения. Методы оптимизации, включающие в себя элементы динамического программирования, были известны и раньше, однако именно Беллман дал строгое математическое обоснование этой области [34].
Глава 15. Динамическое программирование 441 Ху (Ни) и Шинг (ЯЫп8) (159,160] сформулировали алгоритм, позволяющий решить задачу о перемножении матриц в течение времени О (и 18 п). По-видимому, алгоритм решения задачи о самой длинной общей подпоследовательности, время работы которого равно О (тп), — плод "народного" творчества. Кнут (Кппбп) [63] поставил вопрос о том, существует ли алгоритм решения этой задачи, время работы которого возрастало бы медленнее, чем квадрат размера. Масек (Мазек) и Патерсон (Ра~егзоп) ответили на этот вопрос утвердительно, разработав алгоритм, время работы которого равно О (гоп/18 п), где и ( т, а последовательности составлены из элементов множества ограниченного размера.
Шимански (Бгппапзк() (288] показал, что в особом случае, когда ни один элемент не появляется во входной последовательности более одного раза, эту задачу можно решить в течение времени О ((и+ гп) 18(п+ т)). Многие из этих результатов были обобщены для задачи о вычислении расстояния редактирования (задача 15-3). Ранняя работа Гильберта (ОВЬегг) и Мура (Мооге) (114], посвященная бинарному кодированию переменной длины, нашла применение при конструировании оптимального бинарного дерева поиска для случая, когда все вероятности р; равны О.
В этой работе приведен алгоритм, время работы которого равно О (пз). Ахо (АЬо), Хопкрофт (Норсгой) и Ульман ((Л1гпап) (5] представили алгоритм, описанный в разделе 15.5. Упражнение 15.5-4 предложено Кнутом (184]. Ху и Такер (Тис1сег) (161] разработали алгоритм для случая, когда все вероятности р; равны 0; время работы этого алгоритма равно О (пз), а количество необходимой для него памяти — О (и). Впоследствии Кнуту (185] удалось уменьшить это время до величины О(п18п).
ГЛАВА 16 Жадные алгоритмы Алгоритмы, предназначенные для решения задач оптимизации, обычно представляют собой последовательность шагов, на каждом из которых предоставляется некоторое множество выборов. Определение наилучшего выбора, руководствуясь принципами динамического программирования, во многих задачах оптимизации напоминает стрельбу из пушки по воробьям; другими словами, для этих задач лучше подходят более простые и эффективные алгоритмы. В жадном алгориигме (атеей а1яог1йш) всегда делается выбор, который кажется самым лучшим в данный момент — т.е. производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи. В этой главе рассматриваются задачи оптимизации, пригодные для решения с помощью жадных алгоритмов.
Перед освоением главы следует ознакомиться с динамическим программированием, изложенным в главе 15, в частности, с разделом 15.3. Жадные алгоритмы не всегда приводят к оптимальному решению, но во многих задачах они дают нужный результат. В разделе 16.1 рассматривается простая, но нетривиальная задача о выборе процессов, эффективное решение которой можно найти с помощью жадного алгоритма. Чтобы прийти к жадному алгоритму, сначала будет рассмотрено решение, основанное на парадигме динамического программирования„после чего будет показано, что оптимальное решение можно получить, исходя из принципов жадных алгоритмов. В разделе 16.2 представлен обзор основных элементов подхода, в соответствии с которым разрабатываются жадные алгоритмы.
Это позволит упростить обоснование корректности жадных алгоритмов, не используя при этом сравнение с динамическим программированием, как это делается в разделе 16.1. В разделе 16.3 приводится важное приложение методов жадного программирования: разработка кодов Хаффмана (НпПшап) для Глава 16.
Жадные алгоритмы 443 сжатия данных. В разделе 16.4 исследуются теоретические положения„на которых основаны комбинаторные структуры, известные под названием "матроиды", для которых жадный алгоритм всегда дает оптимальное решение. Наконец, в разделе 16.5 матроиды применяются для решения задачи о составлении расписания заданий равной длительности с предельным сроком и штрафами. Жадный метод обладает достаточной мощью и хорошо подходит для довольно широкого класса задач. В последующих главах представлены многие алгоритмы, которые можно рассматривать как применение жадного метода, включая алгоритмы поиска минимальных остовных деревьев (ш!и!шшп-зрапп!пп-ггее) (глава 23), алгоритм Дейкстры (Р!)кз1га) для определения кратчайших путей из одного источника (глава 24) и эвристический жадный подход Чватала (Сача!а!) к задаче о покрытии множества (зег-сочеппя) (глава 35). Алгоритмы поиска минимальных остовных деревьев являются классическим примером применения жадного метода.
Несмотря на то, что эту главу и главу 23 можно читать независимо друг от друга, может оказаться полезно читать их одна за другой. 16.1 Задача о выборе процессов В качестве первого примера рассмотрим задачу о составлении расписания для нескольких конкурирующих процессов, каждый из которых безраздельно использует общий ресурс. Цель этой задачи — выбор набора взаимно совместимых процессов, образующих множество максимального размера. Предположим, имеется множество Я = (аы аз,..., а„), состоящее из п нронессов (аспч!г!ез). Процессам требуется некоторый ресурс, который одновременно может использоваться лишь одним процессом.
Каждый процесс а; характеризуется начапьньгм моментом в; и конечны,ы моментом Д, где О < в; < Д < со. Будучи выбран, процесс а; длится в течение полуоткрытою интервала времени [в;, Г,). Процессы а, и а совместимы (сошрайЫе), если интервалы [в;, ~г) и [в, Г" ) не перекрываются (т.е, если гч > Д или в > гг). Задача о выборе процессов (асг!ч!гу-зе!ее!!оп ргоЫещ) заключается в том, чтобы выбрать подмножество взаимно совместимых процессов, образующих множество максимального размера. Например, рассмотрим описанное ниже множество Я процессов, отсортированных в порядке возрастания моментов окончания: (Вскоре станет понятно, почему удобнее рассматривать процессы, расположенные именно в таком порядке.) В данном примере из взаимно совместимых процессов можно составить подмножество (аз, аэ, аы). Однако оно не является максимапь- Часть 1Ч. Усовершенствованные методы разработки и анализа ным, поскольку существует подмножество (иы и4, ав, ам 1, состоящее из большего количества элементов.
Еше одно такое подмножество — (аз, а4, аш аы1. Разобьем решение этой задачи на несколько этапов. Начнем с того, что сформулируем решение рассматриваемой задачи, основанное на принципах динамического программирования. Это оптимальное решение исходной задачи получается путем комбинирования оптимальных решений подзадач. Рассмотрим несколько вариантов выбора, который делается в процессе определения подзадачи, использующейся в оптимальном решении. Впоследствии станет понятно, что заслуживает внимания лишь один выбор — жадный — и что когда делается этот выбор, одна из подзадач гарантированно получается пустой. Остается лишь одна непустая подзадача.
Исходя из этих наблюдений, мы разработаем рекурсивный жадный алгоритм, предназначенный для решения задачи о составлении расписания процессов. Процесс разработки жадного алгоритма будет завершен его преобразованием из рекурсивного в итерационный. Описанные в этом разделе этапы сложнее, чем те, что обычно имеют место при разработке жадных алгоритмов, однако они иллюстрируют взаимоотношение между жадными алгоритмами и динамическим программированием. Оптимальная подструктура задачи о выборе процессов Как уже упоминалось, мы начнем с того, что разработаем решение для задачи о выборе процессов по методу динамического программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
