什麼是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的正確方法

回答

相關問題