排序具有優先級的雙向單元連接

我有一個單元格的二維網格。在此模擬中，小區可能請求與另一個小區切換位置。該請求也具有優先權。排序具有優先級的雙向單元連接

問題是，我很難想出一個很好的方式來構造這個。如果A想用B切換，並且B也想用A切換，他們當前可以切換並切換回單個邏輯標記（這應該是不可能的）。

該解決方案可能涉及確保（A到B）==（B到A）並按照它們的優先級將它們排序到列表中。

這樣的數據結構是否有名字？任何人都認識到這個問題，並可以提供一些很好的閱讀鏈接

2009-07-24 Mizipzor

我不太瞭解問題的細節。它如何在單個邏輯節拍上切換兩次？是立即或稍後處理的交換機「請求」。 – Victor 2009-07-24 00:20:27

在邏輯記號的第一步中，每個單元格都會記錄它想要切換的單元格（或多個單元格）。當所有交換機都完成後，如果一個小區想要與另一個小區切換，則會選擇具有最高優先級的交換機。當兩個單元想要相互切換並且兩個文件分別獨立的SwitchRequest時，問題就出現了。如果兩者都處理完畢，自從切換並切換回去後，什麼都不會發生。 – Mizipzor 2009-07-24 00:25:25

我不能說，我以前遇到過一個例子就是這樣，所以我不知道它會被調用，但也許這樣的事情會工作...

細胞 - 一個類或結構

CELLID
x座標
y座標

SwitchRequest - 類或結構

RequestingCell
TargetCell
優先
CanSwitch

SwitchRequests - SwitchRequests陣列

個AlreadySwitchedCells - 細胞

陣列算法

對於每個刻度：

clear AlreadySwitchedCells 
build list of SwitchRequests 
sort SwitchRequests by Priority (highest to lowest) 
loop through each SwitchRequest 
{ 
    if (RequestingCell is not in AlreadySwitchedCells and TargetCell is not in AlreadySwitchedCells) 
    { 
    add RequestingCell and TargetCell to AlreadySwitchedCells 
    SwapCellIds(RequestingCell, TargetCell) 
    } 
}

注：有一些選擇這裏，像你是否應該使座標電池的特性或者將CellIds存儲在一個二維數組中，但希望這可以爲您提供一個起點。

來源

2009-07-24 01:39:29 devuxer

排序具有優先級的雙向單元連接

回答

相關問題