algorithm - 使用邻接规则随机化循环链表

Question

假设您有一张任意大小的大圆 table ，您希望让所有客人大部分随机坐在 table 旁，但有一些关于相邻的规则。

示例:Alice、Bob、Charlie、Dan、Eve、Frank、Gerry 和 Heidi 要来吃晚饭。创建一个随机的座位安排，使 Alice 不在 Gerry 旁边，Charlie 也不在 Frank 旁边。

到目前为止，因为我很懒惰而且它有效，所以我一直在通过洗牌列表来做到这一点，然后如果结果违反任何邻接限制则重新洗牌。不过，我很幸运，我的“客人名单”很大，我的限制很少，所以失败的情况很少见。

我猜更好的解决方案包括:

• 使用尾递归，以便我只在解决冲突所需的范围内进行备份，而不是重新排列整个列表并希望获得最佳结果。
• 根据每个条目的排除数量对初始列表进行排序，以便首先解决“比较复杂”的项目，同时在尾部保留更多选项。

虽然我正在研究它，但我发现自己想知道是否有一种方法可以预先检测某个列表的邻接排除是否无法满足。也许通过构建“合法”选项树并查看其深度是否<列表的长度？

Answer 1

在不偏向分布的情况下向采样空间添加约束可能非常困难。如果您进行部分回溯，那么您将较早放置的项目优先于较晚放置的项目，使较早放置的项目的分布更接近(无约束的)随机洗牌的预期分布，同时放大约束对后来的影响 -放置的。考虑这样一种情况，只允许 Alice、Yolanda 和 Zelda 坐在 Beth 旁边。如果你按字母顺序分配座位，当你遇到无法解决的情况时回溯，Alice 比其他两个中的任何一个都不太可能最终排在 Beth 旁边，因为 Beth 最初不太可能被安排在 Alice 旁边，而且你的回溯永远不会让你移动贝丝。

你所说的“懒惰”被称为rejection sampling ，它通常是解决这类问题的首选方法，所以不要低估它。对于您要拒绝很多空间的情况，有几种拒绝抽样的变体，一旦您了解它们就可以很好地工作。使用 the Metropolis-Hastings algorithm 也取得了不错的效果，这(IMO)更容易理解和利用。如果您只想要一个样本，则可以执行老化阶段，然后只获取当前状态。