时间:2021-05-22
假如你对数独解法感兴趣,你可能听说过精确覆盖问题。给定全集 X 和 X 的子集的集合 Y ,存在一个 Y 的子集 Y*,使得 Y* 构成 X 的一种分割。
这儿有个Python写的例子。
这个例子的唯一解是['B', 'D', 'F']。
精确覆盖问题是NP完备(译注:指没有任何一个够快的方法可以在合理的时间内,意即多项式时间 找到答案)。X算法是由大牛高德纳发明并实现。他提出了一种高效的实现技术叫舞蹈链,使用双向链表来表示该问题的矩阵。
然而,舞蹈链实现起来可能相当繁琐,并且不易写地正确。接下来就是展示Python奇迹的时刻了!有天我决定用Python来编写X 算法,并且我想出了一个有趣的舞蹈链变种。
算法
主要的思路是使用字典来代替双向链表来表示矩阵。我们已经有了 Y。从它那我们能快速的访问每行的列元素。现在我们还需要生成行的反向表,换句话说就是能从列中快速访问行元素。为实现这个目的,我们把X转换为字典。在上述的例子中,它应该写为
眼尖的读者能注意到这跟Y的表示有轻微的不同。事实上,我们需要能快速删除和添加行到每列,这就是为什么我们使用集合。另一方面,高德纳没有提到这点,实际上整个算法中所有行是保持不变的。
以下是算法的代码。
真的只有 30 行!
格式化输入
在解决实际问题前,我们需要将输入转换为上面描述的格式。可以这样简单处理
但这样太慢了。假如设 X 大小为 m,Y 的大小为 n,则迭代次数为 m*n。在这例子中的数独格子大小为 N,那需要 N^5 次。我们有更好的办法。
这还是 O(m*n) 的复杂度,但是是最坏情况。平均情况下它的性能会好很多,因为它不需要遍历所有的空格位。在数独的例子中,矩阵中每行恰好有 4 个条目,无论大小,因此它有N^3的复杂度。
优点
求解数独
我们需要做的就是把数独描述成精确覆盖问题。这里有完整的数独解法代码,它能处理任意大小,3×3,5×5,即使是2×3,所有代码少于100行,并包含doctest!(感谢Winfried Plappert 和 David Goodger的评论和建议)
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
线性逻辑回归本文用代码实现怎么利用sklearn来进行线性逻辑回归的计算,下面先来看看用到的数据。这是有两行特征的数据,然后第三行是数据的标签。python代码
一,python输出*组成的菱形(实心):python代码:x=int(input('请输入最长行的*的个数:'))y=int(input('请输入每个*之间的
本文所述实例为Python用3行代码实现解一元一次方程,代码简洁高效,具体用法如下:>>>solve("x-2*x+5*x-46*(235-24)=x+2")3
Notepad++是一款强大的编程工具,可是很多小伙伴表示只会用它来写代码,却不会用它来运行代码,下面我就以python为例,展示一下如何利用Notepad++
我们知道Python3.x引入了新的字符串格式化语法。不同于Python2.x的复制代码代码如下:"%s%s"%(a,b)Python3.x是复制代码代码如下: