陳凱

在人工智能的學(xué)習(xí)過程中，有不少經(jīng)典的算法需要掌握，如一般要掌握樹結(jié)構(gòu)或圖結(jié)構(gòu)中數(shù)據(jù)的搜索方法，其中比較基礎(chǔ)的內(nèi)容，是對樹結(jié)構(gòu)做廣度優(yōu)先搜索和深度優(yōu)先搜索。但在實(shí)際教學(xué)中，卻可能會(huì)遇見一個(gè)矛盾，若是學(xué)校并沒有將“數(shù)據(jù)結(jié)構(gòu)”模塊與“人工智能初步”模塊一起列入選擇性必修的內(nèi)容，那么在講解樹結(jié)構(gòu)的搜索問題時(shí)，面對學(xué)生從未接觸過的“樹”這種數(shù)據(jù)結(jié)構(gòu)，教師該如何平衡好教學(xué)內(nèi)容的安排呢？

一個(gè)辦法是干脆繞過對“樹”這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)過程的講解，直接使用現(xiàn)成封裝好的對象，對樹結(jié)構(gòu)進(jìn)行操作。這樣雖然可以降低教學(xué)上的難度，卻難免會(huì)有些空中造屋或隔靴搔癢的感覺，并且，由于使用了現(xiàn)成的對象，即便完成了樹結(jié)構(gòu)的遍歷和搜索任務(wù)，學(xué)生的成就感也不會(huì)很充足。所以這里就有了一個(gè)值得思考的問題：怎樣尋找替代方案，簡化數(shù)據(jù)結(jié)構(gòu)和程序代碼，減少教學(xué)的容量，與此同時(shí)，還要將實(shí)現(xiàn)樹結(jié)構(gòu)中的搜索的關(guān)鍵思想表現(xiàn)出來，為計(jì)算思維的培養(yǎng)提供落實(shí)點(diǎn)。本文給出的“字母跑馬燈”教學(xué)活動(dòng)，就是為解決上述問題而做的一個(gè)嘗試。

● 樹和字母跑馬燈

先來畫一棵樹，為了清晰簡單，此處的樹的分叉最多為2，并且，樹的節(jié)點(diǎn)信息，就是它的名字本身。如圖1所示，若從根節(jié)點(diǎn)開始，對這棵樹進(jìn)行廣度上的遍歷，那么依次訪問的節(jié)點(diǎn)應(yīng)該是：A—B—C—D—E—F—G—H—I—J。訪問節(jié)點(diǎn)的名字“恰好”按字母順序排列，這當(dāng)然是筆者有意安排所致。

可以根據(jù)每個(gè)節(jié)點(diǎn)和它分叉通向的節(jié)點(diǎn)建立一張規(guī)則表，這樣，即便沒有直觀看到樹結(jié)構(gòu)的展示圖，也可以在拓?fù)鋵W(xué)的意義上，將樹的結(jié)構(gòu)重新還原出來，規(guī)則表中，不再繼續(xù)分叉的節(jié)點(diǎn)，后續(xù)的字符串為空（如圖2）。

接下來，就可以玩名叫《字母跑馬燈》的游戲了，首先設(shè)初始值，就是先放置樹的根節(jié)點(diǎn)，所以可以在紙上寫下只包含一個(gè)字母“A”的字符串。然后：第一步，將字符串中的首字母搬運(yùn)到字符串的末尾;第二步，將字符串末尾的字母，按規(guī)則表進(jìn)行替換;第三步，從第一步開始重復(fù)動(dòng)作。

可以跟蹤觀察一下效果如何，初始時(shí)字符串是“A”，第一步是將首字母（就是“A”）搬運(yùn)到字符串最后，當(dāng)然，因?yàn)樽址兄挥幸粋€(gè)字母，結(jié)果還是“A”，接下來第二步，根據(jù)規(guī)則表，字符串變化成了“BC”，然后第三步，回到第一步接著進(jìn)入第二輪變化，第一步進(jìn)行搬運(yùn)，字符串變成“CB”，然后第二步，字符串變成“CDE”……每一輪的操作產(chǎn)生的字符串變化過程如下：

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

