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