algorithm - 按优先级对双向单元格连接进行排序

Question

我有一个二维的细胞网格。在这个模拟中，细胞可能会请求与另一个细胞交换位置。该请求也有一个优先级。

问题是我很难想出一个好的方法来构建它。如果 A 想和 B 切换，B 也想和 A 切换，他们目前可以在单个逻辑 tick 中切换和切换回来(这应该是不可能的)。

解决方案可能涉及确保 (A to B)==(B to A) 并按优先级将它们插入列表中。

这样的数据结构有名字吗？任何人都认识到这个问题并可以提供一些好的阅读链接？

Answer 1

我不能说我以前遇到过这样的例子，所以我不知道它会被称为什么，但也许这样的东西会起作用......

Cell - 类或结构

• 手机号
• X坐标
• Y坐标

SwitchRequest - 类或结构

• 请求单元格
• 目标单元格
• 优先级
• CanSwitch

SwitchRequests - 一组 SwitchRequests

AlreadySwitchedCells - 一组 Cell

算法

对于每个刻度:

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)
  }
}

注意:此处有一些选项，例如您是应该创建 Cell 的坐标属性还是仅将 CellId 存储在二维数组中，但希望这能为您提供一个起点。