可以看出，字符串的首字母就是廣度遍歷時(shí)依次訪問的節(jié)點(diǎn)名字。實(shí)際上，這種運(yùn)用了“搬運(yùn)—替換”規(guī)則的字符串的迭代過程，是一種被稱為標(biāo)簽系統(tǒng)（Tag-System）的計(jì)算模型。這種計(jì)算模型當(dāng)然不是只能用來模擬樹結(jié)構(gòu)的遍歷，它還能用來實(shí)現(xiàn)什么功能，這個(gè)問題留給讀者們?nèi)ニ伎肌?/p>

● 將變化過程自動(dòng)化

可以利用工具，將以上的搬運(yùn)和迭代過程變成自動(dòng)化的動(dòng)作。只要利用文字編輯工具的宏的功能，就可以實(shí)現(xiàn)自動(dòng)化，整個(gè)過程中，并不需要輸入任何的程序代碼。

下面，以NotePad++軟件為例來說明宏的制作，此軟件可從網(wǎng)絡(luò)上免費(fèi)下載，也可以使用Microsoft Word、Open Office等辦公軟件來完成類似操作。初始時(shí)，在NotePad++的文字編輯區(qū)中，寫入“*A”，這里的星號(hào)起到替換操作標(biāo)識(shí)的作用。星號(hào)后的字母，就是將要執(zhí)行替換操作的對象。

第一步，創(chuàng)建一個(gè)名為“Move”的宏，這個(gè)宏的作用是將首字母搬運(yùn)到字符串末尾。這個(gè)宏中包含的操作步驟是：按“Home”鍵將光標(biāo)移到行首，按“Shift”鍵和右箭頭選中星號(hào)和字符串首字母，執(zhí)行剪切操作，按“End”鍵將光標(biāo)移到行尾，執(zhí)行粘貼操作。

第二步，創(chuàng)建一個(gè)名為“Replace”的宏，這個(gè)宏的作用是按規(guī)則表進(jìn)行替換。這個(gè)宏中包含的操作步驟是：依次將“*A”替換成“BC”，將“*B”替換成“DE”，將“*C”替換成“FG”，以此類推。當(dāng)規(guī)則表全部應(yīng)用完畢后，還要按“Home”鍵，將光標(biāo)移到行首，并補(bǔ)充一個(gè)星號(hào)，重新設(shè)置好替換標(biāo)識(shí)。

這樣一來，只要反復(fù)執(zhí)行“Move”和“Replace”這兩個(gè)宏，就可以實(shí)現(xiàn)樹結(jié)構(gòu)的廣度優(yōu)先遍歷了。下面回顧一下解決遍歷問題的思路：先是將形象的樹的結(jié)構(gòu)抽象成替換規(guī)則的編碼，然后用標(biāo)簽系統(tǒng)這種計(jì)算模型來實(shí)施符號(hào)的搬運(yùn)和替換，最后再利用文字編輯軟件的宏，來實(shí)現(xiàn)符號(hào)的搬運(yùn)和替換的自動(dòng)化。這些都與計(jì)算思維的培養(yǎng)目標(biāo)相契合。

● 極其簡單的廣度優(yōu)先搜索代碼

在熟練掌握符號(hào)替換的宏的制作后，將廣度優(yōu)先遍歷的過程轉(zhuǎn)而用程序代碼實(shí)現(xiàn)，就非常容易了。在實(shí)際的人工智能教學(xué)安排中，對于低年級(jí)的學(xué)生，可以考慮僅利用宏來進(jìn)行操作實(shí)驗(yàn)，而高年級(jí)的學(xué)生，或有算法和程序設(shè)計(jì)基礎(chǔ)的學(xué)生，就可以更上一層樓，借鑒用標(biāo)簽系統(tǒng)這種計(jì)算模型實(shí)現(xiàn)樹結(jié)構(gòu)遍歷的方法，編寫出廣度優(yōu)先搜索的代碼。

這里提供了用Python代碼實(shí)現(xiàn)的例子，代碼中，node列表存儲(chǔ)的是樹的節(jié)點(diǎn)的名稱，link列表存儲(chǔ)的是樹的每一個(gè)節(jié)點(diǎn)分叉的后續(xù)節(jié)點(diǎn)的名稱，data是一個(gè)字典，其中存儲(chǔ)的是樹中每一個(gè)節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)信息。search=search[1：]和search=search+link[myindex]兩句語句實(shí)現(xiàn)了符號(hào)的搬運(yùn)和替換。代碼可以說是極其簡單了，如下頁圖3所示。

