Алгоритм: кратчайший путь, проходящий через m различных узлов
Предположим, у меня есть взвешенный граф с n вершинами и задана начальная точка. Кратчайший путь определяется как путь с наименьшей суммой весов.
Как найти кратчайший путь, проходящий через m различных вершин? (каждая вершина может быть посещена один или несколько раз. То есть в наборе посещенных вершин ровно m вершин, но каждая вершина может быть посещена несколько раз.)
Обратите внимание, что задано число m, но нет конкретных m вершин. (Эти m вершин выбраны алгоритмом)
Это NP-сложная задача?
Как определяется «кратчайший»?
Я голосую за то, чтобы закрыть этот вопрос, потому что мне кажется, что он должен быть на Математике
@МоБ. Каждое ребро имеет вес, а кратчайший путь определяется как путь с наименьшей суммой весов. В наборе посещенных узлов ровно m узлов, но каждый узел может быть посещен несколько раз.
Хорошо, это важная информация, которой не хватало. Пожалуйста, отредактируйте вопрос соответствующим образом.
Это обобщение задачи коммивояжера (где m=n), так что это означает, что она np-трудна.
Похоже, это можно решить с помощью некоторой формы en.wikipedia.org/wiki/Breadth-first_search
Ответы 1
Мы можем свести Задачу о гамильтоновом пути (HPP) к вашей задаче: гамильтонов путь — это путь в ориентированном невзвешенном графе, который посещает каждую вершину ровно один раз. Чтобы решить пример HPP, преобразуйте граф во взвешенный граф с весом 1 на каждом ребре, установите m равным |V| и решите свою задачу. Это полиномиальное сокращение времени, поэтому ваша задача NP-сложна, поскольку HPP NP-полна.
Он также NP-полный, так как явно находится в NP. Таким образом, существует также полиномиальное сокращение вашей задачи до любой другой NP-полной задачи. Алгоритмы решения задачи коммивояжера, вероятно, наиболее подходят для вас: подробности и примеры смотрите здесь.
Такое чувство, что это должно быть на Математике