您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

穷举和推理:用C++程序求解“谁养鱼”

时间:08-28来源:作者:点击数:

这期《程序员》提到“爱因斯坦的谜题”,我才注意到“谁养鱼”这个题目。问题如下:

1、在一条街上,有5座房子,喷了5种颜色
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料,抽不同品牌的香烟,养不同的宠物
已知:
1、英国人住红色房子 
2、瑞典人****** 
3、丹麦人喝茶 
4、绿色房子在白色房子左面 
5、绿色房子主人喝咖啡 
6、抽Pall Mall 香烟的人养鸟 
7、黄色房子主人抽Dunhill 香烟 
8、住在中间房子的人喝牛奶 
9、 挪威人住第一间房 
10、抽Blends香烟的人住在养猫的人隔壁 
11、养马的人住抽Dunhill 香烟的人隔壁 
12、抽Blue Master的人喝啤酒 
13、德国人抽Prince香烟 
14、挪威人住蓝色房子隔壁 
15、抽Blends香烟的人有一个喝水的邻居
问题是:谁养鱼?

在网上找一下,看到以下资料:一个手工表格求解、一个Lisp程序求解阿牛的穷举程序,用C#实现。本文分别用穷举法和推理法解答了这个问题。我先用C++完成了推理法求解。后来看到阿牛的穷举程序后,为了比较两者的效率,又用C++实现了穷举法(参照阿牛的程序)。在我的电脑上,推理法运行时间为:

求解1000次花费3828毫秒,平均每次需要3.8毫秒

在我的T7100笔记本上平均运行时间约为1.88毫秒。穷举法的运行时间与初始数据有很大关系。对比Lisp程序需要的时间(几百到几千毫秒),C++程序确实要快一点。

本文主要介绍算法,对具体实现感兴趣的朋友可以查看源代码。可以下载推理法穷举法的完整源代码。

1 穷举

穷举法的思路很简单:遍历没有约束时所有可能的解(本文称作解空间),用所有约束条件逐一检查,直到找到符合要求的解。实现穷举法的关键是:怎样遍历解空间?换句话说,我们要按照一定顺序枚举出所有可能的解。

可以把“谁养鱼”的解看作按照房间位置排序的5组属性,例如:

1 挪威 黄色 猫 水 Dunhill
2 丹麦 蓝色 马 茶 Blends
3 英国 红色 鸟 牛奶 Pall Mall
4 德国 绿色 鱼 咖啡 Prince
5 瑞典 白色 狗 啤酒 Blue Master

每组属性是5个元素的排列(不重复),有120(5的阶乘)种可能性,如果没有约束条件,解空间的大小就是120的五次方。尽管解空间很大,由于约束条件可以一下排除很多解,所以需要检查的次数并不像“穷举法”字面上暗示的那么多。穷举法的主要逻辑如下:

  foreach (属性1的所有排列) {
    if (违反约束条件) {
      提前进入下轮循环;
    }
    foreach (属性2的所有排列) {
      if (违反约束条件) {
        提前进入下轮循环;
      }
      foreach (属性3的所有排列) {
        if (违反约束条件) {
          提前进入下轮循环;
        }
        foreach (属性4的所有排列) {
          if (违反约束条件) {
            提前进入下轮循环;
          }
          foreach (属性5的所有排列) {
            if (符合约束条件) {
              得到正确解,返回;
            }
          }
        }
      }
    }
  }

进入内层循环前的判断很重要,通过这个判断可以跳过很多次检查。如果约束条件能在外层发挥作用,就可以跳过更多的检查。在外层循环检查约束时,因为还没有填写内层属性,无法使用与内层属性相关的约束条件。所以,将属性放在循环的哪个层次对总检查次数的影响很明显。例如:

属性排列(外->内) 找到正确解的检查次数 总检查次数(找到正确解后不返回) 执行时间(1000次平均)
国家-颜色-香烟-宠物-饮料 6167 11476 14.6毫秒
国家-颜色-宠物-饮料-香烟 28896 61290 84.2毫秒
国家-香烟-饮料-颜色-宠物 47460 86756 110.3毫秒

可见,根据约束条件仔细安排属性位置可以明显降低总检查次数。“找到正确解的检查次数”(或“执行时间”)也有很大的偶然性。假设我们把正确解作为初始数据,显然一下就完成了。

穷举法类似于武功中的“一力降十会”,让我们再试试“以巧破千斤”。

2 推理

我们可以让计算机按照人类的思维模式使用约束条件逐步推导,得到答案。为了更清晰地理解问题域,我们先约定一些名词。

2.1 探索问题域

2.1.1 对象、方案和方案集

在这个问题域中,我们用对象表示一个具有全部属性的人。对象有6个属性:国家、颜色、宠物、饮料、香烟、房间号。可以将所有属性都未定的对象称为空对象。两个空对象是不可区分的。只要对象具备一个及以上已知属性,它就成为唯一的、独特的。

每个方案包含5个对象。这5个对象的所有已知属性都是不同的。方案中的对象在逻辑上是无序的。

方案集是方案的集合。

