最短路徑:向螞蟻學算法

2021-02-17 木末風吟

整理:白泉     

來源:白泉讀書(ID:myheartmyhome)

蟻群尋找食物都沿著最短路徑,即便遇到外界幹擾,總能很快調整過來,找到最佳的路徑。螞蟻這種自我學習、不斷修正、自我進化的能力,被稱為蟻群算法。

在自然界中,螞蚊的食物源總是隨機分散於蟻巢周圍,在蟻群協調、分工、合作後總能找到一條通往食物源的最短路徑。現實中,我們能觀察到大量螞蟻在巢穴與食物源之間形成近乎直線的路徑,而不是曲線、圓等其他形狀(見下圖)。

蟻群不僅能完成複雜的任務,還能適應環境的變化,如在蟻群運動路線上突然出現障礙物時,一開始各只螞蟻分布是均勻的,不管路徑長短,螞蟻總是先按同等概率選擇各條路徑(見下圖)。

蟻在運動過程中,能在其經過的路徑上留下信息素,並且能感知到這種物質的存在及其強度,並以此指導自己運動的方向,螞蟻傾向於信息素濃度高的方向移動。在相同時間內較短路徑上的信息素量就遺留得較多,則選擇較短路徑得螞蟻也隨即增多(見下圖)。

不難看出,由於大量螞蟻組成得蟻群集體行為表現出的一種信息正反饋現象在某一路徑上走過的螞蟻越多,則後來者選擇該路徑的概率就越大,螞蟻個體質檢就是通過這種信息交流機制來搜索食物,並最終沿著最短路逕行進(見下圖)。

算法有別於傳統編程模式,程序是基於一定規則隨機運行來尋找最佳配置,也就是說,當程序最開始找到目標的時候,路徑可能不是最優的。但是,程序可以通過螞蟻尋找食物時候的信息素原理,不斷地去修正原來的路線,使整個路線越來越短,也就是說,程序執行的時間越長,所獲得的路徑就越可能接近最優路徑。這看起來很類似與我們所見的無數例子進行歸納概括形成最佳路徑的過程。實際上好似是程序的一個自我學習、自我進化的過程,這是算法。

拿螞蟻尋找最短路來說,事實上每隻螞蟻能了解到的範圍很局限,每隻螞蟻之間也沒有直接的關係,但是每隻螞蟻都和環境發生交互,而通過信息素這個紐帶,實際上把各個螞蟻之間關聯起來了。比如,當只螞蟻找到了食物,它並沒有直接告訴其它螞蟻這兒有食物,而是向環境播撒信息素,當其它的螞蟻經過它附近的時候,就會感覺到信息素的存在,進而根據信息素的指引找到了食物。

那麼,螞蟻究竟是怎麼找到食物的呢?

在沒有螞蟻找到食物的時候,環境沒有有用的信息素,那麼螞蟻為什麼會相對有效的找到食物呢?這要歸功於螞蟻的移動規則,尤其是在沒有信息素時候的移動規則。

首先,它要能儘量保持某種慣性,這樣使得螞蟻儘量向前方移動(開始,這個前方是隨機固定的一個方向),而不是原地無謂的打轉或者震動;

其次,螞蟻要有一定的隨機性,雖然有了固定的方向,但它也不能像粒子一樣直線運動下去,而是有一個隨機的幹擾。這樣就使得螞蟻運動起來具有了一定的目的性,儘量保持原來的方向,但又有新的試探,尤其當碰到障礙物的時候它會立即改變方向,這可以看成一種選擇的過程,也就是環境的障礙物讓螞蟻的某個方向正確而其他方向則不對。這就解釋了為什麼單個螞蟻在複雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。當然,在有一隻螞蟻找到了食物的時候,其他螞蟻會沿著信息素很快找到食物的。

