字母跑马灯

陈凯

在人工智能的学习过程中，有不少经典的算法需要掌握，如一般要掌握树结构或图结构中数据的搜索方法，其中比较基础的内容，是对树结构做广度优先搜索和深度优先搜索。但在实际教学中，却可能会遇见一个矛盾，若是学校并没有将“数据结构”模块与“人工智能初步”模块一起列入选择性必修的内容，那么在讲解树结构的搜索问题时，面对学生从未接触过的“树”这种数据结构，教师该如何平衡好教学内容的安排呢？

一个办法是干脆绕过对“树”这种数据结构实现过程的讲解，直接使用现成封装好的对象，对树结构进行操作。这样虽然可以降低教学上的难度，却难免会有些空中造屋或隔靴搔痒的感觉，并且，由于使用了现成的对象，即便完成了树结构的遍历和搜索任务，学生的成就感也不会很充足。所以这里就有了一个值得思考的问题：怎样寻找替代方案，简化数据结构和程序代码，减少教学的容量，与此同时，还要将实现树结构中的搜索的关键思想表现出来，为计算思维的培养提供落实点。本文给出的“字母跑马灯”教学活动，就是为解决上述问题而做的一个尝试。

● 树和字母跑马灯

先来画一棵树，为了清晰简单，此处的树的分叉最多为2，并且，树的节点信息，就是它的名字本身。如图1所示，若从根节点开始，对这棵树进行广度上的遍历，那么依次访问的节点应该是：A—B—C—D—E—F—G—H—I—J。访问节点的名字“恰好”按字母顺序排列，这当然是笔者有意安排所致。

可以根据每个节点和它分叉通向的节点建立一张规则表，这样，即便没有直观看到树结构的展示图，也可以在拓扑学的意义上，将树的结构重新还原出来，规则表中，不再继续分叉的节点，后续的字符串为空（如图2）。

接下来，就可以玩名叫《字母跑马灯》的游戏了，首先设初始值，就是先放置树的根节点，所以可以在纸上写下只包含一个字母“A”的字符串。然后：第一步，将字符串中的首字母搬运到字符串的末尾;第二步，将字符串末尾的字母，按规则表进行替换;第三步，从第一步开始重复动作。

可以跟踪观察一下效果如何，初始时字符串是“A”，第一步是将首字母（就是“A”）搬运到字符串最后，当然，因为字符串中只有一个字母，结果还是“A”，接下来第二步，根据规则表，字符串变化成了“BC”，然后第三步，回到第一步接着进入第二轮变化，第一步进行搬运，字符串变成“CB”，然后第二步，字符串变成“CDE”……每一轮的操作产生的字符串变化过程如下：

A—BC—CDE—DEFG—EFG—FGHI—GHI—HIJ—IJ—J—

可以看出，字符串的首字母就是广度遍历时依次访问的节点名字。实际上，这种运用了“搬运—替换”规则的字符串的迭代过程，是一种被称为标签系统（Tag-System）的计算模型。这种计算模型当然不是只能用来模拟树结构的遍历，它还能用来实现什么功能，这个问题留给读者们去思考。

● 将变化过程自动化

可以利用工具，将以上的搬运和迭代过程变成自动化的动作。只要利用文字编辑工具的宏的功能，就可以实现自动化，整个过程中，并不需要输入任何的程序代码。

下面，以NotePad++软件为例来说明宏的制作，此软件可从网络上免费下载，也可以使用Microsoft Word、Open Office等办公软件来完成类似操作。初始时，在NotePad++的文字编辑区中，写入“*A”，这里的星号起到替换操作标识的作用。星号后的字母，就是将要执行替换操作的对象。

第一步，创建一个名为“Move”的宏，这个宏的作用是将首字母搬运到字符串末尾。这个宏中包含的操作步骤是：按“Home”键将光标移到行首，按“Shift”键和右箭头选中星号和字符串首字母，执行剪切操作，按“End”键将光标移到行尾，执行粘贴操作。

第二步，创建一个名为“Replace”的宏，这个宏的作用是按规则表进行替换。这个宏中包含的操作步骤是：依次将“*A”替换成“BC”，将“*B”替换成“DE”，将“*C”替换成“FG”，以此类推。当规则表全部应用完毕后，还要按“Home”键，将光标移到行首，并补充一个星号，重新设置好替换标识。

