仅利用30行Python代码来展示X算法

站长资源 2024/11/24 佚名

2 0 1

假如你对数独解法感兴趣，你可能听说过精确覆盖问题。给定全集 X 和 X 的子集的集合 Y ，存在一个 Y 的子集 Y*，使得 Y* 构成 X 的一种分割。

这儿有个Python写的例子。

X = {1, 2, 3, 4, 5, 6, 7}
Y = {
  'A': [1, 4, 7],
  'B': [1, 4],
  'C': [4, 5, 7],
  'D': [3, 5, 6],
  'E': [2, 3, 6, 7],
  'F': [2, 7]}

这个例子的唯一解是['B', 'D', 'F']。

精确覆盖问题是NP完备（译注：指没有任何一个够快的方法可以在合理的时间内，意即多项式时间找到答案）。X算法是由大牛高德纳发明并实现。他提出了一种高效的实现技术叫舞蹈链，使用双向链表来表示该问题的矩阵。

然而，舞蹈链实现起来可能相当繁琐，并且不易写地正确。接下来就是展示Python奇迹的时刻了！有天我决定用Python来编写X 算法，并且我想出了一个有趣的舞蹈链变种。
算法

主要的思路是使用字典来代替双向链表来表示矩阵。我们已经有了 Y。从它那我们能快速的访问每行的列元素。现在我们还需要生成行的反向表，换句话说就是能从列中快速访问行元素。为实现这个目的，我们把X转换为字典。在上述的例子中，它应该写为

X = {
  1: {'A', 'B'},
  2: {'E', 'F'},
  3: {'D', 'E'},
  4: {'A', 'B', 'C'},
  5: {'C', 'D'},
  6: {'D', 'E'},
  7: {'A', 'C', 'E', 'F'}}

眼尖的读者能注意到这跟Y的表示有轻微的不同。事实上，我们需要能快速删除和添加行到每列，这就是为什么我们使用集合。另一方面，高德纳没有提到这点，实际上整个算法中所有行是保持不变的。

以下是算法的代码。

def solve(X, Y, solution=[]):
  if not X:
    yield list(solution)
  else:
    c = min(X, key=lambda c: len(X[c]))
    for r in list(X[c]):
      solution.append(r)
      cols = select(X, Y, r)
      for s in solve(X, Y, solution):
        yield s
      deselect(X, Y, r, cols)
      solution.pop()
 
def select(X, Y, r):
  cols = []
  for j in Y[r]:
    for i in X[j]:
      for k in Y[i]:
        if k != j:
          X[k].remove(i)
    cols.append(X.pop(j))
  return cols
 
def deselect(X, Y, r, cols):
  for j in reversed(Y[r]):
    X[j] = cols.pop()
    for i in X[j]:
      for k in Y[i]:
        if k != j:
          X[k].add(i)

真的只有 30 行！
格式化输入

在解决实际问题前，我们需要将输入转换为上面描述的格式。可以这样简单处理

X = {j: set(filter(lambda i: j in Y[i], Y)) for j in X}

但这样太慢了。假如设 X 大小为 m，Y 的大小为 n，则迭代次数为 m*n。在这例子中的数独格子大小为 N，那需要 N^5 次。我们有更好的办法。

X = {j: set() for j in X}
for i in Y:
  for j in Y[i]:
    X[j].add(i)

这还是 O(m*n) 的复杂度，但是是最坏情况。平均情况下它的性能会好很多，因为它不需要遍历所有的空格位。在数独的例子中，矩阵中每行恰好有 4 个条目，无论大小，因此它有N^3的复杂度。
优点

简单: 不需要构造复杂的数据结构，所有用到的结构Python都有提供。
可读性: 上述第一个例子是直接从Wikipedia上的范例直接转录下来的！
灵活性: 可以很简单得扩展来解决数独。

求解数独

我们需要做的就是把数独描述成精确覆盖问题。这里有完整的数独解法代码，它能处理任意大小，3×3，5×5，即使是2×3，所有代码少于100行，并包含doctest！（感谢Winfried Plappert 和 David Goodger的评论和建议）

Python,X算法

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

评论“仅利用30行Python代码来展示X算法”

暂无评论...

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒经典版》的玩家都可以获得奖励。

更新日志

2024年11月24日

仅利用30行Python代码来展示X算法

详解Python中的装饰器、闭包和functools的教程

详解Python的迭代器、生成器以及相关的itertools包

评论“仅利用30行Python代码来展示X算法”

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

更新日志

友情链接