Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Приближенный алгоритм решения задачи о вершинном покрытии



Пусть E – множество ребер графа G, VP – искомое множество вершин вершинного покрытия графа G.

VP:=[]; {изначально множество VР пусто}

Е:=<множество всех ребер графа>;

While E<>[] Do Begin{пока множество ребер не пусто}

<выбрать ребро (u, v) из Е>;

VP:=VP+[u]+[v];

<удалить из E все ребра, инцидентные вершинам u и v>

End;

Выполним трассировку алгоритма на примерах, обозначив через А множество выбираемых ребер графа.

Пример 1

  А VP Е
  [] [] [1..9]
  [1] [1,3] [6..9]
  [1,6] [1,2,3,5] []

Найденное решение VP =[1,2,3,5] оптимально.

Пример 2

  А VP Е
  [] [] [1..7]
  [1] [1,3] [4,6,7]
  [1,4] [1,2,3,5] [7]
  [1,4,7] [1..6] []

Найденное решение не оптимально. | VP |=6, а | VPОПТ |=3.

Теорема. Данный приближенный алгоритм решения задачи о вершинном покрытии работает с ошибкой не более чем в 2 раза.

Доказательство. Очевидно (по построению), что множество VP – множество вершин вершинного покрытия.

А – множество ребер, выбираемых в ходе работы алгоритма. Никакие два ребра из А не имеют общих вершин (по построению), следовательно, |VP|=2·|A| или .

Оптимальное вершинное покрытие VPОПТ содержит хотя бы одну из двух вершин выбранных в А ребер, следовательно, | A |≤| VPОПТ |.

Из полученных равенства и неравенства | A |≤| VPОПТ | следует, что . Это означает, что найденное решение не более чем в два раза превосходит оптимальное, т. е. алгоритм работает с ошибкой не более чем в два раза.

Вопросы по главе для самоконтроля

1. Сформулируйте определение массовой проблемы.

2. Сформулируйте определение NP -полной задачи.

3. Сформулируйте нерешенные задачи теории NP -полноты.

4. Сформулируйте определение полиномиальной сводимости.

5. На чем основан способ доказательства NP -полноты задач?

6. Что называется схемой приближения?

7. Что называется полностью полиномиальной схемой приближения?

8. Что значат слова «алгоритм работает с ошибкой не более чем в n раз»?

9. Привести пример графа, для которого приближенный алгоритм решения задачи о вершинном покрытии дает

a) точное решение;

b) решение с ошибкой ровно в два раза.

10. Известно, что задача о ВЕРШИННОМ ПОКРЫТИИ и задача о КЛИКЕ взаимно дополнительны: минимальное вершинное покрытие является дополнением к максимальной клике в графе-дополнении. Можно ли отсюда заключить, что приближенный алгоритм решения задачи о ВЕРШИННОМ ПОКРЫТИИ даст решение и для задачи о КЛИКЕ с такой же погрешностью? Ответ обоснуйте.





Дата публикования: 2015-07-22; Прочитано: 775 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...