#algorithm #graph-theory #approximation #np
#алгоритм #теория графов #аппроксимация #np
Вопрос:
Рассмотрим проблему покрытия цикла: учитывая граф G, мы ищем множество C циклов, таких, что все вершины V (G) находятся по крайней мере в одном цикле C, а количество циклов в C минимально.
Моя задача — показать, что эта задача не допускает абсолютного приближения, т. Е. Не может быть алгоритма H такого, чтобы для всех экземпляров I задачи H (I) <= OPT(I) k, где OPT (I) — оптимальное значение для I, а k -число, большее или равное 1. Обычный метод состоит в том, чтобы показать, что если бы этот алгоритм существовал, мы могли бы решить за полиномиальное время некоторую NP-сложную задачу.
Кто-нибудь знает, какая проблема может быть использована для этого?
Комментарии:
1. Этот вопрос, похоже, не по теме, потому что речь идет о теории, а не о программировании
2. ну, это не первый раз, когда я публикую здесь вопросы о теории, и в связанных вопросах есть много похожих…
3. @user137227 Хотя я ответил на вопрос, я поддерживаю ваше мнение о том, что вопрос может быть не по теме, поскольку он теоретический и не связан с программированием.
Ответ №1:
Предположим, что существует алгоритм H
, такой, что существует положительное целое k
число, такое, что для каждого графа G
H(G)<=OPT(G) k
выполняется, где OPT(G)
обозначает минимальное количество циклов, необходимое для покрытия всех узлов G
, а время выполнения H
полиномиально ограничено в n
, где n
— количество узлов G
.
Учитывая любой граф G
, создайте граф G'
, состоящий из k 1
изоморфных копий G
; обратите внимание, что число узлов в G'
равно (k 1)n
, которое полиномиально ограничено n
. Могут возникнуть следующие два случая:
-
Если
G
содержит гамильтонов цикл, тоOPT(G')=k 1
иH(G')<=OPT(G') k=k 1 k=2k 1
. -
Если
G
не содержит гамильтонова цикла, тоOPT(G')>=2k 2>2k 1
, следовательноH(G')>2k 1
.
В целом, H
может использоваться для принятия решения в среде выполнения, ограниченной линейно, ограниченной в n
том G
, содержит ли гамильтонов цикл; однако, поскольку решение о том, имеет ли G
гамильтонов цикл, является NP
проблемой полного решения, это невозможно, если P=NP
не выполняется.
Примечание: Этот подход называется «созданием пробелов», поскольку экземпляры преобразуются таким образом, что в целевом значении
- оптимальные решения yes-экземпляров;
- неоптимальные решения экземпляров «да» и допустимые решения экземпляров «нет».