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