這一是要歸功於信息素,另外要歸功於環境,具體說是計算機時鐘。信息素多的地方顯然經過這裡的螞蟻會多,因而會有更多的螞蟻聚集過來。假設有兩條路從窩通向食物,開始的時候,走這兩條路的螞蟻數量同樣多(或者較長的路上螞蟻多,這也無關緊要)。當螞蟻沿著一條路到達終點以後會馬上返回來,這樣短的路螞蟻來回一次的時間就短,這也意味著重複的頻率就快,因而在單位時間裡走過的螞蟻數目就多,酒下的信息素自然也會多,自然會有更多的螞蟻被吸引過來,從而灑下更多的信息素,而長的路正相反,因此,越來越多地螞蟻聚集到較短的路徑上來,最短的路徑就近似找到了。

也許有人會問局部最短路徑和全局最短路的問題,實際上螞蟻逐漸接近全局最短路的,為什麼呢?這源於螞蟻會犯錯誤,也就是它會按照一定的概率不往信息素高的地方走而另闢蹊徑,這可以理解為一種創新,這種創新如果能縮短路途,那麼根據剛才敘述的原理,更多的螞蟻會被吸引過來。     

螞蟻這種尋找窩和食物之間最短路的策略機制,就是一種不斷自我進化的算法。

通常,人們對於人生成功的策略理解太簡單了,認為成功的人都是找到了某種規律或秘訣(中國人傳統裡把這規律或秘訣稱之為「道」),似乎只要找到「道」,人生所有的難題都迎刃而解。

有沒有這種規律或秘訣呢?沒有!那也就更沒有因得「道」而直接登上人生巔峰的!人生就象螞蟻尋找食物一樣,只能通過不斷學習、修正、進化,為自己不斷增大概率,實現「迭代升級」。這大概就叫人生算法。

橋水基金創始人達利歐撰寫了一本書,書名叫《原則》,書中分享了成功原則,他說:算法,就是在連續性基礎上運行的原則。

巴菲特的搭檔查理·芒格也說:當成功概率很高的時刻,下最大的賭注,而其餘時間按兵不動。這說的也就是人生算法。

網絡上有這麼一個具體的問題,可以幫助我們更具體地了解人生算法。

問題是這樣的——

假設你現在面對兩個按鈕:按下第一個按鈕,直接給你一百萬美元;按下第二個按鈕,你有50%的機會拿到一億美元,也有50%機會什麼都沒有。

這兩個按鈕只能選一個,你選哪個? 

有人選第一個,理由是落袋為安,100萬美元也不是個小數。

有人選第二個,理由是萬一成功,從此就成了人生贏家。

但是,這道題的核心不是考這個,這道題是有唯一正確答案的。那就是要選第二個按鈕——一半的機會拿到一億美元。

你可以找到一個人並告訴他,我有一半機會能拿到一億美元;如果你給我一百萬美元,我就願意把這個機會分享給你。你去按,什麼也沒有,你認倒黴,如果拿到了一億美元,咱們一人一半。

有的算法,引入了風險,但沒有風控機制,這只能初級;有的算法,引入了風險共擔機制;有的算法引入了市場化機制。算法越迭代,成功的概率就不斷地提高。

而當你掌握核心算法,所要做的事就是大量地重複這個動作。說得更簡單一點,人生算法就是你面對世界不斷重複的、最基本的路,找到它,重複它,強化它。

這樣一來,你想要抓住的機會,就是大概率的事件。

