Хабрахабр: Коллективные / Блоги / Захабренные Голосов: 10 Адрес блога: http://habrahabr.ru/blog/ Добавлен: 2007-10-24 18:05:40 блограйдером Robin_Bad

Алгоритмы / [Из песочницы] Задача о вершинном покрытии

2011-06-01 03:29:32 (читать в оригинале)

Введение.

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

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