Ответ 1
РЕДАКТИРОВАТЬ: В соответствии с недавно добавленным ограничением, что каждый node можно посещать только один раз, проблема наиболее определенно NP-сложна с помощью сокращения до пути Гамильтона: для общего неориентированного, невзвешенного графика, задайте все веса ребер равными нулю, а каждый вес вершины равен 1. Тогда максимальная достижимая оценка равна n, если в исходном графе есть путь Гамильтона.
Так что неплохо было бы заглянуть в целочисленное линейное программирование, например, семейства, которые не были сконструированы специально, чтобы быть жесткими.
В приведенном ниже решении предполагается, что вершину можно посещать более одного раза и использует тот факт, что весы node ограничены константой.
Пусть p (x) - точечное значение для вершины x и w (x, y) - масса расстояния ребра {x, y} или w (x, y) = ∞, если x и y не смежны.
Если нам разрешено посещать вершину многократно, и если мы можем предположить, что p (x) <= C для некоторой константы C, мы можем уйти со следующей рекуррентностью: пусть f (x, y, P) быть минимальным расстоянием, которое нужно получить от x до y при сборке P-точек. Мы имеем
f (x, y, P) = ∞ для всех P < 0
f (x, x, p (x)) = 0 для всех x
f (x, y, P) = MIN (z, w (x, z) + f (z, y, P - p (x)))
Мы можем вычислить f, используя динамическое программирование. Теперь нам просто нужно найти наибольшее P такое, что
f (начало, конец, P) <= верхняя граница расстояния
Это P является решением.
Сложность этого алгоритма с наивной реализацией равна O (n ^ 4 * C). Если граф разрежен, мы можем получить O (n ^ 2 * m * C), используя списки смежности для агрегации MIN.