從迷宮到掃地機器人 | 混亂博物館

來自專欄混亂博物館55 人贊了文章

儘管數學總是給人留下枯燥乏味的印象，但事實恰恰相反，自古以來有太多引人入勝的遊戲和玩具，都是巧妙偽裝的數學問題，分散在數學的每個分支之內。

在今天的節目里，我們將從一些最古老的趣味數學問題開始，悄悄領略一下離散數學中，圖論的趣味。

－文字稿－

說起數學問題，一般人總想到連綿不斷的方程、函數與計算，為此怵頭苦惱，但還有一類從小就給我們帶來許多樂趣的「趣味數學」就完全不是這樣，就比如走迷宮，我們甚至很難意識到它也是數學問題。

「克里特島」的迷宮大概是流傳最廣的迷宮傳說了：在神話中，克里特島國王米諾斯得罪了波塞冬,受到天譴，他的王后就與一頭牛私通，生下了牛頭人米諾陶，一個吃人的可怕怪物。米諾斯於是令代達羅斯建造了一座最複雜的迷宮困住米諾陶，強迫雅典人每年進獻9對童男童女給米諾陶吃——直到大英雄忒修斯來到克里特島，對他一見鍾情的公主阿里阿德涅給了他一個線團，助他斬殺了米諾陶，還走出了迷宮。

後來，歐洲人就將這種不斷分支迂迴錯綜複雜的空間布局叫做迷宮，然後就發展為一門在迷宮平面圖上尋找路徑的消遣遊戲，很受兒童歡迎。

乍看起來，迷宮考的是眼力，但這是因為人腦面對較小的迷宮能迅速隨機遍歷出一條可能的路徑。而對與更加複雜的迷宮，就需要專門的演算法了：最簡單的是溜邊走，可這對於設有橋樑和隧道，或者起點終點不都在迷宮外部的迷宮就無效了。

這就是為什麼忒修斯需要一個線團了——有了線團，他就知道那條路已經走過，從而不斷遍歷新的路徑——這在今天稱為特萊謀演算法（Trémaux），一個典型的圖論演算法。

一般認為，圖論起源於歐拉破解柯尼斯堡七橋問題（Seven Bridges of K?nigsberg），即東普魯士的柯尼斯堡，今日俄羅斯的加里寧格勒，在穿城而過的河中有兩個島，共有7座橋以對稱的位置相連，人們茶餘飯後散步，便思考能否不重複地一次走遍七座橋。

在市民上百年的失敗之後，歐拉在1736年證明了這壓根就不可能：兩島兩岸可以簡化成四個點，七座橋可以簡化成七條邊，所以七橋問題等價為能否一筆畫出這個圖案，而這顯然不可能，因為任何一個點如果發出奇數條邊，那麼它不是起點就是終點，而這個圖中四個點都發出了奇數條邊，遠遠超過了一條線起點終點各一個的配額。

將這個解法倒過來，我們就能輕易解決「週遊世界問題」了：在一個十二面體上，如何沿著邊不重複地遍歷20個頂點。

然而另一個更古老的類似問題卻難倒了歐拉：全世界的象棋都源於印度的恰圖蘭卡，而從9世紀開始，人們就在思考馬走日能否不重複地走遍棋盤上的每一個格子——這被稱為「騎士巡邏問題」。如果將這個問題抽象出來，就是在這樣8×8的結點圖中，能否找到一條路徑不重複遍歷所有結點。其中的可能性已經達到了10的51次方數量級，即便現代的計算機也難以窮舉——這個問題直到1823年才得到了系統化的解決，但直到今天，我們也只算出了回到起點的走法有26534728821064種，而不回到起點的走法仍是個未知的大數字。

在今天，這幾個問題都統一在圖論中的哈密頓路徑問題（Hamiltonian pathproblem）與哈密頓循環問題（Hamiltonian cycleproblem）之下，如果將結點抽象為事件，將邊抽象為關係，我們就會發現這是研究多個事物及其相互關係的利器。

比如更經典更著名的四色問題，即問能否只用四種顏色給任意平面地圖上色，明確區分所有鄰國。就可以將所有的國家都抽象為一個有顏色的點，如果某個國家有一處飛地，就增加一個同顏色的點，兩個國家相鄰，就在對應的點之間連接一條邊。那麼四色問題就是在問，是否存在某種上色方案，使每條邊的端點都有不同的顏色——孰料這個問題異常複雜，直到1976年，當時最快的計算機，IBM 360耗時1200小時，才首次解決了這個問題，而完全出自人腦的解法至今尚未出現。

這的確從側面表明了圖論與計算機科學的親切關係——圖論是當代計算機科學從數據結構到演算法實現到通信網路等等方面的根基理論——雖然絕大多數成果都隱藏在叫人眼花繚亂的代碼之下，但也有一些有趣的東西能被我們直接觀察到：比如現在很多人家中都有掃地機器人，如果僅僅是隨機亂跑，或者撞到障礙物就折返，那麼機器人既不能充分地掃遍地面，也會浪費許多精力在相同的地點。

所以掃地機器人的實際工作，乃是確定整個房間的戶型，然後以最優的路徑遍歷它——但是準確的地圖需要準確的定位，準確的定位又需要準確的地圖，這就需要給機器人裝備特殊的硬體了：目前最有效的解決方案，是讓機器人多角度的掃描屋頂，獲取房間的形狀，同時確定自己的位置，這被稱為「同步定位地圖構建」（SLAM）。

如此一來，機器人就能規划出最合理的行進路線，遍歷全家的地面了。

新一代ILIFE智意天耀X800智能掃地機器人採用最新升級的AI視覺導航系統，搭載3顆AI智能處理晶元並通過高清攝像頭和第二代陀螺儀系統+CV-SLAM視覺導航演算法，同步實現全屋掃描、實時建圖、精準定位、智能分區，從而智能且快速的規劃清掃路線，不漏掃，不重掃，讓清潔更全面、高效。