2

我试图在 SPOJ 上解决这个问题：

                  http://www.spoj.pl/problems/FISHER/

我想不出一个解决方案。我在 topcoder 上发现了一些线程，但我只能推断要使用 DP。如果有人可以指导我这将非常有帮助。

4

3 回答 3

2

如果你使用动态规划来解决正常的最短路径问题，你会得到http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm. 当然，这忽略了时间限制。您总是可以通过扩展状态空间来使动态规划算法更加灵活 - 但要付出一定的代价。在这种情况下，不是在每个节点上跟踪迄今为止找到的到该节点的最便宜路径的成本，您可以跟踪，因为 i = 1,2,3,4.. 最便宜路径的成本到该节点的时间最多为 i 的那个节点。您应该能够使用用于计算单个成本的递归变体来更新此成本数组 - 每个边松弛都采用给定时间的最便宜成本向量，并考虑在每个偏移量处添加该边的时间和成本以查看是否由此产生的扩展路径比迄今为止以该边缘结束的最知名路径更好。

我想知道您是否可以通过以类似方式转换 Dijkstra 算法来节省时间？至少，您可以先运行 Dijkstra 算法，然后丢弃所有节点的最短时间路径超过您的时间限制。

于 2012-05-17T19:32:11.227 回答
1

解决问题的另一种方法是使用 Dijkstra 算法http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/。约束是n<=50和time<=1000。设给定时间 = T。因此，我们将每个节点扩展为 T 个节点，其中dist[node][i]表示给定时间 i 到节点的最短路径。因此，我们将在具有边缘的n * T节点上运行算法，n * n * T这些边缘将在给定的时间约束内，复杂度为O((n * T + n * n *T) * log( N * T) ). 我接受的解决方案：http: //ideone.com/H8UUMf

于 2015-01-24T17:31:59.190 回答
0

使用动态规划。

如果所有花费时间少于该时间的路径都具有较高的成本，则您仅跟踪到节点的路径。当您看到一条新路径时，您可以使用二分搜索找到时间相同或更短的最长路径，然后仅在成本小于该路径且未超过时间限制时添加新路径。添加时，请删除所有需要更长时间且不便宜的现有路径。

您最终将获得按时间排列的最终节点的路径数组。选择适合时间限制的最便宜的。

请注意，您可能需要考虑一个节点的待办事项列表，并且一个节点可以多次出现在该待办事项列表上（每次找到一个新的廉价路径时，它都会返回它。）

于 2012-05-17T22:39:07.250 回答