● 相當(dāng)簡單的深度優(yōu)先搜索代碼

將上面的方法稍微改一下，就可以實(shí)現(xiàn)深度優(yōu)先搜索了，還是可以試著在Notepad++里玩符號(hào)替換的游戲，假設(shè)初始的字符串還是“*A”，這一次不需要搬運(yùn)了，只要對字符串最前面的字母進(jìn)行替換即可，步驟如下：

第一步，根據(jù)樹結(jié)構(gòu)連接的規(guī)律，將“*A”替換成“BCA”（其實(shí)是將“*A”替換成“BC”后再加上“A”自己），將“*B”替換成“DEB”，將“*C”替換成“FGC”，將“*D”替換成“D”（其實(shí)是將“*D”替換成空字符串再加上“D”自己），以此類推。將以上步驟包裝成宏。這種替換字符串的方法稱為馬爾科夫重寫系統(tǒng)，是另一種十分有用的計(jì)算模型。

第二步，按“Home”鍵回到行首，補(bǔ)充一個(gè)星號(hào)。因?yàn)橹挥泻唵蔚囊粋€(gè)動(dòng)作，即便不包裝成宏也是可以的。

然后只要反復(fù)執(zhí)行以上兩步，大致就可以實(shí)現(xiàn)深度優(yōu)先的遍歷了，但在實(shí)際操作中，會(huì)遇見字符串變化陷入停滯或重復(fù)模式的問題。比如，“*A”變成“*BCA”，再變成“*DEBCA”，由于字符“D”對應(yīng)的是空字符串，于是經(jīng)過一輪變化后，字符串還是“*DEBCA”。

解決的方法是要加入一點(diǎn)人工干預(yù)，當(dāng)發(fā)現(xiàn)字符串的變化陷入停滯或重復(fù)的模式中時(shí)，就手動(dòng)刪除行首的字母，若刪除行首字母后仍然陷入停滯或重復(fù)的模式，則繼續(xù)刪除行首字母。雖然這樣做會(huì)顯得整個(gè)過程不特別自動(dòng)化，但也意外地帶來了思考的樂趣：若將要探索的樹比較龐大，那么，是不是應(yīng)該刪除行首字母？應(yīng)該什么時(shí)候刪除行首字母？這就需要考驗(yàn)記憶和判斷能力了。若稍微改一下游戲規(guī)則，如在規(guī)則表中特意放置一個(gè)小寫字母，那就可以在Notepad++中玩迷宮尋寶（尋找小寫字母）的游戲了。

如果是借助程序代碼，判定字符串變化是否陷入停滯或重復(fù)的模式就十分簡單了，只要將每次字符串的變化情況存入列表，然后在新的一輪字符串變化后，檢查其是否與列表中已有的字符串重復(fù)，就可以達(dá)到目的了。按這樣的思路，可以將半自動(dòng)深度優(yōu)先遍歷的過程，轉(zhuǎn)換為完全自動(dòng)的深度優(yōu)先搜索的程序代碼（如圖5）。

代碼中，searched列表用來存儲(chǔ)每一次字符串變化后的情況，一旦發(fā)現(xiàn)有重復(fù)模式出現(xiàn)，就用search=search[1：]去除字符串的首字母。整個(gè)程序代碼居然只有十幾行，這個(gè)結(jié)合了深度優(yōu)先搜索和計(jì)算模型的算法，是否簡單到令人震驚？看了本文的例子后，相信老師們對上好廣度優(yōu)先搜索和深度優(yōu)先搜索的課，會(huì)有更大的把握了吧！

其實(shí)，即便是這樣簡單的程序代碼，也還有進(jìn)一步簡化的可能性，大家有沒有想到，實(shí)際上，對于字符串變化有沒有陷入重復(fù)和停滯這一步的判斷，并不是必須的！換言之，只要稍微更改一下規(guī)則表的使用方法，就可以在Notepad++中實(shí)現(xiàn)完全自動(dòng)化的深度優(yōu)先遍歷，而程序代碼也可以相應(yīng)地大幅縮短，到底如何操作？這個(gè)問題就留給讀者自己思考吧！