Как найти лучший путь в графе с взвешенными узлами и вершинами

Question

Допустим, у меня есть этот график

• всегда полный граф
• один начальный узел - также конечный узел
• взвешенные узлы и вершины

Я хочу найти путь максимально короткий, но с лучшим счетом (суммой точек узлов) - другими словами, путь, который не может быть длиннее определенногопостоянный, но дайте мне лучшее количество очков.И я хочу запускать и останавливаться в одном и том же узле и не хочу проходить через уже посещенные узлы.

Существуют ли алгоритмы, которые могут помочь мне с этой проблемой, или у вас есть идеи, как ее решить??

О, и это не домашняя работа, я просто хочу создать специальный искатель пути.

РЕДАКТИРОВАТЬ

До сих пор я был в состоянии построить работающий алгоритм, который может найти какой-то путь за несколько секунд.Но я не получаю желаемого количества баллов - я набираю только около 85% желаемого результата.И если я изменю параметры алгоритма, то время будет в часах и более ...

Answer 1

Я не думаю, что это разрешимо лучше, чем время перебора.Вы можете рассчитать все пути до определенной длины ограничения.Однако для сколь угодно большого графика это будет очень медленно.Если вы ищете надежную догадку, я бы начал с жадного алгоритма, который выбирает шаг с наибольшим значением Points per Length, пока не будет достигнут предел.Затем вы можете добавить такие вещи, как реверсирование в случае преждевременного заполнения (скажем, если вы перешли на 5, но ваш лимит равен 6, а ваш текущий узел не имеет путей длиной один, подключенных), чтобы узнать, как это работает.

Answer 2

Я не уверен, сработает ли это на самом деле, но это мои первые мысли:

Возможно, попробуйте использовать максимальное связующее дерево (Прима или Крускала).Поскольку вы не хотите повторять вершины, ваш путь должен в конечном итоге быть графом цикл .Пройдите по остовному дереву (может быть, какой-то жадный алгоритм?) И, как только вы нажмете на лист, вернитесь к начальной вершине (поскольку исходный граф был полным графом).Это сработало бы (возможно), если бы не было отрицательных краевых весов.

Просто некоторые мысли на данный момент - уже поздно ночью, утром я посмотрю поближе.:)