遍歷查找中的計算思維

陳凱

機器人小睿身處一個洞穴迷宮中，迷宮中有許多空間，各個空間之間有道路相連。小睿的任務是搜集可能存在于各個空間中的能量石，并且不能有所遺漏。然而，小睿一旦出發(fā)，就必須按既定的命令以規(guī)定好的路徑運行，不能臨時改變方向。為了簡化問題，假設迷宮中不存在回路（就是兜了一圈回到原地的路徑），并且，從最開始的洞穴空間出發(fā)，只有左和右兩條道路可選擇，進到新的洞穴空間后，也一樣只有左右兩條道路可選（包含來時的道路，每個洞穴空間最多有三個方向可以走）。作為小睿的主人，應該怎樣給小睿下達指令，才能比較有效地搜索整個迷宮呢？

這其實就是一個樹結(jié)構(gòu)的遍歷問題，仔細想想，小睿的主人恐怕不是那么容易當?shù)摹Ｒ环矫妫朕k法做到多快好省全，使機器人既不能錯過某條路，也要盡量減少重走已探索過路徑的情況;另一方面，他還要考慮如何將自己的要求編碼成某種指令，用盡可能簡潔明確的方式傳達給機器人小睿。

或許有相當多的讀者知道，可以用廣度優(yōu)先搜索或深度優(yōu)先搜索算法來完成上述任務，但對于人工智能相關內(nèi)容的初學者來說，他所面對的知識和技能的網(wǎng)絡，可能也和迷宮一樣復雜。比如說，他要知道“樹”或者“圖”的數(shù)據(jù)結(jié)構(gòu);為了跟蹤機器人的行蹤，還要知道“堆棧”或者“隊列”的用法;為了將迷宮呈現(xiàn)出來，可能需要高維的數(shù)組或列表;為了能夠讓機器人自動探索路徑，需要用到循環(huán)或遞歸;并且，更重要的是，他要能將上述所有知識和技能綜合在一起，把機器人探路的程序編寫出來。

然而，正如大家已經(jīng)認識到的，計算思維的培養(yǎng)與程序算法的培養(yǎng)，兩者間雖然有聯(lián)系，但并不等同。在計算思維培養(yǎng)過程中，常常要關注如何對問題進行編碼，如何找出形式化的方法，使得問題的解決變得自動化，最后，才是將此自動化過程用算法實現(xiàn)出來。而在傳統(tǒng)的算法學習中，學習者往往是直接面對已經(jīng)相當成熟的、高效的問題解決方案。所以，在計算思維培養(yǎng)過程的初始，就要玩一種“假裝不知道”的游戲，把那些成熟的算法和程序代碼擱在一旁不去看它，試著自主探索某些形式化、自動化的方案，哪怕學習者的算法和程序水平有限，也不妨礙他們自主開展探索并逐漸形成別具一格的方案。

以樹結(jié)構(gòu)的遍歷查找為例，如何在正式推出成熟算法和程序代碼之前，先行開展自主探索活動，落實提高計算思維的教學目標呢？不妨來看看下面這個涂涂畫畫的例子吧。

● 首先來玩畫畫

第一個任務是畫畫，用圖畫模擬出洞穴迷宮的環(huán)境，用畫圖軟件就可以了，如圖1所示。這個任務，其實和后續(xù)指引機器人如何行動的指令編碼有關，它需要學習者對頭腦想象中的環(huán)境進行抽象，將不同空間之間的關系，盡可能用簡潔明了的方式呈現(xiàn)出來。

至于怎么在畫圖軟件中模擬迷宮環(huán)境，辦法很多，比如，畫矩形當作洞穴，在畫面正中間畫一個矩形，然后在它左右兩邊各畫一個矩形與中間的矩形邊緣相接，由此逐漸擴展。可以看出，這實際上就是一個二叉樹的結(jié)構(gòu)，在對它的結(jié)構(gòu)有了充分的了解之后，還可以拓展研究有更多分岔路徑的結(jié)構(gòu)。繪圖的時候，可以有意將新接進來的矩形的左右方位設置得很明顯，這是為了在后續(xù)遍歷時更容易描述機器人的行進動作。

