闖完迷宮 你的CPU燒了嗎

爲什麼看似簡單的電腦鼠走迷宮比賽,卻能燒掉所有參賽者的CPU? 比賽的規則很簡單,讓電腦鼠在迷宮中用最短的時間到達終點 這不僅要找到最短的路徑,還要考慮到轉彎的次數和角度 起初,大多數人會選擇一邊走策略 讓電腦鼠沿着迷宮的一條邊一直走,直至到達終點 而一旦將終點放置在迷宮的中間,這種策略就會失效 電腦鼠會一直在迷宮外圍,不停地兜圈子 之後,參賽者們發明出了深度優先搜索策略,即在每個岔路口中選擇一個方向 當遇到死衚衕或環路時,就返回至岔路口走另一個方向 雖然這種方法可以讓電腦鼠深入探索迷宮內部 但它只有無路可走時纔會返回,其找到的也並非是最短的路線 於是參賽者們又將其改進爲廣度優先搜索策略 即每次遇到岔路口就將所有路徑試走一遍 再標記出第二層的所有岔路口後再進行下一步探尋並循環往復 雖然這樣可以找到最短的路徑,但迷宮有着高達256個格子 如此徹底的搜索會浪費掉大量的時間 而你現在所看到的就是目前最常用的洪水填充搜索策略 其原理是假如迷宮沒牆壁遮擋,電腦鼠會畫出最短的路線 當遇到牆壁時就會進行標記,並默認其他區域依舊都是空白 這種算法會標記出每個格子與終點的距離 當電腦鼠碰壁返回就會重新標記 這時只需沿着數字遞減的方向走,就如同洪水淹沒迷宮一樣 最終讓電腦鼠快速找到終點 雖然這種策略無法保證首次通過就能找到最佳路徑 但卻能極大程度地避免了許多重複路線 但問題是,最短的路徑並不一定是最快的 比如這條最短路徑長度爲13.9米,而另一條路徑長度爲19.4米 由於轉彎的次數影響着電腦鼠的平均速度 所以最短路線需要花費57秒,而長路則只需45秒 如果想要用最短的時間到達終點,就要優化電腦鼠的過彎方式 比如用斜角過彎代替直角過彎 這樣可以減少轉彎的次數並縮短距離 或者用大角度過彎來減少轉彎次數 以此來提高通過速度 沒想到,就是這樣一個簡單的電腦鼠總迷宮比賽 裏面竟然蘊含了如此奇妙的科學知識 而屏幕前的你,CPU是否已經燒掉了呢?