SPOJ COURIER 的正确方法是什么
What can be a correct approach for SPOJ COURIER
我正在尝试解决 spoj 上的 COURIER 问题。我能够理解我必须使用动态编程方法为此解决 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 个这样的不同请求的信息。我知道我可以解决这个问题，但我想先得到一些关于解决方案的建议。
好问题。
完成第1)点后，您可以忽略所有不是来源或收货地址的城市。
因此您有旅行者当前所在的 10 个城市和 2^12 种可能的任务组合尚未完成。
你可以只用两个参数来做 DP：当前城市和要完成的交付，你可以用位掩码存储。
编辑：
如前所述，您有两个参数：跟踪当前位置的 p 和跟踪您已经完成的访问的掩码。
掩码用作位掩码：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
我不知道你现在是否需要答案，但这是我所做的:
最初你的方法是正确的，你必须应用 floyd-warshall
获得最短距离 b/w 所有对。现在是经典的dp+bitmask
问题。只有12个操作，你要安排这12个操作
这样你就得到了最小值。
这可以通过使用位掩码来完成：000000000000
你有这 12 个状态 => 如果你选择一个，你不能再选择它。自从
(2^12=4096)这样的数，存储起来并不难
我的 dp 状态非常简单：'mask number' 和 'parent'
PARENT-> 你完成的最后一个操作
dp[遮罩][par]
希望这会有所帮助
我正在尝试解决 spoj 上的 COURIER 问题。我能够理解我必须使用动态编程方法为此解决 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 个这样的不同请求的信息。我知道我可以解决这个问题，但我想先得到一些关于解决方案的建议。
好问题。
完成第1)点后，您可以忽略所有不是来源或收货地址的城市。
因此您有旅行者当前所在的 10 个城市和 2^12 种可能的任务组合尚未完成。
你可以只用两个参数来做 DP：当前城市和要完成的交付，你可以用位掩码存储。
编辑：
如前所述，您有两个参数：跟踪当前位置的 p 和跟踪您已经完成的访问的掩码。
掩码用作位掩码：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
我不知道你现在是否需要答案，但这是我所做的:
最初你的方法是正确的，你必须应用 floyd-warshall 获得最短距离 b/w 所有对。现在是经典的dp+bitmask 问题。只有12个操作，你要安排这12个操作 这样你就得到了最小值。
这可以通过使用位掩码来完成：000000000000
你有这 12 个状态 => 如果你选择一个，你不能再选择它。自从
(2^12=4096)这样的数，存储起来并不难
我的 dp 状态非常简单：'mask number' 和 'parent'
PARENT-> 你完成的最后一个操作
dp[遮罩][par]
希望这会有所帮助