什么是SPOJ COURIER的正确方法

我正试图解决关于spoj的COURIER问题。我能够理解，我必须用动态规划方法解决TSP问题，但我无法准确理解我在同一对城市之间处理多个包裹的方法是否正确。我的伪代码将有所如下：什么是SPOJ COURIER的正确方法

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个这样的不同请求的信息。我知道我可以把它弄清楚，但我想先解决一些解决方案。

来源

2015-04-14 Naman

不错的问题。

做完1）点后，您可以忽略所有不是来源地或交付地的城市。

因此，你有10个城市，其中旅客目前是和2^12可能的任务仍然完成的组合。

您可以使用两个参数做DP：当前城市和交付完成，您可以使用位掩码进行存储。

编辑：如前所述

你有两个参数：对跟踪当前位置和掩码跟踪其访问你已经做了。

面具作品位掩码：http://en.wikipedia.org/wiki/Mask_%28computing%29

你开始用面膜0，这在二进制是000000000000.当例如5要求的旅游你改变面膜：000000010000等

您可以通过启动调用f（p = 0，掩码= 0）。

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

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

来源

2015-04-15 08:51:53 Riko

非常感谢您的回答。我仍然无法知道如何让TSP多次访问多个城市进行多次交付？您可以添加一个小的pseuodcode或只是更多的描述。这将是很大的帮助。 – Naman

不需要感谢我:)只要upvote和接受，如果你喜欢我的回答:)将作出一个简短的编辑如何接近它，并让你休息给你 – Riko

我不知道，如果你现在还是不是需要的答案，但这里是我做过什么：

最初你的做法是正确的，你必须申请弗洛伊德，沃肖尔获得所有配对的最短距离。现在它是一个经典的dp + bitmask 的问题。只有12个操作，你必须安排这12个操作，使你得到最低限度。

这可以通过使用位掩码完成：000000000000
你有这12个州=>如果你选择一个，你不能再选择它。而且由于（2^12 = 4096）不会难以存储这样的数字。

我DP的状态都非常直截了当：“面具号”和“父”
父 - >您已经做

最后一次操作

DP [面膜] [面值]
希望这将有助于

来源

2016-08-23 19:27:10

什么是SPOJ COURIER的正确方法

回答

相关问题