这样一来，只要反复执行“Move”和“Replace”这两个宏，就可以实现树结构的广度优先遍历了。下面回顾一下解决遍历问题的思路：先是将形象的树的结构抽象成替换规则的编码，然后用标签系统这种计算模型来实施符号的搬运和替换，最后再利用文字编辑软件的宏，来实现符号的搬运和替换的自动化。这些都与计算思维的培养目标相契合。

● 极其简单的广度优先搜索代码

在熟练掌握符号替换的宏的制作后，将广度优先遍历的过程转而用程序代码实现，就非常容易了。在实际的人工智能教学安排中，对于低年级的学生，可以考虑仅利用宏来进行操作实验，而高年级的学生，或有算法和程序设计基础的学生，就可以更上一層楼，借鉴用标签系统这种计算模型实现树结构遍历的方法，编写出广度优先搜索的代码。

这里提供了用Python代码实现的例子，代码中，node列表存储的是树的节点的名称，link列表存储的是树的每一个节点分叉的后续节点的名称，data是一个字典，其中存储的是树中每一个节点中存储的数据信息。search=search[1：]和search=search+link[myindex]两句语句实现了符号的搬运和替换。代码可以说是极其简单了，如下页图3所示。

● 相当简单的深度优先搜索代码

将上面的方法稍微改一下，就可以实现深度优先搜索了，还是可以试着在Notepad++里玩符号替换的游戏，假设初始的字符串还是“*A”，这一次不需要搬运了，只要对字符串最前面的字母进行替换即可，步骤如下：

第一步，根据树结构连接的规律，将“*A”替换成“BCA”（其实是将“*A”替换成“BC”后再加上“A”自己），将“*B”替换成“DEB”，将“*C”替换成“FGC”，将“*D”替换成“D”（其实是将“*D”替换成空字符串再加上“D”自己），以此类推。将以上步骤包装成宏。这种替换字符串的方法称为马尔科夫重写系统，是另一种十分有用的计算模型。

第二步，按“Home”键回到行首，补充一个星号。因为只有简单的一个动作，即便不包装成宏也是可以的。

然后只要反复执行以上两步，大致就可以实现深度优先的遍历了，但在实际操作中，会遇见字符串变化陷入停滞或重复模式的问题。比如，“*A”变成“*BCA”，再变成“*DEBCA”，由于字符“D”对应的是空字符串，于是经过一轮变化后，字符串还是“*DEBCA”。

解决的方法是要加入一点人工干预，当发现字符串的变化陷入停滞或重复的模式中时，就手动删除行首的字母，若删除行首字母后仍然陷入停滞或重复的模式，则继续删除行首字母。虽然这样做会显得整个过程不特别自动化，但也意外地带来了思考的乐趣：若将要探索的树比较庞大，那么，是不是应该删除行首字母？应该什么时候删除行首字母？这就需要考验记忆和判断能力了。若稍微改一下游戏规则，如在规则表中特意放置一个小写字母，那就可以在Notepad++中玩迷宫寻宝（寻找小写字母）的游戏了。

如果是借助程序代码，判定字符串变化是否陷入停滞或重复的模式就十分简单了，只要将每次字符串的变化情况存入列表，然后在新的一轮字符串变化后，检查其是否与列表中已有的字符串重复，就可以达到目的了。按这样的思路，可以将半自动深度优先遍历的过程，转换为完全自动的深度优先搜索的程序代码（如图5）。

代码中，searched列表用来存储每一次字符串变化后的情况，一旦发现有重复模式出现，就用search=search[1：]去除字符串的首字母。整个程序代码居然只有十几行，这个结合了深度优先搜索和计算模型的算法，是否简单到令人震惊？看了本文的例子后，相信老师们对上好广度优先搜索和深度优先搜索的课，会有更大的把握了吧！

其实，即便是这样简单的程序代码，也还有进一步简化的可能性，大家有没有想到，实际上，对于字符串变化有没有陷入重复和停滞这一步的判断，并不是必须的！换言之，只要稍微更改一下规则表的使用方法，就可以在Notepad++中实现完全自动化的深度优先遍历，而程序代码也可以相应地大幅缩短，到底如何操作？这个问题就留给读者自己思考吧！