海底電纜群島

幫群島鋪海底電纜,讓每座燈塔都亮起來!用最少的錢連起所有島(最小生成樹)、找出最便宜的送電路線,再親手跑一次 Dijkstra 演算法。

開始玩

一款認識「圖論與網路演算法」的解謎遊戲。程式產生的群島上,島與島之間畫著可以鋪的海底電纜虛線,每條標著成本。點一下就鋪上電纜,和發電島接通的島,燈塔會立刻亮起來;鋪好後按「通電!」,電流會沿著電纜流過去。目標是讓每座島都通電,總成本越低越好,也就是電腦科學裡的「最小生成樹」。

電纜繞成一圈時,圈上的電纜會出現白色的流動虛點,提醒你其中一條是多餘的;任務欄即時顯示目前成本、3 星標準、電纜數(N 座島最少要 N-1 條)和通電島數。3 星的標準就是用 Kruskal 演算法算出的最低成本。

共 5 章 30 關:全部通電(生成樹與迴路)、便宜的先選(Kruskal 演算法,成本相同時有多種答案)、舊電纜(已經鋪好、不用錢的電纜,認識切割性質與 Prim 演算法)、最省送電路線(只送電到一座目標島的最短路徑,條數少不一定便宜,最小生成樹上的路也不一定最短),以及 Dijkstra 演算法:每座島寫著暫定距離,你要一步步點出「下一座可以確定的島」,看著鄰居的數字被更新(鬆弛),最後得到最短路徑樹。另有無限張的隨機群島。

怎麼玩

  1. 按「開始鋪電纜」從還沒過的關卡玩起,或從「選關」挑章節。每章第一次進入會出現「工程筆記」,用小圖說明這章的演算法;標題畫面的「工程筆記」可以隨時重看。
  2. 第 1~3 章:點虛線電纜把它鋪上,讓每座島都和有閃電的發電島連起來(燈塔亮起來的就是接通了),再按「通電!」。還有島沒接上時,那些島會搖一搖,不會扣分。第 4 章只要送電到插著旗子的目標島,每條鋪下去的電纜都算錢。
  3. 第 5 章:島上方的框是暫定距離(虛線框,還不知道的是「?」),確定後變成實線框加打勾。點「還沒確定的島裡,暫定數字最小的」那一座;點錯會說明為什麼還不能確定,並記一次「點錯」。
  4. 總成本等於最低成本得 3 顆星,多一點點(最多多 2 或 15%)得 2 顆,再多也能過關得 1 顆;第 5 章沒點錯得 3 顆,點錯 1~2 次得 2 顆。用了提示這關最多 2 顆星。一章過 3 關就會打開下一章。

操作方式

給家長

最後更新:

你可能也喜歡