海底ケーブル諸島

海底ケーブルをしいて、すべての灯台に明かりを!いちばん安く島をつなぎ(最小全域木)、いちばん安い送電ルートを見つけ、ダイクストラ法を自分の手で動かそう。

あそぶ

「グラフ理論とネットワークのアルゴリズム」を知るパズルゲームです。プログラムがつくる島々の間に、しける海底ケーブルが点線でかかれ、それぞれにコストがついています。タップでケーブルをしくと、発電島とつながった島の灯台がすぐに光ります。しき終わったら「送電!」で、電気がケーブルを流れていきます。目標はすべての島に電気を送り、合計コストをできるだけ安くすること。コンピューター科学でいう「最小全域木」です。

ケーブルが輪になると、輪の上に白い点が流れて、どれか 1 本がむだだと教えてくれます。上の欄には今のコスト、星 3 の基準、ケーブルの本数(島が N 個なら少なくとも N-1 本)、点灯した島の数がその場で出ます。星 3 の基準は、クラスカル法で求めたいちばん安いコストです。

全 5 章 30 ステージ:ぜんぶに電気を(全域木と閉路)、安いものから(クラスカル法、同じコストなら答えはいくつも)、古いケーブル(もうしいてある無料のケーブル、カットの性質とプリム法)、いちばん安いルート(目的の島 1 つだけに送る最短経路。本数が少ないほど安いとはかぎらず、最小全域木の上の道も最短とはかぎらない)、そしてダイクストラ法:島ごとに仮の距離が書かれ、次に確定できる島を自分でタップして、となりの数字が小さくなる(緩和)のを見ながら最短経路木を完成させます。さらに、無限に遊べるランダムな島もあります。

あそびかた

  1. 「ケーブルをしく」でまだクリアしていないステージから、または「ステージ」から章を選びます。新しい章にはじめて入ると「技師のメモ」が小さな図でその章のアルゴリズムを説明します。タイトル画面の「技師のメモ」でいつでも読み返せます。
  2. 第 1~3 章:点線のケーブルをタップしてしき、すべての島をいなずまの発電島とつなぎます(灯台が光ればつながっています)。できたら「送電!」。まだつながっていない島があると、その島がゆれるだけで、減点はありません。第 4 章では旗の立った目的の島だけに電気を送り、しいたケーブルはすべてお金がかかります。
  3. 第 5 章:島の上のわくは仮の距離です(点線のわく。まだわからなければ「?」)。確定すると実線のわくにチェックがつきます。まだ確定していない島のうち、数字がいちばん小さい島をタップしよう。まちがえると、なぜまだ確定できないかを説明し、「ミス」を 1 回数えます。
  4. 合計コストが最安なら星 3 つ、少し高い(2 か 15% まで)なら 2 つ、それ以上でもクリアで 1 つ。第 5 章はミスなしで 3 つ、ミス 1~2 回で 2 つ。ヒントを使うとそのステージは最大で星 2 つです。1 つの章で 3 ステージクリアすると次の章が開きます。

そうさ方法

保護者の方へ

最終更新:

こちらもおすすめ