中國郵差的變化問題_

爲了做好春季季度考試的準備，我正在學習和嘗試圖形問題。中國郵差的變化問題_

我已經熟悉了像「旅行推銷員」這樣的典型問題，但是當我深入研究「中國郵遞員問題」及其變化時，我立即覺得這個問題的一個重要方面缺失了：容量有限，因此需要在一定數量的n信件成功發送（爲了獲得新信件）後返回辦公室。那麼尋找最短路徑呢？

我對CPP非常感興趣，因爲它與現實生活中的相關性和易用性有關，但我認爲增加這個方面會使它更適合現實生活。

對於如何在無向圖中找到最短路徑的任何幫助感謝，該路徑至少訪問一次邊（CPP）必須返回到起點（後站）的限制字母數量被傳送。

EDIT（originial CPP的說明）：「中國郵遞員問題或郵遞員問題是要找到訪問一個（連接）無向圖的每條邊的最短閉合路徑或電路。當圖具有。一個歐拉電路（一個封閉的步行覆蓋每個邊緣一次），該電路是一個最佳解決方案如果圖形不是歐拉，它必須包含奇數度的頂點通過握手引理，必須有一個偶數爲了解決postman問題，我們首先找到一個最小的T-連接，我們通過T連接的兩倍來生成歐拉圖，原始圖中郵遞員問題的解決方案是通過找到新的歐拉電路來獲得圖「。 Src：wikipedia.org

來源

2012-04-11 Chicago1971

[這些詞語過濾器必須去...]（http://meta.stackexchange.com/questions/107989/using-the-word-problem-in-titles） – Mysticial 2012-04-11 21:22:36

請提供問題的描述或鏈接到一個很好的描述... – RBarryYoung 2012-04-11 21:24:27

*「我想聽聽你對這個問題的想法。」*不是一個正確的問題。如果你沒有問一個適當的編程問題，你會被社區關閉。 StackExchange論壇是Q + A論壇。他們不是討論論壇，他們絕對不是爲它設立的。 – RBarryYoung 2012-04-11 21:38:56

您的變體通過從所有值嚴格在B/4和B/2之間的例如3-partition problem減少爲NP-hard。它可能使用與capacitated vehicle routing相同的方法「解決」。不過，你必須明白，CPP不是一個真正的問題，而不是研究T-join的藉口。

來源

2012-04-11 22:19:59 oldboy

一個應用程序正在測試中，其中節點是狀態，並且您想要執行每個狀態轉換。雖然http://www.ams.jhu.edu/~castello/251/Handouts/ChinesePostman.doc聲稱，它真的對檢查或維修現實生活中的道路有用上。 – mcdowella 2012-04-12 04:12:26

感謝您的回答，老人。儘管如此，我仍然沒有發現任何類似於上面在瀏覽容量不同的車輛路徑問題時發佈的問題。 – Chicago1971 2012-04-12 13:24:00

如果您想盡量減少總距離，多輛車和多輛車之間沒有差別。 CVRP將爲有限容量的車輛提供所有客戶端*頂點*（而不是邊緣）。從您的問題到CVRP的一個可能的減少是將客戶端放在每個邊緣的中間。 – oldboy 2012-04-12 13:31:42

中國郵差的變化問題_

回答

相關問題