Как найти цикл, содержащий набор узлов на графике?

Question

Учитывая график неправомерного g = (v, e) и набор узлов P. Мне нужно найти цикл (не самый короткий цикл длины), содержащий эти узлы? Как мне найти этот цикл?

Answer 1

Содержит гамильтонианский цикл (для P = V), отсюда решение о решении (просто зная, если есть такая вещь), является NP-Complete. Таким образом, нет эффективного алгоритма, если P = NP.

Answer 2

Я бы, вероятно, начал бы проектировать алгоритм, выбрав первый узел в P (давайте назовем его P [0]), а затем выполнили поиск по глубине из P [0], обращая внимание на любое время p [0] снова достигнут. Вам придется сохранить путь, по которым можно было пересмотреть p [0] (или, по крайней мере, были ли другие узлы P), чтобы вы знали, что любой цикл, который вы найдете, содержит все узлы в P. То же самое, что и для поиска по глубине, который, я считаю, это O (V + E).

Кто-то может придумать лучшее решение, и некоторые эвристики могут быть применены, чтобы помочь, но это должно вас начать. (Например, вы можете сделать вывод, вы должны начать на узле P с наименьшим краям, а не начать с p [0].)

Редактировать:

Еще одна вещь, о которой я подумал ... Когда вы достигаете другого узла в P через ваш поиск первого глубины, нет необходимости в DF, чтобы «начать начать» с самого начала или рассмотреть пути, которые не включают это в новее -Нугольный узел. Это свойство может помочь вашему алгоритму быстрее в случае, если такой цикл не существует.

Дальше редактирование:

Не берите в голову Последнее редактирование - он будет работать только, если его можно установить, что нет узла в P на другом пути между p [0] и узел в P достигли, который не может быть достигнут другим способом, и мы не будем знать, что наверняка, не делая целых dfs.

Что касается ответа на гамильтонианские циклы, я не знаю, как обнаружение цикла в задачей, выполняемой NP. Да, нам пришлось бы пройти через весь график (все вершины и ребра), достижимые с начальной точки, чтобы определить, существует ли цикл, соответствующий критериям проблемы под рукой. Кроме того, нам нужно знать, вступив в контакт с ранее посещаемой вершиной, какая «прямая путь» вершины будет определять, существует ли цикл, соответствующий критериям. Поскольку мы не заботимся о самом коротком цикле, я не уверен, как мы обязательно пытаемся найти гамильтонский цикл. Хотите просветить?