java - 如何在具有加权节点和顶点的图中找到最佳路径

Question

假设我有这个图表

• 始终是完整的图表
• 一个起始节点 - 也是结束节点
• 加权节点和顶点

我想找到一条尽可能短但得分最高(节点点数总和)的路径 - 换句话说，一条路径不能比某个定义的常量更长，但能给我最好的点数。我想在同一个节点中启动和停止，并且不想遍历已经访问过的节点。

是否有任何算法可以帮助我解决这个问题，或者您有任何解决办法吗？

哦，这不是家庭作业，我只是想创建一个特殊的路径查找器。

编辑

到目前为止，我已经能够构建一个可以在几秒钟内找到某些路径的工作算法。但我没有得到我想要的分数——我只得到了期望分数的 85% 左右。如果我更改算法的参数，那么时间将以小时为单位甚至更多......

Answer 1

我不认为这比暴力破解更好。您可以计算所有路径直至一定的约束长度。然而，对于任意大的图来说，这将非常慢。如果您正在寻找可靠的猜测，我会从贪婪算法开始，该算法选择每长度点数最高的步骤，直到达到限制。然后，您可以添加一些内容，例如在过早填充的情况下进行反转(例如，如果您已经填充了 5 个，但您的限制是 6 个，并且当前节点没有长度为 1 的连接路径)，以了解其工作原理。