● 然后來涂顏色

第二個任務，是試著依靠顏色指引機器人如何行進。想象一下，機器人一旦從初始空間出發(fā)，就需要根據(jù)實時情況的變化，保存或變更一些信息，其后才能根據(jù)這些信息指引自己在迷宮中繼續(xù)行動。本文游戲中，用五彩斑斕的顏色，來直觀地展現(xiàn)信息的存儲和變化過程。

例如，這里有一個非常簡單的方案：將搜索的空間分出不同的層級，探索的第一層就是最中間的空間，也就是機器人初始所在的位置，第二層是鄰近第一層空間的左側(cè)和右側(cè)的空間，第三層，是左側(cè)空間的左側(cè)空間，左側(cè)空間的右側(cè)空間，右側(cè)空間的左側(cè)空間，右側(cè)空間的右側(cè)空間，以此類推。

考慮如下方案A。由于空間總共有四層，所以它將用到紅綠藍黃四種顏色，若加上原本的白色，就是五種顏色，四種顏色放置在調(diào)色盤中，如果迷宮層級增加，調(diào)色盤也可相應擴充：①將正中間的空間涂成紅色。②搜索所有和紅色鄰近的空間，涂成綠色。③搜索所有和綠色鄰近的空間，涂成藍色。④搜索所有和藍色鄰近的空間，涂成黃色。每一層涂色完畢后，就可以將調(diào)色盤最上層的顏色擦除，這樣，機器人就知道下一層應該涂什么樣的顏色了。

按這樣的規(guī)則，可以很快將所有空間遍歷完成。方案A雖然簡單，但若是仔細思考一下，便會發(fā)覺有很大的漏洞，因為，這其實是要求，機器人小睿必須具有重復分身的能力，每進入一個新的空間，它就在這個空間一分為二，然后二者各自去探索左右兩個路徑。這樣的機器人，恐怕是比較難以制造出來的。

接著，考慮如下方案B。在這個方案中，除了原本的白色，就只用到紅色：①機器人由低層向高層行進，若行進到無法行進時（不再有更高層），則原路返回到最初始的空間，返回時不進行新的探測任務。②當?shù)谝粚涌臻g（也就是最初始的空間）遇到機器人第四次返回時，則變成紅色。③當?shù)诙涌臻g（有兩個空間）遇到機器人第二次返回時，則變成紅色。④當?shù)谌龑涌臻g（有四個空間）遇到機器人第一次返回時，則變成紅色。⑤若當前空間為白色，則探索左側(cè)空間，否則，探索右側(cè)空間。

這個方案也可以遍歷所有空間，不過，它的規(guī)則的描述比較麻煩，除了標注顏色，還需要額外的計數(shù)器來計算機器人返回了幾次，當然，這個計數(shù)器也是可以用顏色變化來實現(xiàn)的，但如此一來，問題解決的復雜性就大大增加了。另一個問題是，每次機器人將一條路徑走到底后，就必須返回“老巢”，無法在回程時順便探索一下其他路徑，所以效率不高。另外，若是從某個空間分岔的路徑多于兩條，也很難基于此方案進行擴充修改。

考慮如下方案C。該方案使用到十五種顏色，包含白色就是十六種，實際上，就是準備好足夠多的顏色，給每個空間做一個標識。這個方案也用到了調(diào)色盤，如果層級增加，調(diào)色盤也可相應擴充：①任取一種顏色將正中間的空間涂色，然后將選取的顏色填在右側(cè)調(diào)色盤最下一格。②任取一種顏色，對剛才所涂顏色的空間的后一層左側(cè)空間涂色，然后將選取的顏色填在右側(cè)調(diào)色盤中先前填色格子的上一個格子中，進入該空間，然后再執(zhí)行步驟2;如不再能找到未調(diào)色的后一層左側(cè)空間，則找到未調(diào)色的后一層右側(cè)空間，將選取的顏色填在右側(cè)調(diào)色盤中先前填色格子的上一個格子中，進入該空間，然后執(zhí)行步驟2;若未找到后一層左側(cè)和右側(cè)空間，則擦除調(diào)色盤最上一層顏色（填入白色即可），然后執(zhí)行步驟3。③按調(diào)色盤最上一層顏色的指示，回到當前空間的前一層空間，然后執(zhí)行步驟2。

