比方说，我有这个图如何找到与加权节点图的最佳路径和顶点
我想找到尽可能短但路径st得分（节点的总和） - 换句话说，一条路径不能长于某个定义的常数，但给我最好的点数。我想在同一个节点上启动和停止，并且不想过去已经访问过的节点。
是否有任何算法可以帮助我解决这个问题，或者您有什么想法如何解决它？
哦，它的不是作业，我只是想创建一个特殊的路径查找器。
编辑
到目前为止，我已经能够建立一个工作算法可以在几秒钟一些路径。但是我没有得到我想要的分数 - 我只获得了所需分数的大约85％。如果我更改算法的参数，那么时间将在几小时内和更多...
我不认为这是可以解决比蛮力时间更好。你可以计算出全部路径达到一定的约束长度。但是，对于任意大的图表来说，这将非常缓慢。如果你正在寻找一个可靠的猜测，我会从一个贪婪算法开始，选择每个长度值最高的步骤，直到达到极限。然后，您可以在提前填充的情况下（例如，如果您已经过了5次，但是您的限制为6，并且您的当前节点没有连接的长度路径）添加事物，例如反向，以了解它是如何工作的。
我认为你是对的。这似乎是一个NP问题。我不知道如何将有效的算法与路径搜索相结合。具有启发式和分支界限的蛮力仍然没用 - 时间非常长，因为我有大约80个节点。 – user219882 2012-03-18 20:37:42
我不知道这是否会实际工作，但这些都是我最初的想法：
也许用最大生成树尝试（普里姆的或Kruskal的）。由于您不想重复顶点，因此您的路径必须最终成为cycle图表。走生成树（也许某种贪婪算法？），一旦你点击一片叶子，回到开始顶点（因为原始图是完整的图）。如果没有负边权重，这只会起作用（可能）。
现在只是想一想 - 这是深夜，我会在早上仔细观察。 :)
该图是否定向？否则：找到最小权重边缘'（u，v）'，使得'u'是你的源，'（u，v），（v，u）'是最短路径。你没有提到两次使用同一条边的问题。 – amit 2012-03-17 18:14:12
它没有指示。当然，我不能两次使用相同的边缘 - 这将打破我无法浏览已经访问过的节点的情况。 – user219882 2012-03-17 18:16:16
如您所说，如果它也是目标节点，则必须访问源两次。路径将是：'v - > ... - > v'，并且'v'必须被访问两次。 – amit 2012-03-17 18:16:55