对于我的一个项目，我正在尝试创建一个求解器，给定一组具有加权路径的随机加权节点，它将找到具有有限移动次数的最高得分路径。我创建了一个视觉对象来帮助描述问题。
为了完整起见，此示例显示了所有连接边。边上的数字是遍历成本，节点内的数字是分数。一个节点只有在遍历到它时才被计算在内，并且不能从它自己遍历到它自己。
正如您从图像中的描述中看到的那样，有一个开始/结束节点，其中包含随机放置的节点，每个节点都有一个任意分数。每个节点都连接到所有其他节点，并且每个连接都具有从剩余移动单元总数中减去的任意权重。为简单起见，您可以假设连接的权重是距离的函数。节点可以多次移动，并且再次应用它们的分数。目标是找到在给定移动限制下得分最高的循环路径。
求解器永远不会处理超过 30 个节点，通常处理 10-15 个节点。我仍然需要尝试让它尽可能快。
除了纯粹的蛮力方法之外，关于算法或方法的任何想法可以帮助我解决这个问题吗？
这是一个 O(mn^2) 时间的算法，其中 m 是移动次数，n 是节点数。
对于 {0, 1, ..., m} 中的每个时间 t 和每个节点 v，计算从起始节点开始到 v 结束的 t 步步行的最大分数，如下所示。如果 t = 0，则只有 walk，即在起始节点处不做任何事情，因此如果 v 是起始节点，则 (0, v) 的最大值为 0，否则为 -infinity（即不可能）。
对于 t > 0，我们使用 t - 1 的条目来计算 t 的条目。为了计算 (t, v) 条目，我们将 v 的分数加上 (t - 1, w) 条目的所有节点 w 的最大值之差减去从 w 到 v 的转移惩罚。换句话说，一个到 v 的最优 t 步步行包括从某个节点 w 到 v 的一步，然后是 (t - 1) 步步行到 w，并且这个 (t - 1) 步步行必须是最优的，因为历史不会影响未来得分。
最后，我们查看 (m, start node) 条目。要恢复实际的行走，需要向后工作并反复确定哪个 w 是最好的节点。