<<
>>

Алгоритм

Целью аппроксимирующего алгоритма является поиск вершинного покрытия одновременно с назначением цен.
Алгоритм можно рассматривать как жадный в отношении того, как он назначает цены. Затем цены используются для управле- ния выбором узлов вершинного покрытия.

Узел i называется насыщенным (или «оплаченным»), если

Vertex-Cover-Approx (G,w):

Присвоить pe = 0 для всех e e E Пока существует ребро e = (i,j), для которого ни i, ни j ненасыщенны Выбрать такое ребро e Увеличить pe без нарушения справедливости Конец Пока

Присвоить S множество всех насыщенных узлов Вернуть S

Для примера рассмотрим выполнение алгоритма для экземпляра на рис. 11.8. Изначально плотных узлов нет; алгоритм решает выбрать ребро (a, b). Он может поднять цену, оплачиваемую (a, b), до 3; в этот момент узел b становится плотным и повышение останавливается. Затем алгоритм выбирает ребро (a, d). Оно может поднять цену только на 1, так как в этот момент узел становится насыщенным (так как вес узла a равен 4 и он уже инцидентен ребру с оплатой 3). Наконец, алгоритм выбирает ребро (c, d).

Он может поднять цену, оплачиваемую (c, d), на 2, когда узел d становится насыщенным. В возникшей ситуации у каждого ребра имеется хотя бы один насыщенный конец, поэтому алгоритм завершается. Насыщенными являются узлы a, b и d; это и есть полученное вершинное покрытие. (Обратите внимание: это вершинное покрытие не минимально; для получения минимального покрытия следовало бы выбрать a и c.)

Рис. 11.8. Части (a)-(d) представляют шаги выполнения алгоритма назначения цены в экземпляре взвешенной задачи о вершинном покрытии. Числа в узлах обозначают веса; числа у ребер обозначают цены, выплачиваемые в ходе выполнения алгоритма

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

Еще по теме Алгоритм:

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