Scheme来实现八皇后问题(2)

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/9790466.html 

  作者:窗户

  QQ/微信:6679072

  E-mail:6679072@qq.com 

  上一章讲了用1~n的排序来表示n皇后的解,然后通过枚举1~n所有的排列、判定谓词过滤所有排列得到最终的所有解。

  在此基础上,这一章我们思考是否存在更好的解法,从而深化这个问题。

效率问题

  为了测试效率,在代码末尾加上

(queen (read))

  表示解决的皇后个数由输入的结果决定。

  还是先把Scheme代码编译、链接为普通可执行文件,这样运行就不是在解释的条件下了,速度可以提升数倍。

  八皇后使用这个程序出来结果还算可以接受,但是当我想解决10皇后问题的时候,却花了半分钟,而如果是解决11皇后问题,我等待了好几分钟,系统把进程杀了。

  我们可以意识到,程序的效率似乎并不是那么高。那么有没有提升的办法呢?

  想要找到提升的办法,我们先要分析之前的算法慢的原因。

  这个算法中,内存使用姑且就不说了(其实存储所有的排列需要很大的内存),我们要产生所有的排列,然后每一个排列都要单独判定是否符合条件。

  然而,我们想一想,我们真的需要每个排列都独立检查一遍吗?

  实际上,我们可能真的不需要如此。我们其实只需要检测到一个片段上存在皇后互吃,那么包含这个片段的所有排列自然都不可能是解,可以直接被排除。

  比如我们检测到如果一个排列以1、2开头的话,那么这两个点距离为1,值也相差1,两个皇后互吃,从而就可以知道,所有以1、2开头的排列都不需要检测了。

  也就是所有的(1 2 ...)排列直接因为我检测到(1 2)不能作为解而直接排除。

  这样从片段来对所有排列剪枝,当然比挨个检测效率高。

字典顺序

  我们要考虑一个字典顺序的检测。

  字典顺序就是按照英文字典那样,单词出现的顺序是按字符串的大小顺序。

  字符串的大小比较,大家应该都很熟。

  两个字符串从头逐位比较,过程中,对应位的字符相等则继续比较,直到过程中一个字符串先到尾部或者字符上分出大小,先到尾部或者对应位上的字符小的一方的字符串较小,另一个字符串则较大。如果两个字符串同时都检测到了尾部,那么两个字符串当然一模一样,则为相等。

  C语言中字符串比较可以用strcmp函数,而Scheme里字符串比较可以用 string=?  string>? 等函数。

  但是,我们这里是要对于所有排列按照字典顺序检测,可是这里每个排列是一个数字组成的list,那么我们可以按照数字的大小来替代之前字符串比较时的字符大小,就可以做到字典序列了。

  比如1~3的全排列一共有6个排列,按照字典顺序从小到大本应该如下:

  (1 2 3)

  (1 3 2)

  (2 1 3)

  (2 3 1)

  (3 1 2)

  (3 2 1)

  但考虑到列表的特殊结构,我们判断两个排列的大小从最后一位开始看的话(也就是列表反过来看),在这里因为一路可以使用cons/car/cdr而不是append/take/drop之类相对复杂的递归,从而要方便很多,效率也要高,于是上述1~3的全排列按照字典顺序会如下:

  (3 2 1)

  (2 3 1)

  (3 1 2)

  (1 3 2)

  (2 1 3)

  (1 2 3)

实际的例子

  我们需要实际来看看按照字典序列并加上之前的剪枝思路如何完成完整的解答。

  在这里,我们可以用4皇后来作为i例子。

  我们试图要用迭代完成我们的检测,用当前检测的列表和已有的解合成迭代的状态

  最开始的时候,我们要检测的list是空列,而解初始也为一个空列

目前                    解 说明

  ()                         ()                 初始

(1)       ()                 检测合法 

(2 1)                    ()     不合法,所以以(2 1)结尾的排列都不合法

(1)                       ()                因为上面不合法,所以2被退掉

