第7章 Floyd-dijkstra路徑
關燈
小
中
大
林知夏說完,拉起江逾白往前跑。
被A組和B組設定為基地的城堡和堡壘都位於高處,縱橫交錯的隧道大多數位於低處。
在聶天清的幹擾下,泡泡球滾進不同的隧道。聶天清穿梭在隧道裏,毫無顧忌,四處踢球。
林知夏縱觀全局,總結道:“如果我們把這場游戲看成一個圖論問題,隧道的每一個節點就是圖的頂點。我們一共有三十七個頂點。這張圖已經印在了我的腦子裏。有些隧道是透明的,有些隧道不是,這裏又涉及到了部分可觀察的馬爾可夫決策……”
“林知夏!”江逾白大義凜然地說,“你不用跟我解釋!我相信你!”
林知夏把他拽進一條隧道:“你是因為聽不懂,所以不想聽嗎?那你只能跟著我,一直聽我的指揮。”
為了整個小組的勝利,江逾白原諒了林知夏的挑釁。
他們跑向隧道的節點,很快就撿了七個球。
四處奔波的路上,林知夏撞見了本組的董孫奇。董孫奇高喊:“你們跟我來,這裏有一條最短的路!走最短的路,才能更快回去!”
“不!”林知夏卻說,“總是選擇最短路徑,不一定是全局最優解!”
董孫奇大驚失色:“我靠!你在講什麽東西!”
林知夏回應道:“你想一想三角形的三條邊!a邊和b邊都比c邊短,它們的和一定會超過c的邊長,這麽簡單的道理!為什麽放進圖論裏,你就不懂了呢!”
董孫奇虎軀一震:“好像有點道理!你話多,聽你的!”
於是,董孫奇和江逾白都成為了林知夏的跟班。
短短幾分鐘之內,他們收集到了十二個泡泡球。然而,天有不測風雲,敵方小組的三個人直奔他們而來。
丁巖一邊狂奔,一邊嚷嚷道:“甘姝麗,聶天清!我們走,快去打劫江逾白!他們有好多球!他們好會撿!我們不用自己撿球,我們就跟著他們,專門打劫!”
江逾白絲毫不慌亂。他從容不迫地站在原地,冷靜地看著林知夏:“你肯定有辦法。”
林知夏眼波一轉,竟然說:“我沒辦法,我們快跑!救命,救命!快跑呀!”
“什麽?”江逾白倉皇失措,匆忙跟著林知夏一路逃命。
林知夏又笑又跳,馬尾辮都散開了。她和江逾白、董孫奇相繼坐上滑梯,沖進蹦床。
林知夏抱著四個球跑在最前方,身影飛快一閃,消失在錯綜覆雜的隧道裏。
江逾白和董孫奇都很茫然,就像是二戰時期失去了馬奇諾防線的法國軍隊。即便他們仍然保留著機動兵力,卻不知道如何才能繼續打仗了。
“你們走藍色隧道!然後走紅色隧道!”林知夏的聲音從高處傳來,“你們快把泡泡球放進我們組的中心區域!”
江逾白立刻問:“你要去哪裏?”
林知夏說:“我要去找他們B組的人。”
“不!”江逾白阻攔道,“林知夏,你別走!”
林知夏與他訣別:“我這一走!不知道還能不能回來!”
江逾白一腳踩上藍色隧道的入口:“你在哪裏?我去救你!”
林知夏去意已決:“不用了,我不能做縮頭烏龜!你們留在家裏,好好保護泡泡球,保護好每一個泡泡球!那是我們勝利的最後希望!”
董孫奇也痛心疾首:“林知夏,你快走吧!我們會一直記得你!”
“你說什麽?”江逾白開始批評董孫奇,“我們是一個小組,怎麽能拋棄同伴?你心裏沒有想守護的東西嗎?”
董孫奇斬釘截鐵地回答:“有!我想守護泡泡球!林知夏讓我們保護泡泡球,你快去我們A組的中心區域!”
他們二人直奔A組基地的中心區。
懸空隧道內,聶天清突然說:“有腳步聲,林知夏來了。”
聶天清小組的三個人都沒跑。他們站定不動,商量著對策。
丁巖透露道:“林知夏在我們班的綽號是怪胎。她好聰明,你們要小心。”
“她才九歲,”聶天清說,“再聰明能聰明到哪兒去。”
丁巖臉色微變:“她背書只要三秒鐘!”
聶天清不信。
丁巖憤怒道:“真的!我騙你是小狗!”
甘姝麗也說:“真的,她好聰明。”
“你們不要長他人志氣,滅自己威風,”聶天清像一位哥哥一樣教育他們,“對手沒有那麽可怕。我們有三個人,對她出石頭剪刀布,難道贏不過她嗎?我們每一個人的獲勝概率都是百分之五十!”
“有道理!”應話的人,是林知夏。
林知夏順著聶天清的意思,對他們說:“百分之五十的三次方等於0.125,我的獲勝概率只有0.125。”
聶天清問:“為什麽是0.125?”
林知夏歪頭:“我必須贏過你們每一個人。第一次獲勝概率是0.5,第二次0.25,第三次0.125……這不是你說的嗎?你假設兩兩對戰的獲勝概率都是0.5……”
聶天清皺著眉毛:“但是,林知夏,你和我們玩石刀剪刀布,只要你輸了一次,你就不能再繼續。為什麽你還用0.5的冪次方來算概率?”
“你這樣想呀,”林知夏耐心地解釋,“我和你們三個人玩,一共會出現四種結果。第一種結果,我第一局就輸,這個概率是0.5。第二種結果,我第二局輸,概率是0.25。第三種結果,我第三局輸,概率是0.125,第四種結果,我第三局贏,概率也是0.125。這幾個概率事件之和,正好等於1,你算一算?我能進入第二局和第三局的前提條件都是,我上一局就贏了。不過,你要知道,上一局的獲勝,並不是最終狀態。”
聶天清恍然大悟,右手成拳,錘進左手的掌心:“我想通了。”
他扭頭看著兩位同伴:“高興嗎!我們有0.875的概率能贏!”
丁巖有些顫抖:“聶天清,她講了這麽多,你還覺得你自己能贏?她肯定是騙你玩的。我不信。”
聶天清繞開了丁巖。他走向林知夏,充滿戰意地說:“開始吧,林知夏,石刀剪刀布。”
林知夏開心應好。
隨後,他們二人同時出招——聶天清出了石頭,林知夏出了布。
聶天清心中一驚,原地定格。
林知夏雙手拍掌,跳到丁巖面前。
丁巖的內心恐懼極了。他硬著頭皮,亮出剪刀,林知夏則是石頭。丁巖一臉“我早就知道”的表情,也開始倒數三分鐘的冰凍秒數。
丁巖小組的人,只剩下一個甘姝麗。
全組的希望,都寄托在了甘姝麗的身上。
甘姝麗口齒不清道:“我……剪刀石頭……”
“甘姝麗,”林知夏拍了拍她的肩膀,“你不要緊張。”
隧道節點是一個封閉的空間。左右兩側各貼著一扇玻璃窗,頂端開著排氣孔,甘姝麗向外一望,能望見蹦床、滑索、吊燈。她把心一橫,直面林知夏:“林知夏!石頭剪刀布!”
話音落後,她張開五指,做成“布”形。
而林知夏的出招,好像比甘姝麗更早。她早在甘姝麗反應過來之前,就已經比了個剪刀手。
甘姝麗滿臉驚訝:“你……又贏了。”
林知夏笑著說:“哎呀,全靠運氣啦。”
林知夏心裏想的卻是——全靠運氣讓她天生和大家不一樣。通過各種細節觀察,她才能預測到每一位同學的行為。
甘姝麗為她鼓掌:“運氣真好。”
“我說過了吧!”丁巖警告聶天清,“我早就知道!我們贏不了她!”
聶天清翻起舊賬:“你早就知道,為什麽還帶著我們來搶劫林知夏這一組?”
丁巖被堵得啞口無言。他只是看不慣江逾白跟著林知夏輕松撿球的快樂樣子。短短幾分鐘,撿了一堆球!為什麽啊!為什麽江逾白就不用動腦子!他也不想動腦子啊!
可憐他們小組三個人,全被冰凍在原地。
林知夏早就跑遠了。
返回基地的路上,林知夏還在撿球。她太開心了,長發松散,披在肩上,像個小瘋子。但她完全不在意。她撿到四個球,沖進一條隧道,正好和江逾白撞了個滿懷。
林知夏當場摔倒。
江逾白跪在地上,雙手扶她。
她悵然道:“四個泡泡球都滾走了,快去撿呀……”
江逾白只問她:“對不起,我撞傷你了嗎?我家裏有醫生。”
林知夏搖頭:“沒有。”隨後又問:“你為什麽要和我說對不起?我也撞到你了。你也不是故意的呀。力的作用是相互的。”
一只紅色發繩掛在林知夏的發尾。江逾白輕輕摘下她的發繩:“你把頭發紮起來。在隧道裏,頭發不能擋住眼睛,你必須看清路線。”
林知夏已經撿起了三個泡泡球。她坐在地上,背對著江逾白:“你幫我紮頭發!快點!”
江逾白一怔:“我……我不會紮頭發。”
林知夏立刻把泡泡球扔進他的懷裏,又從他手中搶走那只紅色發繩。她一邊紮起自己的長發,一邊念念有詞:“紮頭發很簡單的。”
江逾白說:“我沒學過。”
林知夏告訴他:“有很多東西,簡單到不用學,只需要看一眼,就可以掌握了。”
遠處的董孫奇發出一陣驚天動地的怒吼:“江逾白!林知夏!你們在哪裏!”
“快走!”林知夏拽起江逾白,“我們繼續撿球!”
江逾白問她:“你還在用最短路徑算法嗎?”
林知夏回頭看他一眼,帶著他向前飛奔:“當然!我的腦子裏有一個Floyd算法矩陣!所有隧道節點都是圖的頂點,矩陣行不通的時候,我就建一棵Dijkstra樹,這棵樹也長在我的腦子裏。其實說白了就是貪心、窮舉和剪枝算法融合,像是紮頭發一樣簡單,不需要思考,看一眼就會了!我帶你走最快的路!我們一起回家!”
江逾白不由自主地佩服她。聽見她說“我帶你走最快的路,我們一起回家”,江逾白非常高興,這一次他們A組一定能贏!
隧道內的道路崎嶇,江逾白和林知夏各自懷揣著四個球。江逾白窺視著敵方的動靜,奇怪道:“他們不追我們了。”
林知夏哈哈大笑:“他們馬上會去我們A組的基地中心,打劫董孫奇。我們要趕在他們偷襲前,盡快跑回A組基地的中心區域!”
“什麽!”江逾白指責道,“他們很陰險!”
林知夏安慰他:“別怕!我會保護你!”
她跳上一條管道。
江逾白把自己懷中的四個球全部放進管道。然後,他單手握住吊環,站在滑索軌道的起點,轉過頭對林知夏說:“你先回基地!我看見蹦床上有兩只球!”
林知夏叮囑他:“小心,快去快回!”
江逾白像一陣風,飛向了地面。他縱身一躍,降落在蹦床上,步法十分穩健。他的落地姿勢也很有技巧,借由原地一個翻滾減輕了緩沖,蹦床甚至沒有上下晃動。
他撿起寶貴的泡泡球,擡頭眺望城堡上的林知夏。
林知夏站在城堡的窗戶邊,伸出一只手,朝他揮了揮。
江逾白記起自己看過的童話書——公主總是站在城堡上,等待王子屠盡惡魔,等待王子來解救她。
而他眼前那位公主不一樣。
眼前那位公主,比他更像是披荊斬棘的王子。
童話書裏的故事寫得不對。據他親眼所見,公主也能所向披靡、乘風破浪。
本站無廣告,永久域名(danmei.twking.cc)
被A組和B組設定為基地的城堡和堡壘都位於高處,縱橫交錯的隧道大多數位於低處。
在聶天清的幹擾下,泡泡球滾進不同的隧道。聶天清穿梭在隧道裏,毫無顧忌,四處踢球。
林知夏縱觀全局,總結道:“如果我們把這場游戲看成一個圖論問題,隧道的每一個節點就是圖的頂點。我們一共有三十七個頂點。這張圖已經印在了我的腦子裏。有些隧道是透明的,有些隧道不是,這裏又涉及到了部分可觀察的馬爾可夫決策……”
“林知夏!”江逾白大義凜然地說,“你不用跟我解釋!我相信你!”
林知夏把他拽進一條隧道:“你是因為聽不懂,所以不想聽嗎?那你只能跟著我,一直聽我的指揮。”
為了整個小組的勝利,江逾白原諒了林知夏的挑釁。
他們跑向隧道的節點,很快就撿了七個球。
四處奔波的路上,林知夏撞見了本組的董孫奇。董孫奇高喊:“你們跟我來,這裏有一條最短的路!走最短的路,才能更快回去!”
“不!”林知夏卻說,“總是選擇最短路徑,不一定是全局最優解!”
董孫奇大驚失色:“我靠!你在講什麽東西!”
林知夏回應道:“你想一想三角形的三條邊!a邊和b邊都比c邊短,它們的和一定會超過c的邊長,這麽簡單的道理!為什麽放進圖論裏,你就不懂了呢!”
董孫奇虎軀一震:“好像有點道理!你話多,聽你的!”
於是,董孫奇和江逾白都成為了林知夏的跟班。
短短幾分鐘之內,他們收集到了十二個泡泡球。然而,天有不測風雲,敵方小組的三個人直奔他們而來。
丁巖一邊狂奔,一邊嚷嚷道:“甘姝麗,聶天清!我們走,快去打劫江逾白!他們有好多球!他們好會撿!我們不用自己撿球,我們就跟著他們,專門打劫!”
江逾白絲毫不慌亂。他從容不迫地站在原地,冷靜地看著林知夏:“你肯定有辦法。”
林知夏眼波一轉,竟然說:“我沒辦法,我們快跑!救命,救命!快跑呀!”
“什麽?”江逾白倉皇失措,匆忙跟著林知夏一路逃命。
林知夏又笑又跳,馬尾辮都散開了。她和江逾白、董孫奇相繼坐上滑梯,沖進蹦床。
林知夏抱著四個球跑在最前方,身影飛快一閃,消失在錯綜覆雜的隧道裏。
江逾白和董孫奇都很茫然,就像是二戰時期失去了馬奇諾防線的法國軍隊。即便他們仍然保留著機動兵力,卻不知道如何才能繼續打仗了。
“你們走藍色隧道!然後走紅色隧道!”林知夏的聲音從高處傳來,“你們快把泡泡球放進我們組的中心區域!”
江逾白立刻問:“你要去哪裏?”
林知夏說:“我要去找他們B組的人。”
“不!”江逾白阻攔道,“林知夏,你別走!”
林知夏與他訣別:“我這一走!不知道還能不能回來!”
江逾白一腳踩上藍色隧道的入口:“你在哪裏?我去救你!”
林知夏去意已決:“不用了,我不能做縮頭烏龜!你們留在家裏,好好保護泡泡球,保護好每一個泡泡球!那是我們勝利的最後希望!”
董孫奇也痛心疾首:“林知夏,你快走吧!我們會一直記得你!”
“你說什麽?”江逾白開始批評董孫奇,“我們是一個小組,怎麽能拋棄同伴?你心裏沒有想守護的東西嗎?”
董孫奇斬釘截鐵地回答:“有!我想守護泡泡球!林知夏讓我們保護泡泡球,你快去我們A組的中心區域!”
他們二人直奔A組基地的中心區。
懸空隧道內,聶天清突然說:“有腳步聲,林知夏來了。”
聶天清小組的三個人都沒跑。他們站定不動,商量著對策。
丁巖透露道:“林知夏在我們班的綽號是怪胎。她好聰明,你們要小心。”
“她才九歲,”聶天清說,“再聰明能聰明到哪兒去。”
丁巖臉色微變:“她背書只要三秒鐘!”
聶天清不信。
丁巖憤怒道:“真的!我騙你是小狗!”
甘姝麗也說:“真的,她好聰明。”
“你們不要長他人志氣,滅自己威風,”聶天清像一位哥哥一樣教育他們,“對手沒有那麽可怕。我們有三個人,對她出石頭剪刀布,難道贏不過她嗎?我們每一個人的獲勝概率都是百分之五十!”
“有道理!”應話的人,是林知夏。
林知夏順著聶天清的意思,對他們說:“百分之五十的三次方等於0.125,我的獲勝概率只有0.125。”
聶天清問:“為什麽是0.125?”
林知夏歪頭:“我必須贏過你們每一個人。第一次獲勝概率是0.5,第二次0.25,第三次0.125……這不是你說的嗎?你假設兩兩對戰的獲勝概率都是0.5……”
聶天清皺著眉毛:“但是,林知夏,你和我們玩石刀剪刀布,只要你輸了一次,你就不能再繼續。為什麽你還用0.5的冪次方來算概率?”
“你這樣想呀,”林知夏耐心地解釋,“我和你們三個人玩,一共會出現四種結果。第一種結果,我第一局就輸,這個概率是0.5。第二種結果,我第二局輸,概率是0.25。第三種結果,我第三局輸,概率是0.125,第四種結果,我第三局贏,概率也是0.125。這幾個概率事件之和,正好等於1,你算一算?我能進入第二局和第三局的前提條件都是,我上一局就贏了。不過,你要知道,上一局的獲勝,並不是最終狀態。”
聶天清恍然大悟,右手成拳,錘進左手的掌心:“我想通了。”
他扭頭看著兩位同伴:“高興嗎!我們有0.875的概率能贏!”
丁巖有些顫抖:“聶天清,她講了這麽多,你還覺得你自己能贏?她肯定是騙你玩的。我不信。”
聶天清繞開了丁巖。他走向林知夏,充滿戰意地說:“開始吧,林知夏,石刀剪刀布。”
林知夏開心應好。
隨後,他們二人同時出招——聶天清出了石頭,林知夏出了布。
聶天清心中一驚,原地定格。
林知夏雙手拍掌,跳到丁巖面前。
丁巖的內心恐懼極了。他硬著頭皮,亮出剪刀,林知夏則是石頭。丁巖一臉“我早就知道”的表情,也開始倒數三分鐘的冰凍秒數。
丁巖小組的人,只剩下一個甘姝麗。
全組的希望,都寄托在了甘姝麗的身上。
甘姝麗口齒不清道:“我……剪刀石頭……”
“甘姝麗,”林知夏拍了拍她的肩膀,“你不要緊張。”
隧道節點是一個封閉的空間。左右兩側各貼著一扇玻璃窗,頂端開著排氣孔,甘姝麗向外一望,能望見蹦床、滑索、吊燈。她把心一橫,直面林知夏:“林知夏!石頭剪刀布!”
話音落後,她張開五指,做成“布”形。
而林知夏的出招,好像比甘姝麗更早。她早在甘姝麗反應過來之前,就已經比了個剪刀手。
甘姝麗滿臉驚訝:“你……又贏了。”
林知夏笑著說:“哎呀,全靠運氣啦。”
林知夏心裏想的卻是——全靠運氣讓她天生和大家不一樣。通過各種細節觀察,她才能預測到每一位同學的行為。
甘姝麗為她鼓掌:“運氣真好。”
“我說過了吧!”丁巖警告聶天清,“我早就知道!我們贏不了她!”
聶天清翻起舊賬:“你早就知道,為什麽還帶著我們來搶劫林知夏這一組?”
丁巖被堵得啞口無言。他只是看不慣江逾白跟著林知夏輕松撿球的快樂樣子。短短幾分鐘,撿了一堆球!為什麽啊!為什麽江逾白就不用動腦子!他也不想動腦子啊!
可憐他們小組三個人,全被冰凍在原地。
林知夏早就跑遠了。
返回基地的路上,林知夏還在撿球。她太開心了,長發松散,披在肩上,像個小瘋子。但她完全不在意。她撿到四個球,沖進一條隧道,正好和江逾白撞了個滿懷。
林知夏當場摔倒。
江逾白跪在地上,雙手扶她。
她悵然道:“四個泡泡球都滾走了,快去撿呀……”
江逾白只問她:“對不起,我撞傷你了嗎?我家裏有醫生。”
林知夏搖頭:“沒有。”隨後又問:“你為什麽要和我說對不起?我也撞到你了。你也不是故意的呀。力的作用是相互的。”
一只紅色發繩掛在林知夏的發尾。江逾白輕輕摘下她的發繩:“你把頭發紮起來。在隧道裏,頭發不能擋住眼睛,你必須看清路線。”
林知夏已經撿起了三個泡泡球。她坐在地上,背對著江逾白:“你幫我紮頭發!快點!”
江逾白一怔:“我……我不會紮頭發。”
林知夏立刻把泡泡球扔進他的懷裏,又從他手中搶走那只紅色發繩。她一邊紮起自己的長發,一邊念念有詞:“紮頭發很簡單的。”
江逾白說:“我沒學過。”
林知夏告訴他:“有很多東西,簡單到不用學,只需要看一眼,就可以掌握了。”
遠處的董孫奇發出一陣驚天動地的怒吼:“江逾白!林知夏!你們在哪裏!”
“快走!”林知夏拽起江逾白,“我們繼續撿球!”
江逾白問她:“你還在用最短路徑算法嗎?”
林知夏回頭看他一眼,帶著他向前飛奔:“當然!我的腦子裏有一個Floyd算法矩陣!所有隧道節點都是圖的頂點,矩陣行不通的時候,我就建一棵Dijkstra樹,這棵樹也長在我的腦子裏。其實說白了就是貪心、窮舉和剪枝算法融合,像是紮頭發一樣簡單,不需要思考,看一眼就會了!我帶你走最快的路!我們一起回家!”
江逾白不由自主地佩服她。聽見她說“我帶你走最快的路,我們一起回家”,江逾白非常高興,這一次他們A組一定能贏!
隧道內的道路崎嶇,江逾白和林知夏各自懷揣著四個球。江逾白窺視著敵方的動靜,奇怪道:“他們不追我們了。”
林知夏哈哈大笑:“他們馬上會去我們A組的基地中心,打劫董孫奇。我們要趕在他們偷襲前,盡快跑回A組基地的中心區域!”
“什麽!”江逾白指責道,“他們很陰險!”
林知夏安慰他:“別怕!我會保護你!”
她跳上一條管道。
江逾白把自己懷中的四個球全部放進管道。然後,他單手握住吊環,站在滑索軌道的起點,轉過頭對林知夏說:“你先回基地!我看見蹦床上有兩只球!”
林知夏叮囑他:“小心,快去快回!”
江逾白像一陣風,飛向了地面。他縱身一躍,降落在蹦床上,步法十分穩健。他的落地姿勢也很有技巧,借由原地一個翻滾減輕了緩沖,蹦床甚至沒有上下晃動。
他撿起寶貴的泡泡球,擡頭眺望城堡上的林知夏。
林知夏站在城堡的窗戶邊,伸出一只手,朝他揮了揮。
江逾白記起自己看過的童話書——公主總是站在城堡上,等待王子屠盡惡魔,等待王子來解救她。
而他眼前那位公主不一樣。
眼前那位公主,比他更像是披荊斬棘的王子。
童話書裏的故事寫得不對。據他親眼所見,公主也能所向披靡、乘風破浪。
本站無廣告,永久域名(danmei.twking.cc)