如果把推理过程看作船的航行,Wizard会这样预言这次航行:

方案集是船,方案是乘客,
所有约束条件构成问题域的环境。
航行伊始,船上只有一个乘客。
它的所有对象的
所有属性都是未定的,
代表我们对环境的一无所知。
当船经过一个个约束条件时,
船上的乘客有时增加、有时减少。
无论乘客怎么变化,船总包含着所有可能。
无论乘客怎么变化,我们的知识都在增加。
当船通过所有的约束条件,
一个乘客会到达终点,
它就是答案。

在介绍详细的推理过程前,让我们再考察一下约束条件。

2.1.2 对象内约束和对象间约束

约束条件可以分为两类:对象内约束和对象间约束。对象内约束描述一个对象内两个属性的关系,例如“英国人住红色房子”。对象间约束描述两个对象的属性间的关系,例如“抽Blends香烟的人住在养猫的人隔壁”。

在“谁养鱼”的约束条件中,对象间约束有两种关系:

  1. 邻居关系,例如前面所说的“抽Blends香烟的人住在养猫的人隔壁”;
  2. 有序邻居关系。例如“绿色房子在白色房子左面”。

2.2 推理过程

2.2.1 初始状态

“我们构建一个空方案,它的所有对象的所有属性都是未定的,它是方案集中的唯一方案。未定代表可能,这个唯一的方案也包含了所有的可能。”

这个开头虽然很有“无中生有”的哲学意味,但是不实用。我实际采用的初始状态是这样的:

方案1
英国 红色 未定 未定 未定 未定 
瑞典 未定 狗 未定 未定 未定 
丹麦 未定 未定 茶 未定 未定 
德国 未定 未定 未定 Prince 未定 
挪威 未定 未定 未定 未定 房间1 

我手工选择了5个“对象内约束”对方案作了初始化。我特意选择了不可能出现在同一个对象上的约束条件。这样,这个方案还是包含了所有的可能。初始状态的方案集中只有这么一个方案。

2.2.2 使用对象内约束

将当前方案集作为输入方案集,再准备一个空的输出方案集。将对象内约束应用到输入方案集的所有方案上。例如将“绿色房子主人喝咖啡”应用到方案1上,这时可能出现两种情况:

  1. 约束条件可以放到方案的多个对象上。例如“绿色房子主人喝咖啡”可以放到颜色和饮料属性未定的对象上。每次将约束条件放到一个不矛盾的位置,就会产生一个新的方案。将新方案放到输出方案集中。
  2. 约束条件可能与方案冲突。这时简单地忽略这个方案。

范例程序可以打印出推导过程,“使用对象内约束”的推导过程如下:

初始状态
-------------------- 一共有 1 个解 --------------------

解1
英国 红色 未定 未定 未定 未定 
瑞典 未定 狗 未定 未定 未定 
丹麦 未定 未定 茶 未定 未定 
德国 未定 未定 未定 Prince 未定 
挪威 未定 未定 未定 未定 房间1 



增加约束: 5、绿色房子主人喝咖啡
-------------------- 一共有 3 个解 --------------------

解1
英国 红色 未定 未定 未定 未定 
瑞典 绿色 狗 咖啡 未定 未定 
丹麦 未定 未定 茶 未定 未定 
德国 未定 未定 未定 Prince 未定 
挪威 未定 未定 未定 未定 房间1 

解2
英国 红色 未定 未定 未定 未定 
瑞典 未定 狗 未定 未定 未定 
丹麦 未定 未定 茶 未定 未定 
德国 绿色 未定 咖啡 Prince 未定 
挪威 未定 未定 未定 未定 房间1 

解3
英国 红色 未定 未定 未定 未定 
瑞典 未定 狗 未定 未定 未定 
丹麦 未定 未定 茶 未定 未定 
德国 未定 未定 未定 Prince 未定 
挪威 绿色 未定 咖啡 未定 房间1 



增加约束: 12、抽Blue Master的人喝啤酒
-------------------- 一共有 7 个解 --------------------
...


增加约束: 6、抽Pall Mall香烟的人养鸟
-------------------- 一共有 16 个解 --------------------
...


增加约束: 7、黄色房子主人抽Dunhill香烟
-------------------- 一共有 19 个解 --------------------
...


增加约束: 9+14、 挪威人住第一间房+挪威人住蓝色房子隔壁=第二间房是蓝色的
-------------------- 一共有 28 个解 --------------------
...


增加约束: 8、住在中间房子的人喝牛奶
-------------------- 一共有 30 个解 --------------------
...

对象内约束的指定属性被应用到方案的未定属性上,使方案的眉目逐渐清晰。每个输出方案集总是包含着在增加了当前所有约束后的所有可能。

2.2.3 使用对象间约束

对象间约束必须被应用到方案的已知属性上,然后判断两个方案的房间号属性是否符合指定关系。为此,我们在对方案使用对象间约束前,必须保证:

  1. 假设约束条件使用了某个属性值(例如颜色为绿色),方案中必须有对象具备这个属性值;
  2. 方案所有对象的房间号属性已知。

