Алгоритм прохождения k узлов неориентированного взвешенного графа (и возврата к исходной точке) с наименьшими затратами

Question

Я ищу алгоритм для следующих действий:

In an undirected, weighted graph with cycles

-find a path that visits exactly k nodes
-minimize the total cost(weight)
-each node can be visited only once
-return to the origin

edit: The start (and end) vertex is set in advance.

Если бы я хотел посетить все узлы, алгоритм Traveling Salesman (и все его варианты) работал бы. Но в моем случае «продавец» должен отправиться домой после посещения k узлов.

В этом случае хороши как приблизительные, так и точные алгоритмы.

Answer 1

Поскольку ваша задача включает в себя TSP для k = n в качестве особого случая, в общем случае она будет NP-полной. Для малых k вы можете адаптировать решение по динамическому программированию Bellmann (1962), чтобы решить его за время O (2 ^ k n ^ 3).

Пусть T (u, S) - длина кратчайшего маршрута, начиная с вершины u, в которой вершины из S уже посещены. Тогда вы хотите наименьшее из T (u0, {u0}) по всем начальным вершинам u0. Т удовлетворяет рецидиву

T(u,S) = min { d(u,v)+T(v,S+{v}) | v in V\S }     if |S|<k
T(u,S) = d(u,u0)                                  if |S|=k

для расстояний d (u, v). В таблице DP есть 2 ^ kn записей, каждая запись занимает O (n) времени для вычисления, и вы должны вычислить его n раз для каждой начальной вершины.