在操作過程中需要注意的是，每次擦除顏色，都只是擦除調(diào)色盤上的顏色，而不是擦除迷宮空間里的顏色。

圖2是整個方案實施中的某一步。

在整個過程中，調(diào)色盤其實起到了堆棧的作用，而機器人行走的路徑，則模擬了深度優(yōu)先搜索的整個過程，規(guī)則指令運行起來頗為波折，但跟蹤過程也很有趣味。此方案的優(yōu)點是，如果遇到有更多條路徑分岔的情況，也很容易修改規(guī)則來完成探路游戲。大家若有興趣，還可以把迷宮做成棋盤，把規(guī)則指令做成積木塊，把積木塊打亂之后，思考怎么重新排列積木塊，來指揮機器人完成迷宮探索任務。

除了上面提到的方案A、B、C，其實還有更多方案，比如，也可以不依賴調(diào)色盤來完成探路任務，這就需要用到遞歸，或是用并行自動機的方法，限于篇幅這里不再一一描述，給讀者留一些探索空間。

● 接著來猜字謎

重新考察方案B，如果將機器人行進方向分為L和R（前進時總是往后一層，返回時總是往前一層），則可以看出，探索第二層空間時，機器人執(zhí)行的是LRRL，探索第三層空間時，機器人執(zhí)行的是LLRRLRRLRLLRRRLL，到了第四層的時候，全部的指令要是寫出來的話就比較長了：LLLRRRLLRRLLLRLRLRLRRRLLRLLLRRRLRLRLRRLLLRRRRLLL。

其實，探索第二層空間的指令，和探索第三層、第四層空間的指令，是存在著演變變化規(guī)律的，怎么找出規(guī)律呢？

由于返回的路徑總是與前進路徑方向相反，所以不妨簡寫為“B”，于是上述指令字符串就變成了這樣：LLLBLLRBLRLBLRRBRLLBRLRBRRLBRRRB。

可以看出，方案B的指令字符串的演變，其實和二進制計數(shù)器完全一致，這也說明了，為什么可以用二進制數(shù)來對二叉樹的節(jié)點進行標注。

接著，再重新考察方案C，也將機器人行進方向分為L和R（這里暫時先不考慮到底是往前一層還是后一層），假如整個迷宮只有第一層和第二層空間的話，則機器人的行進方向就是LRRL，若是有三層空間，則機器人的行進方向是LLRRLRRLRRLL，如果是探索四層空間的話，行進方向的指令寫出來后也比較長，不過比起方案B的指令字符串要短一些：LLLRRLRRLRRLLRRLLRRL

RRLRRLLL。

對于不同層級的迷宮，機器人探索路徑的行動方向也是有規(guī)律可尋的，這個規(guī)律和一種常用的自動化過程——迭代有著密切的關系，并且，在一系列的迭代之后，實際上起到了分形的效果。方案C的指令字符串的演變規(guī)律如下：①初始字符串為LxRRxL。②將字符串中的x替換為LxRRxL，反復此過程。

但方案C與方案B不同，它還需要更多地考慮機器人在什么時候前進一層，什么時候后退一層，如果將機器人前進和后退的方向標為“U”和“D”，就形成了新的指令字符串，可以將“U--D”字符串和“L--R”字符串結(jié)合使用，來指引機器人行進，大家能看出“U--D”指令字符串中的規(guī)律嗎？

兩層迷宮：UDDU

三層迷宮：UUDUDDUUDU

DD

四層迷宮：UUUDUDDUUD

UDDDUUUDUDDUUDUDDD

本期參考答案：設初始狀態(tài)為UxDUxD，然后執(zhí)行將x替換為“UxDUxD”的動作，反復進行迭代即可。

對此期主題有任何好主意和建議，請發(fā)送稿件至kaikai_rabbit@sina.com（專欄作者）或tougao4@china.it.edu.cn（雜志社）。