修改后的骑士旅行问题的最大流解
A maximum flow solution to a modified Knight travel problem
给你一个 n x n 的棋盘，上面有 k 个骑士（相同颜色）。有人在其中 k 个方块上洒了强力胶，如果一位骑士在其中一个胶方块上完成了他的移动，它就会永远卡住。此外（这就是为什么我们不能拥有好东西的原因）有人切掉了一些方块，所以棋盘上有洞。您将获得骑士的初始位置。骑士们的移动就像他们在普通国际象棋中所做的那样，但与普通国际象棋不同的是，每一轮所有的骑士都会同时移动（当然除了被卡住的那些）。在每一步结束时，一个方格不能被超过 1 个马占据。洞方格也不能被骑士占据（但它们确实算作骑士可以跳过的方格）。给出一个 0(t x poly(n)) 时间的算法来确定你是否可以使用 < t 移动将所有骑士从他们的初始位置移动到新的位置，在那里他们每个人都被困在一个胶水方块上。
我最初的想法是将这个问题表述为一个最大流问题，然后用Ford-Fulkerson算法来求解。但我不确定我的节点和边应该是什么。任何的想法？谢谢！
所描述的问题可以建模为分层网络问题，如下所示。网络的节点集由一个人工起始节点s和一个人工终端节点t组成。中间节点集由k份n * n个棋盘组成，也就是说有
个
2 + k * n * n
总共 个节点。想象 s 在顶部，然后是棋盘副本的 k 层。终端节点 t 将在底部。
将s连接到第一个棋盘中的初始马位置，并将t连接到第k个棋盘中马的所有所需终端位置。
对于每个 i in {1,...,k-1} 将第 i 个棋盘中的每个方格连接到 i+1 棋盘中的每个方格当且仅当它可以被合法的马移动到达.最后，删除所有留下超级粘合正方形的边（除非 t 是它的尾巴）并删除所有导致孔的边。此外，每条边都被限制为允许至少 0 且最多 1 的流量。总共，网络最多
2 * k + k * n * n = k * ( 2 + n * n )
边。进一步考虑到每个方格最多由一个马占据，每个中间节点的流量也必须受到 1 的约束。这可以通过将每个中间节点扩展为两个节点并通过附加边连接它们来完成，其中流量受 1 约束，这导致节点和边集最多增长 2.
当且仅当网络允许 s-t-价值流 k]，其中马的移动顺序和实现的网络流双射对应。
给你一个 n x n 的棋盘，上面有 k 个骑士（相同颜色）。有人在其中 k 个方块上洒了强力胶，如果一位骑士在其中一个胶方块上完成了他的移动，它就会永远卡住。此外（这就是为什么我们不能拥有好东西的原因）有人切掉了一些方块，所以棋盘上有洞。您将获得骑士的初始位置。骑士们的移动就像他们在普通国际象棋中所做的那样，但与普通国际象棋不同的是，每一轮所有的骑士都会同时移动（当然除了被卡住的那些）。在每一步结束时，一个方格不能被超过 1 个马占据。洞方格也不能被骑士占据（但它们确实算作骑士可以跳过的方格）。给出一个 0(t x poly(n)) 时间的算法来确定你是否可以使用 < t 移动将所有骑士从他们的初始位置移动到新的位置，在那里他们每个人都被困在一个胶水方块上。
我最初的想法是将这个问题表述为一个最大流问题，然后用Ford-Fulkerson算法来求解。但我不确定我的节点和边应该是什么。任何的想法？谢谢！
所描述的问题可以建模为分层网络问题，如下所示。网络的节点集由一个人工起始节点s和一个人工终端节点t组成。中间节点集由k份n * n个棋盘组成，也就是说有
2 + k * n * n
个节点。想象 s 在顶部，然后是棋盘副本的 k 层。终端节点 t 将在底部。
将s连接到第一个棋盘中的初始马位置，并将t连接到第k个棋盘中马的所有所需终端位置。
对于每个 i in {1,...,k-1} 将第 i 个棋盘中的每个方格连接到 i+1 棋盘中的每个方格当且仅当它可以被合法的马移动到达.最后，删除所有留下超级粘合正方形的边（除非 t 是它的尾巴）并删除所有导致孔的边。此外，每条边都被限制为允许至少 0 且最多 1 的流量。总共，网络最多
2 * k + k * n * n = k * ( 2 + n * n )
边。进一步考虑到每个方格最多由一个马占据，每个中间节点的流量也必须受到 1 的约束。这可以通过将每个中间节点扩展为两个节点并通过附加边连接它们来完成，其中流量受 1 约束，这导致节点和边集最多增长 2.
当且仅当网络允许 s-t-价值流 k]，其中马的移动顺序和实现的网络流双射对应。