У меня есть неориентированный граф, и я хотел бы найти в нем все возможные пути, соединяющие все узлы заданного набора. Это проблема НП? Есть ли алгоритм для этого или хороший способ сделать это? Меня не волнует порядок, в котором каждый путь касается узлов в наборе, мне просто нужно пройти через каждый из них.
Как найти все пути в неориентированном графе, касающиеся всех узлов заданного множества
Ответы (1)
Она называется гамильтоновой проблемой пути и является NP-полной.
Подробная информация: https://en.wikipedia.org/wiki/Hamiltonian_path_problem
person
Şafak Özdek
schedule
15.11.2017
Сначала, как и вы, я думал о задаче о гамильтоновом пути, но она не совсем соответствует моему сценарию, или, по крайней мере, я не понимаю, как это могло бы быть, в графе есть другие узлы, а не только те, что в заданном набор: я хочу, чтобы каждый путь касался их всех, но меня также интересуют те узлы в графе, через которые проходит путь и которые не входят в набор.
- person Alessandro Oddi; 16.11.2017
@AlessandroOddi В худшем случае ваш набор включает все узлы в графе, поэтому он ограничен сверху гамильтоновой проблемой пути, если гамильтонова задача пути является NP-полной, то ваша проблема также является NP-полной.
- person Şafak Özdek; 04.03.2020
