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

Как и в приведенных выше задачах, для этой задачи нетрудно предложить не- сколько естественных жадных алгоритмов. Но к счастью, это один из тех случаев, в которых многие из проверяемых в первую очередь жадных алгоритмов оказы- ваются правильными: все они решают задачу оптимально.
Сейчас мы рассмотрим некоторые из этих алгоритмов и при помощи метода замены выясним, какие при- чины лежат в основе этого семейства простых оптимальных алгоритмов.

Итак, перед вами три жадных алгоритма, каждый из которых правильно на- ходит минимальное остовное дерево.

♦ Один простой алгоритм начинает с пустого дерева и строит остовное дерево, последовательно вставляя ребра из E в порядке возрастания стоимости. При перемещении по ребрам в этом порядке каждое ребро e вставляется в том случае, если при добавлении к ранее вставленным ребрам оно не создает цикл. Если же, напротив, вставка e порождает цикл, то ребро e просто игнорируется, а выполнение алгоритма продолжается. Такое решение называется алгоритмом Крускала.

♦ Другой простой жадный алгоритм проектируется по аналогии с алгоритмом Дейкстры для путей, хотя на самом деле он определяется проще. Алгоритм на- чинает с корневого узла 5 и пытается наращивать дерево. На каждом шаге в уже существующее частичное дерево просто добавляется узел, который может быть присоединен с минимальной стоимостью.

Или говоря конкретнее, алгоритм поддерживает множество S ίΞ V, для кото- рого уже было построено остовное дерево. В исходном состоянии S = {5}. При каждой итерации S наращивается на один узел; при этом добавляется узел, минимизирующий «стоимость присоединения» mine=(u vyu^S ce, и ребро e = (u, v), обеспечивающее этот минимум в остовном дереве.

Такое решение называется алгоритмом Прима.

♦ Наконец, жадный алгоритм может представлять собой своего рода «алгоритм Крускала наоборот», а именно: он начинает с полного графа (V, E) и удаляет ребра в порядке уменьшения стоимости. При переходе к каждому ребру e (на- чиная с самого дорогого) это ребро удаляется, если это не приводит к потере связности текущего графа. Обычно этого алгоритм называется алгоритмом об- ратного удаления (насколько нам известно, с именем конкретного человека он никогда не связывался).

На рис. 4.9 изображены первые четыре ребра, добавленные алгоритмами Прима и Крускала соответственно, для геометрического экземпляра задачи нахождения минимального остовного дерева, в котором стоимость каждого ребра пропорцио- нальна геометрическому расстоянию на плоскости.


Рис. 4.9. Пример выполнения алгоритмов нахождения минимального остовного дерева: а — алгоритм Прима; b — алгоритм Крускала, для общих входных данных. Первые четыре ребра, добавленных в остовное дерево, обозначены сплошными линиями; следующее добавляемое ребро обозначено пунктиром


Тот факт, что каждый из этих алгоритмов гарантированно строит оптимальное решение, предполагает определенную «устойчивость» задачи нахождения мини- мального остовного дерева — ответ можно получить разными способами. Затем мы исследуем некоторые причины, из-за которых минимальные остовные деревья могут строиться настолько разными алгоритмами.

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