■ Ekillion とは

 JR では、東京・大阪・新潟・福岡の4地域で「大都市近郊区間」を設定しています。
 大都市近郊区間内では、ある駅からある駅までの運賃は、実際に乗車した経路に関わらず
 その最短距離で計算するというルールがあります(ただし、同じ駅を二度通ってはいけません)。
 このルールを利用し、わざと遠回りをして電車旅を楽しむのが大都市近郊区間大回り」です。

 Ekillion(エキリオン)は、どこから乗るか(始点駅)・どこで降りるか(終点駅)を
 選択すると、大都市近郊区間内を通るすべての経路を超高速に計算し、表示します。
 「なるべく多くの駅を経由する経路」「○○駅を経由する経路」など、条件を指定して
 結果を表示させることができます。

  東京駅から隣の神田駅まで行くには、何通りの経路があるでしょうか?
  また、その中でもっとも距離の長い経路は、何キロになるでしょうか?

 すぐにでも Ekillion を試してみたい! という方は、こちらからどうぞ。 → Ekillion
 このページの下にある「Ekillion の使いかた」もあわせてご覧ください。

 Ekillion の特徴は、単に最長の経路1つのみを探索するのではなく、指定した条件に沿う
 すべての経路を求めている点にあります。条件によっては数百万通りもの経路が存在する
 こともありますが、Ekillion はそのすべてを短時間で求めることができます。

 このように複雑な経路探索を高速にやってのけるのが、JST ERATO 湊離散構造処理系プロジェクト
 で開発された Graphillion というソフトウェアです。普通に計算するとスーパーコンピュータ
 数年、数十年とかかる問題も、高度なアルゴリズムを利用することによって
 数秒、数十秒といった時間で解くことができるのです。(しかも、普通のパソコンで!)
 Ekillion という名前は、この Graphillion に由来しています。

 Graphillion に興味のある方は、こちらのサイトをご覧ください。 → graphillion.org(英語)

 Graphillion を使わずにこの問題を解こうとするとどうなるのか? を知りたい方は…


■ Ekillion の使いかた


  ① 近郊区間のエリアを選ぶ 
  ② 始点駅、終点駅を選ぶ
  ③ 結果をなに順で表示するかを選ぶ (通過駅数、営業距離などが選べます)
  ④ ルートに含めたい駅、含めたくない駅があれば選ぶ
  ⑤ 「go!」 ボタンを押すと、条件を満たすルートが表示されます


 ⑥「順位付け」で指定された順でルート一覧が表示されます(「表示件数」で指定された上位件数が表示されます)

 ⑦ ルート一覧より参照したいルートをクリックするとルート内容が表示されます(検索直後は最上位ルートの内容が表示されています)

 ⑧ ルート内容で表示されている駅をクリックすると対象駅の情報が表示されます(ルート選択直後は始点駅の情報が表示されています)

 ⑨ 選択中のルートと駅が地図上に図示されます


■ Ekillion で使用しているデータ

 Ekillion では、駅データ.jp の提供する駅情報・路線情報を使用しています。

■ サンプルコードおよびデータセットのダウンロード

 Ekillion で用いているアルゴリズムやデータ構造について、
 『グラフ列挙アルゴリズムの最先端 -「フカシギの数え方」から広がる世界-』(森北出版)
 にて解説させていただきました。
 興味のある方は、以下の ekillion_book.zip をダウンロードし、サンプルコードおよびデータセット
 (いずれも UTF-8 形式のテキストファイル)を展開のうえ Ekillion をお試しください。
 なお使い方など詳しくは、同書をご覧ください。

ċ
ekillion_book.zip
(126k)
nysol info,
2014/11/18 3:54