C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):遞歸(3)

2019-11-17 05:04:09

字體：大中小

供稿：網(wǎng)友

　　關(guān)于迷宮，有一個引人入勝的希臘神話，這也是為什么現(xiàn)今每當(dāng)人們提到這個問題，總是興致勃勃（對于年青人，估計(jì)是RPG玩多了），正如雖然九宮圖連小學(xué)生都能做出來，我們總是自豪的說那叫“洛書”。這個神話我不復(fù)述了，有愛好的可以在搜索引擎上輸入“希臘神話迷宮”，就能找到很多的介紹。
C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):遞歸(3)

C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):遞歸(3)

　　迷宮的神話講述了一位英雄如何靠著“線團(tuán)”殺死了牛頭怪（玩過《英雄無敵》的朋友一定知道要想造牛頭怪，就必須建迷宮，也是從這里來的），我看到的一本編程書上援引這段神話講述迷宮算法的時候，不知是有意杜撰，還是考證不嚴(yán)，把這個過程敘述成：英雄靠著線團(tuán)的幫助——在走過的路上鋪線，每到分岔口向沒鋪線的方向前進(jìn)，假如碰到死胡同，沿鋪的線返回，并鋪第二條線——走進(jìn)了迷宮深處，殺死了牛頭怪。然而，神話傳說講的是，英雄被當(dāng)成貢品和其他的孩子送到了迷宮的深處，英雄殺死了牛頭怪，靠著線團(tuán)標(biāo)識的路線退出了迷宮。實(shí)際上，這個線團(tuán)只是個“棧”，遠(yuǎn)沒有現(xiàn)代人賦予給它的“神奇作用”。我想作者也是RPG玩多了，總想著怎樣“勇者斗惡龍”，然而，實(shí)際上卻是“勝利大逃亡”。

　　迷宮問題實(shí)際上是一個心理測試，它反映了測試者控制心理穩(wěn)定的能力——在一次次失敗后，是否失去冷靜最終陷在迷宮之中，也正體現(xiàn)了一句詩，“不識廬山真面目，只緣身在此山中”。換而言之，我們研究迷宮的計(jì)算機(jī)解法，并沒有什么意義，迷宮就是為人設(shè)計(jì)的，而不是為機(jī)器設(shè)計(jì)的，它之所以稱為“迷”宮，前提是人的記憶準(zhǔn)確性不夠高；假設(shè)人有機(jī)器那樣的準(zhǔn)確的記憶，只要他不傻，都能走出迷宮。現(xiàn)在可能有人用智能機(jī)器人的研究來反駁我，實(shí)際上，智能機(jī)器人是在更高的層面上模擬人的思考過程，只要它完全再現(xiàn)了人的尋路過程，它就能走出迷宮。但是，研究迷宮生成的計(jì)算機(jī)方法，卻是有意義的，因?yàn)槿藗兛偸怯信按约旱膬A向（不少人在RPG里的迷宮轉(zhuǎn)了三天三夜也不知道倦?。?，呵呵，笑談。

　　不管怎么說，還是親自研究一下計(jì)算機(jī)怎么走迷宮吧。

　　迷宮的存儲：按照慣例，用一個二維數(shù)組來表示迷宮，0表示墻，1表示通路，以后我們的程序都走下面這個迷宮。