相關焦點

  • 圓柱體側面展開的最短路徑——螞蟻行程問題
    圓柱體側面展開的最短路徑模型分析:上圖為無底的圓柱體側面展開圖.如果螞蟻從點A沿圓柱表面爬行一周,到點B的最短路徑就是展開圖 BAA′B′中AB' 的長度,AB'=√(AA'+A'B′),做此類題目的關鍵就是, 正確展開立體圖形, 利用「兩點之間線段最短」或「兩邊之和 大於第三邊」準確找出最短路徑。
  • 謎之問題:溺水救人的最短路徑
    在大多數情況下,光會選擇時間最短的路程。費曼的物理講義有更多細節)。他證明,當光從一點傳播到另一點時,總是會選擇耗時最短的路徑。這一現象奇妙的暗示著,當救生員想要儘可能快的到達呼救者時,要問自己光會怎麼做。你也可以這麼理解,當你用雷射筆照向一碗水時,雷射也面臨著和救生員一樣的問題。
  • 勾股定理:幾何最短路徑問題
    最短路線問題通常是以「平面內連結兩點的線中,線段最短」為原則引申出來的.人們在生產、生活實踐中,常常遇到帶有某種限制條件的最近路線即最短路線問題.對於數學中的最短路線問題可以分為兩大類:第一類為在同一平面內;第二類為空間幾何體中的最短路線問題,對於平面內的最短路線問題可先畫出方案圖,然後確定最短距離及路徑圖。對於幾何題內問題的關鍵是將立體圖形轉化為平面問題求解,然後構造直角三角形,利用勾股定理求解.
  • 算法:有向無環圖的最短路徑
    (點擊上方藍字,快速關注我們)編譯:ImportNew - 郭楚沅如有好文章投稿,請點擊 → 這裡了解詳情介紹我們已經知道了如何通過Dijkstra算法在非負權圖中找到最短路徑即使圖中有負權邊,我們也知道通過Bellman-Ford算法找到一個從給定的源點到其它所有節點的最短路徑。現在我們將看到一個在線性時間內運行得更快的算法,它可以在有向無環圖中找到從一個給定的源點到其它所有可達頂點的最短路徑,又名有向無環圖(DAG)。由於有向無環圖無環所以我們不必擔心負環的問題。
  • 中考數學專題系列五十七:初中數學,「螞蟻怎樣走最短」題型歸納
    連接AB,根據兩點之間線段最短,則線段AB的長就是螞蟻爬的最短路線長。3、算最短。在直角三角形ABC中,由題意知道線段AC的長等於底面圓周長的一半,所以AC=15,線段BC的長等於圓柱的高,所以BC=20,根據勾股定理得,AB=25.所以螞蟻爬的最短路線長約為25.
  • 中考數學試題解析之最短路徑問題
    一天,一位羅馬將軍專程去拜訪他,向他請教一個百思不得其解的問題:將軍每天從軍營 A 出發,先到河邊飲馬,然後再去河岸同側的 B 地開會,應該怎樣走才能使路程最短?從此,這個被稱為 「將軍飲馬」 的問題廣泛流傳.
  • 單源最短路徑-Dijkstra 算法
    Dijkstra(迪傑斯特拉)算法是典型的單源最短路徑算法,用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。可以簡單描述為:最短路徑的子路徑也是最短路徑。2.如果考慮到邊的權值為正數,則由定理 7.2 可以得到以下結論:若π = (s , u1 , u2 , … , uk)是從s到uk的最短路徑,則從s到各頂點ui(i=1, 2, …k)的最短路徑是嚴格遞增的。
  • 最短路徑:Dijkstra 算法和 Floyd 算法
    主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法,在很多專業課程中都作為基本內容有詳細的介紹,如數據結構,圖論,運籌學等等。注意該算法要求圖中不存在負權邊。問題描述:在無向圖 G=(V,E) 中,假設每條邊 E[i] 的長度為 w[i],找到由頂點 V0 到其餘各點的最短路徑。
  • 最短路徑問題模型匯總
    【問題概述】最短路徑問題是圖論研究中的一個經典算法問題, 旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑
  • 5.初中數學:怎麼求螞蟻吃蜂蜜,爬行的最短路徑?勾股定理經典考題
    初中數學:怎麼求螞蟻吃蜂蜜,爬行的最短路徑?勾股定理經典考題。大家先在草稿本上,認真地做一遍,然後再看後面的視頻。期待您在評論區留言。溫馨提醒:因為視頻內容越來越多,為了更好的把內容進行分類歸納,方便大家更系統的學習,將所有內容優化成三個微信公眾號,分為幾何部分、代數部分、七年級數學。
  • 八年級上冊數學:勾股定理的應用之路徑最短值問題和生活實際應用
    最短路徑問題初中階段我們學過三種路徑最值問題,>一是兩點之間線段最短;二是將軍飲馬問題;三是直線外一點與直線上一點的連線中,垂線段最短.>當然,還有很多線段最值問題,待到九年級時會相應擴展的.我們言歸正傳,回到今天所講勾股定理在線段最值問題中的應用,還有實際生活中的應用;螞蟻爬之路徑最短值問題
  • 短小精悍的多源最短路徑算法—Floyd算法
    的,Floyd主要計算多源最短路徑。在單源正權值最短路徑,我們會用Dijkstra算法來求最短路徑,並且算法的思想很簡單——貪心算法:每次確定最短路徑的一個點然後維護(更新)這個點周圍點的距離加入預選隊列,等待下一次的拋出確定。
  • 圖算法的最短路徑,以及背後的技術構建
    上一次,我們使用Neo4j中的示例,重點介紹了尋路和圖搜索算法,重點是單源最短路徑算法。這一次,我們將研究另一個算法,查看All Pairs Shortest Path算法,該算法用於評估高速公路備份或網絡容量等情況下的備用路由。它也是提供多路徑的邏輯路由的關鍵,例如在發生故障時的呼叫路由選擇。
  • 【方法技巧】最短路徑秒殺攻略
    【方法技巧】排列組合——圖形染色【方法技巧】排列組合——錯位排列【方法技巧】小齊瞎預測:今年國考排列組合考「平均分組」【方法技巧】環形排列(預測)最短路徑假如他只能向東或者向北行走,則他上班不同走法共有:A.12種B.15種C.20種D.10種【例2】A、B、C三地的地圖如下圖所示,其中A在C正北,B在C正東,連線處為道路。如要從A地到達B地,且途中只能向南、東和東南方向行進,有多少種不同的走法:
  • 圖的最短路徑算法-Floyd算法-弗洛伊德算法
    Floyd算法又稱為插點法,是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法 在計算機科學中,Floyd-Warshall算法是一種在具有正或負邊緣權重(但沒有負周期)的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度(加權)。
  • 維度空間:平面上兩點間的最短路徑最短,換個角度看,就不一定?
    曾經老師說過:平面上的兩點間的最短路徑是一條直線段。從數學幾何的視角,可以提取三個關鍵詞:平面、兩點、直線段。如果換成一個曲面的兩點間的最短路徑是直線段嗎!推導:通過最短路徑,節省點時間。這是人們在面對一些不好渡過的路徑,常常考慮的一點。能過去就過去,不能過去想辦法湊過去。高級版本在探測天體的歷程中。
  • 最短路徑問題「將軍飲馬」,「造橋選址」,「費馬點」(珍藏版)
    【問題概述】最短路徑問題是圖論研究中的一個經典算法問題, 旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑.算法具體的形式包括:①確定起點的最短路徑問題 - 即已知起始結點,求最短路徑的問題.②確定終點的最短路徑問題 - 與確定起點的問題相反,該問題是已知終結結點,求最短路徑的問題.
  • 螞蟻、蜜蜂和算法
    Marco Dorigo發現,儘管單個螞蟻的智能非常的低級,其智能甚至還不如當今人類設計的最差的機器人,但它們卻能完成相當複雜的任務,比如穿過田野,找到最佳食物,並搬回蟻穴。它們靠的是什麼?顯然不是它們簡答的大腦。
  • 初中生應該知道的數學模型,利用軸對稱解決最短路徑問題
    利用軸對稱解決簡單的最短路徑問題就是其中一個重要的數學模型,按照教學大綱要求,每個初中生都必須掌握。下面就分享這個模型常考的題型及解題思路。在最短路徑模型中,「兩點一線」的最短路徑問題是最基礎的問題。例如:相傳,古希臘亞歷山大裡亞城裡有一位久負盛名的學者,名叫海倫。
  • 數學八(上):用勾股定理求最短路徑長,最全題型整理,建議收藏
    利用勾股定理求最短路徑長度,是八年級數學(上)的一個考試熱點問題,這類題型通常包括平面圖形和立體圖形的最短路徑問題還有通過計算比較最短路徑長度。解決這類題型,可通過幾何變換及勾股定理來求解。巧用勾股定理求最短路徑長,通常有四種題型,接下來我們就一起來看看這部分考試常考的題型:題型一:用計算法求平面中的最短問題題型二:用平移法求平面中的最短問題