algorithm - SPOJ COURIER 的正确方法是什么

Question

我正在尝试解决 COURIER spoj 的问题。我能够理解我必须使用动态编程方法为此解决 TSP 但我无法完全理解我在同一对城市之间处理多个包裹的方法是否正确。我的伪代码如下所示:

1) Use floyd warshall to find all pair shortest path in O(n^3). Some pair of cities are connected by more than one roads, I can just keep the shortest one for my undirected graph.
2) Add the shortest cost for each request start to end.
3) Create a new directed graph for each of 12 requests and homecity. The node of this new graph will be a merge of each request's source and destination. The edge weight between a->b can be calculated by shortest path between 'a' request's destination to 'b' request's source.I am thinking of duplicating the pairs if I have multiple request between them.
4) Use a TSP DP to solve this new undirected 13 city TSP problem. O(n^2 2^n) would come around 1384448. Not sure whether this will time out for multiple test cases.

您能否提供您的意见，因为我创建这个新有向图的方法是否使问题复杂化了？我没有使用只有 5 个这样的不同请求的信息。我知道我可以解决这个问题并且知道，但我想先获得一些关于解决方案的建议。

Answer 1

好问题。

完成第1)点后，您可以忽略所有不是来源或送货地址的城市。

因此，您有旅行者当前所在的 10 个城市和 2^12 种可能的任务组合尚未完成。

你可以只用两个参数来做 DP:当前城市和要完成的交付，你可以用位掩码存储。

编辑:

如前所述，您有两个参数:p 跟踪当前位置，mask 跟踪您已经完成的访问。

掩码用作位掩码:http://en.wikipedia.org/wiki/Mask_%28computing%29

您从掩码 0 开始，二进制为 000000000000。例如，当您执行第 5 次请求旅行时，您将掩码更改为:000000010000 等。

您首先调用 f(p=0, mask=0)。

当你求解 f(p, mask) 时，你有两个选择。你可以搬到任何其他城市p2。如果这是您尚未完成的旅行之一，则可以进行旅行 p -> p2。在所有这些选项中，您必须选择最好的一个。

这个问题非常棘手，我建议首先使用位掩码解决更简单的问题。你可以在这里找到一些:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=778