2.1 搜索树
2.1.1 树的构造和图形表达
思考一下下面的问题。
问题1 15谜题（见图2.1）
在一个4×4的格子里配置1到15的滑块，通过把滑块移动到空白位置从而达到最终目标的游戏称为15谜题。这个游戏也称为“滑块谜题”。关于15谜题有一个好玩的轶事。1887年，Sam Loyd[1]开始贩卖这种谜题，当年的初始状态如下。
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 X
最终需要变成如下所示的状态。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X
图2.1 15谜题
当时Loyd宣称能够解开这个谜题者将获得赏金1000美元（这里X表示空白位置）。于是人们开始对这个谜题变得狂热，这种狂热的情绪不仅在美国发酵，还传染到了欧洲，据说15谜题在当时大卖[33]。虽然很多人宣称解开了这个谜题，但并没有什么人的解法和领奖的信息被记录下来。实际上这个问题理论上是无法解开的。终点状态的滑块放置方式超过20兆种，其中只有一半的方式可以从初始状态滑到终点状态。剩下的一半状态（包含上述终点状态）无法从初始状态到达终点状态，因此无法解开上述谜题。
两种状态A和B是否能够彼此到达其实可以用置换的奇偶性进行判断。我们首先考虑一下从A状态转换到B状态需要的滑块交换次数[2]。如果这个交换次数是偶数，则A和B的奇偶性是相同的，可以通过空白位置的移动到达[20]。这个谜题的原型利用了4×4格子的“幻方”，且在19世纪80年代就已经开发出售了。也就是说，真正的创作灵感可能并非来自Sam Loyd[33]。
问题2 传教士与野人（Missionaries and Cannibals）[3]
有两个传教士和两个野人正打算集体渡河（见图2.2）。渡河的小舟只有一艘，最多只能同时载两个人。让人感到为难的是，一旦野人的数量超过传教士，野人就会发动叛乱。也就是说，不管是此岸还是彼岸，野人的人数是不可以超过传教士的。但是出于对干粮消耗的节制，一边的河岸上只剩下野人这种情况是允许的。在这种情况下，全员能平安无事地渡河吗？
我们试着用火柴棒解决传教士与野人问题。在这里我们要准备四根火柴，去掉两根火柴的头部，用没有头的火柴作为传教士，有头的火柴作为野人。我们能解决这个问题吗？需要注意的是，如果过于随便地进行搜索，会导致反复回到相同的状态，最后无法解开这个问题。
那么我们要想出一个可以系统性地进行搜索的方法。经常使用的一个方法就是利用状态空间进行搜索。使用如下形式表示状态。
（LM,LC,RM,RC,PB） （2.1）
图2.2 传教士与野人的问题
在这里，LM、LC分别代表在左岸的传教士和野人的人数，RM、RC分别代表在右岸的传教士和野人的人数。PB表示小舟所处的位置（L和R分别表示左岸和右岸）。
初始状态为：
（2,2,0,0,L） （2.2）
目标状态为：
（0,0,2,2,R） （2.3）
在这里条件必须被设置为：
LM≥LC或者LM=0 （2.4）
RM≥RC或者RM=0 （2.5）
当然以下条件必然成立。
LM+RM=2 （2.6）
LC+RC=2 （2.7）
小舟每移动一次，状态就会发生变化。但需要注意的是小舟每次只能载两个人。比如说，小舟移动一次以后会从初始状态移动到以下几种状态。
（0,2,2,0,R）,（1,1,1,1,R）,（2,0,0,2,R）,（2,1,0,1,R） （2.8）
这些状态分别表示传教士两人、传教士和野人各一个人、野人两人、野人一个人坐小舟移动。如果只有一个传教士乘舟，就会导致L侧岸边上的传教士人数少于野人人数，从而进入违反条件的状态。
接下来，我们调查一下按式（2.8）所示状态移动小舟时可能会导致的状态。通过不断地搜索，返回值如图2.3所示。
图2.3 系统性的搜索方法
从图2.3中可以看出，从以下状态
（2,2,0,0,L） （2.9）
到目标状态
（0,0,2,2,R） （2.10）
有多种选择，我们可以从中找到解决方案。比如说经过以下状态可以到达目标状态。
（2,2,0,0,L）→（1,1,1,1,R）→（2,1,0,1,L）→（0,1,2,1,R）→（0,2,2,0,L）→（0,0,2,2,R） （2.11）
当然同时也知道除此之外还有其他的解决方案。
应当需要注意的是，从状态
（0,2,2,0,R） （2.12）
之后没有其他选择，所以只有一种方法，即从这个状态返回以下状态。
（2,2,0,0,L） （2.13）
从以上的例子可以知道，图结构经常被用于搜索活动。这样状态空间就能够全面地得到可视化的效果。图结构中经常用到的是树结构。树结构被认为是家族图谱，也有“不存在闭环的连接图”这样的严格定义。此外，它还有任意两个节点之间只存在唯一一个连接通道的性质。通过直观的表达形式（见图2.4），把初始状态放在最上面，然后把可能到达的状态放置在下方并连接。图2.3由于存在闭环，因此并不是树结构。
图2.4 树结构
在这里我们整理一下关于图结构的专门用语。图是由被称为“节点”的点，以及连接节点和节点之间的弧（arch或者edge）组成的。弧往往是单方向的，也就是说它是有向（directed）的。弧尾节点是弧头节点的“前驱（predecessor）节点”或者“父节点”。反过来说，弧头节点被称为“子节点”。如果两个节点之间可以相互作为对方的后连接节点，则这个弧具有双向性（bidirectional）。树是图的一种特殊形式，它具有以下两个性质。
1）树具有唯一根节点（root），也就是说具有顶点（top node），根节点以上不存在节点。
2）根节点以外的节点都有自己的唯一父节点。
树具有比图构造更加简洁、更方便使用的优点。特别值得一提的是，从树上的一个节点到达其他任何节点都只有唯一一条路径（path），或者可以说它的特征就是不存在循环结构。接下来的章节会介绍针对图以及树结构的搜索方法。
[1] Sam Loyd（1841-1911）：美国谜题作者，娱乐数学学者。
[2] 把两个不同的滑块取出进行位置交换计为1次。
[3] 在我还是学生时，“传教士与野人”问题就已经很有名了。就如结构主义人类学家Claude Levi-Strauss所解析的那样，非洲和美洲大陆的原住民具有有别于西欧的独特而又优秀的文化。这个问题使用这样的称呼，强烈反映了西欧中心的优越感思想，遭受了很多批判。让人遗憾的是，这个问题的名称基于历史原因已经十分固定，难以改变。虽然这几年还有“猫和老鼠问题”［27］这样的称呼，但这种称呼又会导致对问题题意的理解偏颇。虽然我不认可西欧中心主义思想，但如上面描述的原因，为了方便，依然采用“传教士与野人”这个名称。