4446
правок
Вершинное покрытие и деревья поиска: различия между версиями
Материал из WEGA
Вершинное покрытие и деревья поиска (посмотреть исходный код)
Версия от 00:27, 16 июля 2016
, 16 июля 2016→Ветвление и поиск
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
== Ветвление и поиск == | == Ветвление и поиск == | ||
Самой эффективной техникой является метод ветвления и поиска, широко использовавшийся в алгоритмах решения задачи о вершинном покрытии и многих других NP-полных задач. Этот метод можно описать следующим образом. Пусть (G, k) – экземпляр задачи о вершинном покрытии. Предположим, что каким-либо образом определено семейство <math>\{ C_1, ..., C_b \} \;</math> подмножеств графа G (где для каждого i подмножество <math>C_i \;</math> имеет <math>c_i \;</math> вершин), такое, что если граф G содержит вершинное покрытие из k вершин, то по меньшей мере для одного из подмножеств <math>C_i \;</math> существует вершинное покрытие из k вершин для G, содержащее все вершины из <math>C_i \;</math>. После этого можно построить семейство экземпляров меньшего размера <math>(G_i, k_i) \;</math>, где 1 | Самой эффективной техникой является метод ветвления и поиска, широко использовавшийся в алгоритмах решения задачи о вершинном покрытии и многих других NP-полных задач. Этот метод можно описать следующим образом. Пусть (G, k) – экземпляр задачи о вершинном покрытии. Предположим, что каким-либо образом определено семейство <math>\{ C_1, ..., C_b \} \;</math> подмножеств графа G (где для каждого i подмножество <math>C_i \;</math> имеет <math>c_i \;</math> вершин), такое, что если граф G содержит вершинное покрытие из k вершин, то по меньшей мере для одного из подмножеств <math>C_i \;</math> существует вершинное покрытие из k вершин для G, содержащее все вершины из <math>C_i \;</math>. После этого можно построить семейство экземпляров меньшего размера <math>(G_i, k_i) \;</math>, где <math>1 \le i \le b \;</math>; <math>k_i = k - c_i \;</math>, а <math>G_i \;</math> получается из G путем удаления всех вершин, входящих в <math>C_i \;</math>. Отметим, что исходный граф G имеет вершинное покрытие из k вершин в том и только том случае, если один из меньших экземпляров <math>(G_i, k_i) \;</math> графа <math>G_i \;</math> имеет вершинное покрытие из <math>k_i \;</math> вершин. Таким образом, процесс может быть разветвлен на b подпроцессов, каждый из которых на меньшем экземпляре задачи <math>(G_i, k_i) \;</math> рекурсивно выполняет поиск вершинного покрытия из <math>k_i \;</math> вершин для графа <math>G_i \;</math>. | ||
Пусть T(k) – количество листьев в дереве поиска для вышеописанного процесса ветвления и поиска на экземпляре задачи (G, k). Тогда операция ветвления дает следующее рекуррентное соотношение: | Пусть T(k) – количество листьев в дереве поиска для вышеописанного процесса ветвления и поиска на экземпляре задачи (G, k). Тогда операция ветвления дает следующее рекуррентное соотношение: | ||
<math>T(k) = T(k - c_1) + T(k - c_2) + ... + T(k - c_b) \;</math> | |||
Для решения этого рекуррентного соотношения положим <math>T(k) = x^k \;</math>, после чего оно будет выглядеть следующим образом: | |||
<math>x^k = x^{k - c_1} + x^{k - c_2} + ... + x^{k - c_b} \;</math> | |||
Можно доказать [3], что вышеприведенное полиномиальное уравнение имеет единственный корень <math>x_0 \;</math> больше 1. Исходя из этого, получаем <math>T(k) = x^k_0 \;</math>, что с точностью до полиномиального коэффициента задает верхнюю границу времени выполнения процесса ветвления и поиска на экземпляре (G, k). | |||
Простейший случай соответствует выбору вершины v степени d > 0 в графе G. Пусть <math>w_1, ..., w_d \;</math> – соседи вершины v. Тогда либо v входит в вершинное покрытие C из k вершин, либо, если v не входит в C, то все ее соседи <math>w_1, ..., w_d \;</math> должны входить в C. Таким образом, получаем набор из двух подмножеств <math>C_1 = \{ v \} \;</math> и <math>C_2 = \{ w_1, ..., w_d \} \;</math>, к которому может быть применен процесс ветвления и поиска. | |||
Эффективность операции ветвления и поиска определяется эффективностью определения семейства подмножеств вершин. Интуитивно кажется, что чем больше размеры подмножеств вершин, тем эффективнее операция. Для повышения размеров этих подмножеств было приложено немало усилий, в основном связанных с очень сложным и утомительным анализом и перечислением комбинаторных структур графов. В недавней статье [3] было получено семейство из двух подмножеств <math>C_1 \;</math> и <math>C_2 \;</math> размером <math>c_1 = 1 \;</math> и <math>c_2 = 6 \;</math>, соответственно, и другие семейства подмножеств вершин, которые оказались по меньшей мере не хуже указанных (техники кернелизации и свертки вершин играли большую роль в вычислении данных семейств). В результате был получен следующий алгоритм решения задачи о вершинном покрытии. | |||
Теорема 3. Задача о вершинном покрытии может быть решена за время <math>O(kn + 1,2852^k) \;</math>. | |||
Недавно коэффициент из теоремы 3 удалось улучшить, разработав алгоритм с временем выполнения O(kn + 1 | |||
Недавно коэффициент из теоремы 3 удалось улучшить, разработав алгоритм с временем выполнения <math>O(kn + 1,2738^k) \;</math> [4]. | |||
== Применение == | == Применение == | ||
