盡管數(shù)學(xué)總是給人留下枯燥乏味的印象,，但事實(shí)恰恰相反,，自古以來有太多引人入勝的游戲和玩具,，都是巧妙偽裝的數(shù)學(xué)問題，分散在數(shù)學(xué)的每個分支之內(nèi),。

在今天的節(jié)目里,，我們將從一些最古老的趣味數(shù)學(xué)問題開始，悄悄領(lǐng)略一下離散數(shù)學(xué)中,，圖論的趣味,。

－文字稿－

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

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

后來,，歐洲人就將這種不斷分支迂回錯綜復(fù)雜的空間布局叫做迷宮，然后就發(fā)展為一門在迷宮平面圖上尋找路徑的消遣游戲,，很受兒童歡迎,。

乍看起來，迷宮考的是眼力,，但這是因?yàn)槿四X面對較小的迷宮能迅速隨機(jī)遍歷出一條可能的路徑,。而對與更加復(fù)雜的迷宮，就需要專門的算法了：最簡單的是溜邊走,，可這對于設(shè)有橋梁和隧道,，或者起點(diǎn)終點(diǎn)不都在迷宮外部的迷宮就無效了。

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

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

在市民上百年的失敗之后,，歐拉在1736年證明了這壓根就不可能：兩島兩岸可以簡化成四個點(diǎn),，七座橋可以簡化成七條邊，所以七橋問題等價為能否一筆畫出這個圖案,，而這顯然不可能,，因?yàn)槿魏我粋€點(diǎn)如果發(fā)出奇數(shù)條邊，那么它不是起點(diǎn)就是終點(diǎn),，而這個圖中四個點(diǎn)都發(fā)出了奇數(shù)條邊,，遠(yuǎn)遠(yuǎn)超過了一條線起點(diǎn)終點(diǎn)各一個的配額。

將這個解法倒過來,，我們就能輕易解決“周游世界問題”了：在一個十二面體上,，如何沿著邊不重復(fù)地遍歷20個頂點(diǎn)。

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

在今天，這幾個問題都統(tǒng)一在圖論中的哈密頓路徑問題（Hamiltonian pathproblem）與哈密頓循環(huán)問題（Hamiltonian cycleproblem）之下,，如果將結(jié)點(diǎn)抽象為事件,，將邊抽象為關(guān)系，我們就會發(fā)現(xiàn)這是研究多個事物及其相互關(guān)系的利器,。

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

這的確從側(cè)面表明了圖論與計算機(jī)科學(xué)的親切關(guān)系——圖論是當(dāng)代計算機(jī)科學(xué)從數(shù)據(jù)結(jié)構(gòu)到算法實(shí)現(xiàn)到通信網(wǎng)絡(luò)等等方面的根基理論——雖然絕大多數(shù)成果都隱藏在叫人眼花繚亂的代碼之下,，但也有一些有趣的東西能被我們直接觀察到：比如現(xiàn)在很多人家中都有掃地機(jī)器人，如果僅僅是隨機(jī)亂跑,，或者撞到障礙物就折返,，那么機(jī)器人既不能充分地掃遍地面，也會浪費(fèi)許多精力在相同的地點(diǎn),。

所以掃地機(jī)器人的實(shí)際工作,，乃是確定整個房間的戶型，然后以最優(yōu)的路徑遍歷它——但是準(zhǔn)確的地圖需要準(zhǔn)確的定位,，準(zhǔn)確的定位又需要準(zhǔn)確的地圖,，這就需要給機(jī)器人裝備特殊的硬件了：目前最有效的解決方案，是讓機(jī)器人多角度的掃描屋頂,，獲取房間的形狀,，同時確定自己的位置，這被稱為“同步定位地圖構(gòu)建”（SLAM）,。

如此一來,，機(jī)器人就能規(guī)劃出最合理的行進(jìn)路線，遍歷全家的地面了,。

新一代ILIFE智意天耀X800智能掃地機(jī)器人采用最新升級的AI視覺導(dǎo)航系統(tǒng),，搭載3顆AI智能處理芯片并通過高清攝像頭和第二代陀螺儀系統(tǒng) CV-SLAM視覺導(dǎo)航算法，同步實(shí)現(xiàn)全屋掃描,、實(shí)時建圖,、精準(zhǔn)定位、智能分區(qū),，從而智能且快速的規(guī)劃清掃路線,，不漏掃，不重掃，讓清潔更全面,、高效,。

本文系網(wǎng)易新聞·網(wǎng)易號“各有態(tài)度”特色內(nèi)容