假設我們有一個棋盤（任意大小）和最初放置在 N 個方格上的 N 個國王。讓我們假設現在我們選擇 N 個新方格讓國王通過一系列合法的移動（無碰撞）。目標是最小化所有國王移動的總距離。我真的想不出一種演算法/適應可以處理移動所有部分，同時注意防止“碰撞”國王。該演算法應該比遞回選擇目標方塊和選擇最小傳輸更快。我希望有人對這個問題有寶貴的建議。
謝謝
uj5u.com熱心網友回復：
首先，您需要找到所有國王和所有目標方格之間的最小總距離完全二分匹配。您可以重鑄這是一個最大重量雙邊匹配與重量（something_big距離）來代替每個距離，然后找到一個最大重量雙邊匹配，或者你可以保持不變，匹配完成，直接找到最低雙邊匹配.
我認為最簡單的方法是使用Edmonds-Karp 演算法。這通常用于查找最大流，但一旦添加單個源和匯頂點，最大權重二分匹配本質上就是該問題的一個實體。
一旦找到國王與其目標方格之間的匹配，您就可以移動國王。只要您沿著最短路徑移動每個國王，并且您不將國王移動到已經被占據的方格上，那么排列它們的順序并沒有太大區別。如果國王想進入一個被占領的方格，有兩種選擇：
- 如果中間的王還沒有到達它的目標方格，那么只需移動那個方格。
- 如果中間王已經在它的目標方格上，那么在你想要移動的王和中間王之間交換目標。然后只需移動王者。這不會改變您必須進行的移動總數。
當然，王合的路也可能有一個國王的方式，如此反復運用這些規則，直到你到達一個可以移動。
現在您可能想知道如果每個必須移動的國王都有自己的國王該怎么辦。只有當存在一個所有國王都想在回圈中移動的回圈時才會發生這種情況……但這不可能發生。
在一個周期內移動所有的國王需要移動，但它不會改變棋盤的狀態。因此，這種情況意味著您在原始映射中找到的路徑集不是最小的。由于它們是最小的，這樣的條件是不可能的。
uj5u.com熱心網友回復：
以下演算法應該有效：
- 找到距離最近的王更遠的目標方格。
- 將最近的國王移動到那個方格。（不會發生阻塞，因為一個國王必須更近才能阻止另一個國王）
- 重復直到所有國王都被移動到一個目標。
目標上的國王可能會在#2 中阻擋一個未移動的國王，但我不確定這會發生。
經過進一步思考，我很清楚我上面的演算法更像是貪婪方法啟發式，而不是確定性解決方案。我可以很容易地想出一個無法產生最佳解決方案的例子。
考慮當 N=4 在 [(1 to 5)x(1 to 5)] 板上時：
- K = {(2,2), (3,4), (4,3), (5,5)}，和
- T = {(1,1), (1,2), (2,1), (3,3)}
我的演算法將首先嘗試將 K:{(2,2), (3,4), (4,3)} 之一移動到 T:(3,3)，這是錯誤的。它應該將 K:(5,5) 移動到 T:(3,3) 并且可能不是首先。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/347693.html
下一篇：為什么我會收到與使用Hibernate的PosgreSQL表的自動增量PK相關的錯誤？錯誤：關系“hibernate_sequence”不存在