Оптимальный путь в графе для максимизации значения

Я пытаюсь найти разумный алгоритм для этой проблемы:

Скажем, у нас есть множество мест. Мы знаем расстояния между каждой парой мест. В каждом месте также есть точка. Цель состоит в том, чтобы максимизировать сумму очков при перемещении от начального местоположения до места назначения без превышения заданного расстояния.

Вот простой пример: Начальное местоположение: C, Направление: B, Дано расстояние: 45

Решение: маршрут C-A-B с 9 точками

Мне просто интересно, есть ли какой-то динамический алгоритм для этого типа проблемы. Какой был бы лучший, или, скорее, самый простой способ решения этой проблемы?

Любая помощь очень ценится.

Изменить: Вам не разрешено посещать одно и то же место много раз.

Ответ 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.