Почему найти самый длинный путь в графе сложно? - PullRequest
Новая
       17

Почему найти самый длинный путь в графе сложно?

0 голосов
/ 20 ноября 2018

Эта ссылка упоминает:

Самый длинный путь между двумя заданными вершинами s и t в взвешенном графе G - это то же самое, что и кратчайший путь в графе -Gполучен из G путем изменения каждого веса на его отрицание.Следовательно, если кратчайшие пути можно найти в -G, то самые длинные пути также можно найти в G.

Так почему поиск самого длинного пути является NP-трудной задачей, если это преобразование может уменьшить ее допроблема кратчайшего пути?

После преобразования у нас есть следующие случаи:

  • -G имеет отрицательный цикл, и в этом случае кратчайший путь в -G не может бытьfound
  • -G не имеет отрицательного цикла, и в этом случае алгоритм Флой-Варшалла или Беллмана-Форда может найти кратчайший путь в -G за полиномиальное время

Вопросы:

  1. Правильно ли говорить, что если нет отрицательного цикла, проблема поиска самого длинного пути не является NP-трудной?

  2. Правильно ли сказать, что при наличии отрицательных циклов между узлами все еще существует самый длинный simple path, который трудно найти NP?

  3. Если такПравильнее ли будет найти самый длинный простой путь вграфик является NP-сложным?

  4. Если это так, то из-за преобразования -G также правильно сказать, что поиск кратчайшего простого пути в графе такжеNP-hard?

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

Эта ссылка более подробно объясняет путаницу с проблемой самого длинного пути: https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869

1 Ответ

0 голосов
/ 20 ноября 2018

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

Беллман-Форд и аналогичные алгоритмы, с другой стороны, вычисляют кратчайший путь в графе (примечание: без просто ), то есть вершины можно повторять.

Итак, ваши четыре вопроса:

  1. Нет.Если в -G есть отрицательный цикл, самый длинный путь вообще не существует в G, потому что вы можете просто продолжать обходить цикл вечно.Самый длинный путь simple может все еще существовать, но с отрицательным циклом или без него, проблема может быть сведена к гамильтонову пути и поэтому все еще NP-трудна.
  2. Действительно!(Если график не ориентирован.)
  3. Да
  4. Да
...