(3 1)                    ()                填入比刚才退掉的2大的数中最小的

      ...

  这里产生了一个问题,上面红字标注的两行,除了说明之外,其他一模一样,无法区分。而一个转化成(2 1)()状态,另外一个转化为(3 1)()状态,相同的状态转换成了不同的状态,对于迭代,

这个完全没道理!

  说明状态还不完善,我们刚才两次从(1)()状态出发,之所以第一次转化到了(2 1)()状态,而第二次转化到了(3 1)()状态,原因就在于其实都是在(1)的基础上,找了原则上最小的值。从而,我们可以在状态中再加一个限值,标志着列表下一个添加的元素的选取必须高于这个值。

  这样状态才是完备的。

  于是上面4皇后问题状态的转换可以如下:

目前        限值 说明

  ()                  0                     ()                 初始

  (1)      0                  ()                 (1)合法,升位   

  (1)                2                     ()      (2 1)非法 (满足的最小的数是2)

  (3 1)             0                     ()                (3 1)合法,升位

  (3 1)             2                     ()                (2 3 1)非法

  (3 1)             4                     ()                (4 3 1)非法

  (1)                3                     ()                不存在值,降位

  (4 1)             0                     ()                (4 1)合法,升位

  (2 4 1)          0                     ()                (2 4 1)合法,升位

  (2 4 1)          3                     ()                (3 2 4 1)非法

  (4 1)             2                     ()                不存在值,降位

  (4 1)             3                     ()                 (3 4 1)非法

  (1)                4                     ()                 不存在值,降位

  ()                  1                     ()                 不存在值,降位

  (2)                0                     ()                  (2)合法,升位

  ...

  (3 1 4 2)       0                     ()                  (3 1 4 2)合法,升位

  (1 4 2)          3                     ((3 1 4 2))     加入解,降位

  ...

  (4)                3        ((2 4 1 3) (3 1 4 2))    不存在值,降位

  ()                  4        ((2 4 1 3) (3 1 4 2))    不存在值且无法降位,结束

状态转移

  现在,我们定下状态为 目前,限值,解

  我们来分析关于状态的一切:

  初始时,状态为 ()0()。

  结束时,一定是因为目前的是空列,而且限值已经达到了n皇后的n。

  当目前的列表包含了1~n的数时(其实就是长度为n),那么找到了一个解,把这个列表加入到解,然后降位,也就是目前的列表把最前面的一位去掉,然后限值设为最前面的这一位。

  其他情况下,找剩余的数中大于限制的最小数:

  (1)如果不存在,则降位

  (2)如果存在,假如这个值加到目前的列表前得到的新表是合法的,那么升位,新列表作为目前列表,限值设为0即可。

  (3)如果存在,假如这个值加到目前的列表前得到的新表是非法的,那么限制调整为刚才找到的最小数。

迭代和封装

  按上述规则,迭代代码如下:

 (define (_queen n current gt result)
  (cond
   ((and (null? current) (>= gt n)) result);终止条件
   ((= n (length current)) (_queen n (cdr current) (car current) (cons current result)));记下解
   (else
    (let (
      (remained (filter (lambda (x) (> x gt )) (remove* current (range 1 (+ n 1)))) );剩下的数中哪些是大于下限的
     )
     (if (null? remained)
      (_queen n (cdr current) (car current) result)
      (let ((next (car remained)))
       (if (valid? current next)
        (_queen n current next result)
        (_queen n (cons next current) 0 result))))))))

  其中,remove*是racket里的函数,用于集合相减,并且不改顺序,但它并不属于Scheme标准。此处略去实现。

  比如(remove* '(2 3 4) '(1 2 4 5 6))返回'(1 5 6)。

  当然,不忘封装一下:

(define (queen n) (_queen n '() 0 '()))