如果方案不满足上述条件,我们在应用约束条件前就必须先“扩展”方案,让其满足上述条件。“扩展”的过程还是读入一个方案集,输出一个方案集。读入方案如果已经具备指定属性值,就直接将其放入输出方案集。读入方案如果已经不具备指定属性值,就将增加该属性值后的所有可能方案放入输出方案集。

对房间号属性的扩展只需要在应用第一个“对象间约束”前做一次就可以了。

使用对象间约束对扩展过的方案集进行过滤,去掉不满足约束条件的方案,就得到了最后的答案。这部分的推导过程如下:

增加约束: 4、绿色房子在白色房子左面 
-------------------- 一共有 4 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3 
瑞典 蓝色 狗 啤酒 Blue Master 房间2 
丹麦 白色 未定 茶 Blends 房间5 
德国 绿色 未定 咖啡 Prince 房间4 
挪威 黄色 未定 水 Dunhill 房间1 

解2
英国 红色 鸟 牛奶 Pall Mall 房间3 
瑞典 白色 狗 啤酒 Blue Master 房间5 
丹麦 蓝色 未定 茶 Blends 房间2 
德国 绿色 未定 咖啡 Prince 房间4 
挪威 黄色 未定 水 Dunhill 房间1 

解3
英国 红色 未定 牛奶 Blends 房间3 
瑞典 蓝色 狗 啤酒 Blue Master 房间2 
丹麦 白色 鸟 茶 Pall Mall 房间5 
德国 绿色 未定 咖啡 Prince 房间4 
挪威 黄色 未定 水 Dunhill 房间1 

解4
英国 红色 未定 牛奶 Blends 房间3 
瑞典 白色 狗 啤酒 Blue Master 房间5 
丹麦 蓝色 鸟 茶 Pall Mall 房间2 
德国 绿色 未定 咖啡 Prince 房间4 
挪威 黄色 未定 水 Dunhill 房间1 



增加约束: 10、抽Blends香烟的人住在养猫的人隔壁
-------------------- 一共有 4 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3 
瑞典 蓝色 狗 啤酒 Blue Master 房间2 
丹麦 白色 未定 茶 Blends 房间5 
德国 绿色 猫 咖啡 Prince 房间4 
挪威 黄色 未定 水 Dunhill 房间1 

解2
英国 红色 鸟 牛奶 Pall Mall 房间3 
瑞典 白色 狗 啤酒 Blue Master 房间5 
丹麦 蓝色 未定 茶 Blends 房间2 
德国 绿色 未定 咖啡 Prince 房间4 
挪威 黄色 猫 水 Dunhill 房间1 

解3
英国 红色 未定 牛奶 Blends 房间3 
瑞典 蓝色 狗 啤酒 Blue Master 房间2 
丹麦 白色 鸟 茶 Pall Mall 房间5 
德国 绿色 猫 咖啡 Prince 房间4 
挪威 黄色 未定 水 Dunhill 房间1 

解4
英国 红色 未定 牛奶 Blends 房间3 
瑞典 白色 狗 啤酒 Blue Master 房间5 
丹麦 蓝色 鸟 茶 Pall Mall 房间2 
德国 绿色 猫 咖啡 Prince 房间4 
挪威 黄色 未定 水 Dunhill 房间1 



增加约束: 15、抽Blends香烟的人有一个喝水的邻居
-------------------- 一共有 1 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3 
瑞典 白色 狗 啤酒 Blue Master 房间5 
丹麦 蓝色 未定 茶 Blends 房间2 
德国 绿色 未定 咖啡 Prince 房间4 
挪威 黄色 猫 水 Dunhill 房间1 



增加约束: 11、养马的人住抽Dunhill香烟的人隔壁
-------------------- 一共有 1 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3 
瑞典 白色 狗 啤酒 Blue Master 房间5 
丹麦 蓝色 马 茶 Blends 房间2 
德国 绿色 鱼 咖啡 Prince 房间4 
挪威 黄色 猫 水 Dunhill 房间1 

推理结束。

2.3 不足

目前的推理法程序还有一个地方可以改进:就是在扩展房间号时,其实没有必要先扩展方案集。因为,扩展房间号其实就是几个房间号在几个未定位置的排列。可以对每个方案,枚举所有房间号的排列后,直接用约束条件过滤。这样可以减少需要放入方案集中的方案。

这个推理法已经比较接近人类的思维模式了。但有一点不像:人在推理时喜欢假设和尝试,如果走不通就退回去再尝试其它可能。人类一般不会一板一眼地在每一步上列出所有可能。我的算法没有设计“尝试-回溯”机制。增加这个机制会使逻辑更复杂,严重违反KISS(Keep It Simple, Stupid)理念。其实对于“谁养鱼”这种规模的问题,穷举法是最合适的。

我本来想把“谁养鱼”的问题从5阶扩展到12阶,以测试穷举法和推理法的性能,还选择了一个武林大会的题材。但在准备了12组属性后,发现至少要写70多个hint才能玩起来,就不想玩了。有兴趣的朋友可以用推理法的程序出题。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门