我正在處理一組L的地塊和一組C的縣。每個地塊L_i花費m美元，占地b英畝。每個縣C_i需要n英畝的地塊。現在假設如果分配給他們的最后一塊土地“超載”了他們的容量，這些縣并不關心獲得多于n英畝的土地。最后，L_i必須在C_i質心的x英里范圍內，才能考慮分配給C_i。
我設計了一種分配演算法來解決這個問題，使C_i達到n英畝，同時最小化成本m。但是，該設計的計算量非常大。令L_c為C_i x英里內的地塊。我的演算法按成本升序對L_c進行排序，分配前n英畝，然后移動到下一個縣。
關于如何提高效率的任何想法？是否有針對此類分配問題設計的既定演算法？
uj5u.com熱心網友回復：
這個問題例外困難。即使沒有“到質心的距離”限制，問題也會歸結為 NP-Complete 的 SUBSET-SUM（并且添加距離限制不會改變這一點）。簡短的、非正式的證明是，如果您想解決一個 SUBSET-SUM 的實體，并作為一個預言機解決這個問題，您可以讓 C_1 想要目標子集總和，而 C_2 想要其余的。也就是說，你不會找到一個有效的演算法來完美準確地解決這個問題。話雖如此，您可以獲得一個非常好的演算法，它非常快，犧牲了解決方案的準確性來大大加快它。
解決方案的想法與您的想法相似，除了您可以使用一些 BST 來查找最大尺寸但仍不會超出 C_i 限制的未選擇地塊，直到沒有額外的地塊溢位 C_i。然后，只需將您選擇的一個包裹替換為一個稍大的包裹，這樣您就可以達到或超過您的配額（或者，如果更容易的話，只需再拿一個包裹）。這將為其他城市留下盡可能多的土地，同時仍能滿足 C_i 的配額。然后，繼續前往下一個城市。
您可能可以嘗試使用某種形式的整數單純形來解決更好的近似值，但我不建議沿著這條路線走。很抱歉給你一個壞訊息，但你不會很快找到任何令人滿意的、100% 準確的高效演算法:(
uj5u.com熱心網友回復：
我認為這可以表述為分配問題的一個版本。作為一個實驗，我用所有隨機資料為此制定了一個 MIP（混合整數規劃）模型。
看起來像：
min sum(allowed(c,p),cost(p)*x(c,p))
sum(allowed(c,p),x(c,p)) <= 1 for all parcels p
sum(allowed(c,p),area(p)*x(c,p)) >= minacres for all counties c
x(c,p) ∈ {0,1}
筆記：
- c : 縣
- p：地塊
- allowed(c,p) 是允許的分配（即在距離內）
- x(c,p) 是二元決策變數（賦值）
對于 100 個縣和 1000 個地塊，很難找到經過驗證的最佳解決方案。但是，如果我們可以在達到差距（最佳解決方案和最佳可能解決方案之間的差異）時稍早停止，那么：
5% gap reached after 1 seconds
4% 1.5
3% 6
2% 275
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/437295.html