合法性检测

  检测所用的valid?函数并未实现。

  在这个算法中,如果一个序列是非法的,也就是存在皇后互吃的,一定是最新的元带来的。因为如果判断到这一步,那么之前的子序列一定是合法的。

  这是一个递归的思路,也是比上一章使用迭代来检测一个排列所有的可能更加快速的地方之一。

  比如要检测'(2 5 3 1)是不是合法,在检测前,我们无条件知道(cdr '(2 5 3 1))也就是'(5 3 1)是合法的。

  那么合法性判断就成了看最左边的2和后面的3个元素是否有差值的绝对值等于距离,一种比较好的做法是:

  先将'(5 3 1)的每个元素减去新加的2,得到'(3 1 -1),再取绝对值得到'(3 1 1),再和'(1 2 3)比较,看看是否在相同位置有相同元素。

  判断两个列表存在不存在相同位置有相同元素,用个递归很容易写:

(define (same_ele_pos? x y)
 (cond
  ((null? x) #f)
  ((= (car x) (car y)) #t)
  (else (same_ele_pos? (cdr x) (cdr y)))
 )
)

  于是合法性检测就可以写成如下:

(define (valid? lst new)
 (same_ele_pos?
  (range 1 (+ 1 (length lst)))
  (map (lambda (x) (abs (- x new))) lst)
 )
)

  上面检查'(2 5 4 1)是否合法,就可以通过(valid? '(5 4 1) 2)来检测。

测试

  把上述代码后面加(queen 10)解决10皇后问题,编译之后,我们发现运行时间连1秒都不需要。

  而如果要求12皇后问题需要20秒。实际上,我们还可以在状态中引入一些别的东西以提高速度,从而使得运行时间变成现在的几分之一,但这已经不是我想在这里讲的了。

  算法这东西,很多时候很难做到极致,所以工程中有一个方向就是随着时间推移,软件版本在提升算法运行速度,比如PCB/FPGA的布线。工程师们依然为之不断努力。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Crossin的编程教室

【编程课堂】震惊!小 bug 引发大灾难,0.1 + 0.2 的结果竟然是……

各位观众点进标题看文章的时候,我已经准备打包行李去UC报道啦~ 冷笑话结束,嗯,说正事。 请大家思考一下在 python 控制台输入 0.1 + 0.2 ==...

2859
来自专栏西枫里博客

Python学习笔记三(常用运算符)

2017年年终确定的从2018年开始学习一门新的语言。随着机器学习人工智能的日渐深入,是时候有必要掌握以下Python了。博客今天更新第三篇学习记录,关于Pyt...

922
来自专栏Java3y

HashMap就是这么简单【源码剖析】

2053
来自专栏飞雪无情的博客

Go语言性能优化-两数之和算法性能研究

好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,...

1903
来自专栏高爽的专栏

HashMap深度解析(二)

上一篇比较深入的分析了HashMap在put元素时的整体过程,Java Collections Framework中实际操作的都是数组或者链表,而我们通常...

2290
来自专栏美团技术团队

Java8系列之重新认识HashMap

摘要 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8...

4315
来自专栏小樱的经验随笔

HUST 1541 Student’s question

1541 - Student’s question 时间限制:1秒 内存限制:128兆 696 次提交 134 次通过 题目描述 YYis a stude...

3488
来自专栏阿凯的Excel

八种方式实现多条件匹配

之前在Excel内部的分享交流群和别的讲师探讨了多条件匹配有哪些实现方式。 围观的市民刘先生表示:我活了二十多年,看见斗图的比较多,这么无聊斗Excel使用技巧...

3424
来自专栏程序员的SOD蜜

Why to do,What to do,Where to do 与 Lambda表达式!

最近我做一个“四象限”图表控件,其中有一个比较复杂的“坐标变换”问题,即是如何让一组数据放到有限的一个区间内,例如有一组数据 List[4,5,6,7,8],要...

2259
来自专栏QQ音乐技术团队的专栏

Android Native 开发之 NewString 与 NewStringUtf 解析

本文将从一个 Native Crash 分析入手,带大家了解我们平时开发中,那些容易忽略但又很值得学习的底层源码知识。

1.4K9

扫码关注云+社区

领取腾讯云代金券