首頁 後端開發 Python教學 仅利用30行Python代码来展示X算法

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

Jun 06, 2016 am 11:23 AM
python

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

这儿有个Python写的例子。
 

1

2

3

4

5

6

7

8

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转换为字典。在上述的例子中,它应该写为

1

2

3

4

5

6

7

8

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的表示有轻微的不同。事实上,我们需要能快速删除和添加行到每列,这就是为什么我们使用集合。另一方面,高德纳没有提到这点,实际上整个算法中所有行是保持不变的。

以下是算法的代码。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

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 行!
格式化输入

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

1

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

登入後複製

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

1

2

3

4

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的评论和建议)

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前 By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

模板化的優點和缺點有哪些? 模板化的優點和缺點有哪些? May 08, 2024 pm 03:51 PM

模板化的優點和缺點有哪些?

Google AI 為開發者發佈 Gemini 1.5 Pro 和 Gemma 2 Google AI 為開發者發佈 Gemini 1.5 Pro 和 Gemma 2 Jul 01, 2024 am 07:22 AM

Google AI 為開發者發佈 Gemini 1.5 Pro 和 Gemma 2

怎麼下載deepseek 小米 怎麼下載deepseek 小米 Feb 19, 2025 pm 05:27 PM

怎麼下載deepseek 小米

deepseek怎麼問他 deepseek怎麼問他 Feb 19, 2025 pm 04:42 PM

deepseek怎麼問他

evaluate函數怎麼保存 evaluate函數怎麼保存 May 07, 2024 am 01:09 AM

evaluate函數怎麼保存

NET40是什麼軟體 NET40是什麼軟體 May 10, 2024 am 01:12 AM

NET40是什麼軟體

deepseek該怎麼搜索 deepseek該怎麼搜索 Feb 19, 2025 pm 05:18 PM

deepseek該怎麼搜索

瀏覽器插件是什麼語言寫的 瀏覽器插件是什麼語言寫的 May 08, 2024 pm 09:36 PM

瀏覽器插件是什麼語言寫的

See all articles