学生証番号，氏名，説明を含んだファイル(pdfファイル, テキストファイル， WORDファイルなど) を作成して，cfiveの課題提出機能を使って提出すること． 提出期限はWWWページで指定する．
＿＿地下鉄路線図のデータモデル＿＿ ＜必要な情報＞ ・発駅〜着駅間の最短距離 ・発駅〜着駅間の時間 ・運賃料金 ＜データモデルの概要＞ 地下鉄路線のデータモデルを考えるとき最も必要なのは、 発駅〜着駅間の経路を調べることである。それができれば 簡単に距離や時間を算出できるからである。 経路を求める方法は色々あるだろうが、 以下の方法で考える。 ・駅間の線路に”時間”、”距離”をもつ構造体を作る。 ・それぞれの路線に、隣り合う路線の配列を持たせる。 ・発駅〜着駅の経路を求めるとき、まずは路線で考えてから、 その後駅間で考える。 例えば、「京王井の頭線の駒場東大前駅〜西武新宿線の田無駅」 を求めるとき、京王井の頭線と隣り合う路線を調べ、さらにその路線と隣り合う 路線を調べ………というようなことをして、西武新宿線が見つかるまで調べる。 このとき候補をいくつか挙げておく。 その後、それらの経路での駅間の距離や時間を足していき、総合距離や移動時間を 算出する。そして、最短経路などを求める。 このようなデータモデルを作りたい。 ＜データモデルの構造＞ ・駅間の線路 Med_Stations = Struct.new(:med_number, :line_number, :distance, :time) //med_number:線路のその路線での識別番号 //line_number:路線番号 //distance:その線路の距離 //time:その線路をわたるのにかかる時間 ・駅 Station = Struct.new(:station_number, :name, :line_number, :array_stations, :array_lines) //station_number:駅のその路線での識別番号 //name:駅の名前 //line_number:路線番号 //array_stations:隣り合う駅 //array_lines:その駅で乗り換え可能な路線 ・路線 Line = Struct.new(:line_number, :name, :array_stations, :array_lines) //line_number:路線の識別番号 //name:路線の名前 //array_stations:路線に含まれる駅 //array_lines:隣り合う路線 ・経路 Process = Struct.new(:array_line_numbers, :sum_distance, :sum_time) //array_line_numbers:経路中の路線の番号 //sum_distance:距離 //sum_time:時間 ~~~経路の求め方~~~ start_station end_station //発駅と着駅を尋ねる。 Processes = Array.new(20) //２０個ほど空の候補を作っておく。 //着駅の路線に当たるまで、発駅の路線の隣の隣の………という感じで1０個ほど候補を作る。 このとき途中に通った路線の識別番号をProcessesに入力していく。 //Processのarray_line_numbersから路線を求めて、それぞれのProcessで、駅から次ぎに行くべき路線へ 乗換できる駅間の時間や距離をそのProcessに足していく。このとき、路線に複数の乗換駅があった場合 はProcessesの余った部分に入れていく。Hashを使った方がいいかもしれない。 //その後、Processの候補から最短経路などをもとめて出力する。 最後に、このプログラムでは、例えば「東京〜福岡」を調べた場合、計算時間がかなりかかったり、候補数が足りなくなったりする 場合があるので、ある県から他の県へ移るなど長い距離の経路を求める場合を想定して、県〜県をつなぐ候補をあらかじめ作っておいて、それぞれの県内を分けて考えたあと、その二つの県での時間とあいだをつなぐ経路の時間を足して、算出すると、計算時間が短くなると思う。また電車以外の交通手段を考えるときは、その交通手段を電車と考えて、このプログラムに応用すればできると思う。
地下鉄路線図のデータモデル
**************************************************
目次
１．データモデルと説明
２．データの入力例
３．想定するアプリケーション
**************************************************
++++++++++++++++++++++++++++++
１．データモデルと説明
++++++++++++++++++++++++++++++
まず早速、以下がデータの雛形を表すRubyのソースです。
#-------------------
# Lineクラス（路線を表し、路線名・駅の配列・乗換候補の配列を持つ）
class Line
attr_accessor :name, :stations, :exchanges
def initialize(*x)
@name, @stations, @exchanges = x
end
end
# LineExchangeクラス（ある路線全体に対する乗換候補を表し、
# 乗換駅のインデックス・乗換先路線への参照・乗換先路線での乗換駅のインデックスを持つ）
class LineExchange
attr_accessor :index, :dstLine, :dstIndex
def initialize(*x)
@index, @dstLine, @dstIndex = x
end
end
# Stationクラス（駅を表し、駅名・路線への参照・次の駅までの距離・乗換候補の配列を持つ）
class Station
attr_accessor :name, :line, :upD, :exchanges
def initialize(*x)
@name, @line, @upD, @exchanges = x
end
end
# Exchangeクラス（ある駅における乗換候補を表し、
# 乗り換え先路線への参照・その路線における同駅のインデックス・乗換所要時間を持つ）
class Exchange
attr_accessor :dstLine, :dstStationIndex, :exchangeTime
def initialize(*x)
@dstLine, @dstStationIndex, @exchangeTime = x
end
end
#------------------
データモデルの説明をします。
まず、一つの路線に一つのLineクラスインスタンスが対応します。
各路線はそれぞれ駅（Stationクラスインスタンス）の配列を持ちます（@stations）。
乗換駅に関しては、一つの駅に対して複数のStationクラスインスタンスが割り当てられ、各々が各路線でのその駅となります。
つまり、例えばＡ駅がＰ線とＱ線の乗換駅だとしたら、Ｐ線のＡ駅とＱ線のＡ駅はデータ上は別の駅です。また、駅によっては、駅名が違っても乗換駅関係として扱うことがあります。
各路線上の駅には、その路線におけるインデックスが割り当てられています。これは、路線が持つ駅の配列におけるインデックスと同じものです。また、
一つの路線に対して、乗換候補の配列（@exchanges、LineExchangeクラスインスタンスの配列）が与えられます。
これは、その路線上の駅から乗り換えられる乗換候補の一覧です。
各乗換候補は、その路線における乗換駅のインデックス、乗換先路線への参照、乗換先路線における乗換駅のインデックスを持ちます。
乗換駅には、乗換候補の配列（@exchanges、Exchangeクラスインスタンスの配列）が与えられます。
どの路線からどの路線への乗換かによって、乗換の所要時間などが異なるので、同じ駅でも路線が違えば別々の乗換候補配列を持ちます。
また、乗換候補の配列は、基本的に乗換所要時間の昇順に並べられます。
各駅のデータとして、Stationクラスのインスタンスは駅名、路線への参照（Lineクラスインスタンスの参照）、インデックスの大きい側の隣駅までの距離、乗換候補配列を持ちます。乗換駅でない場合、乗換候補配列はnilとなります。また、東京メトロや都営地下鉄など、路線ごとに駅に駅番号が振られるものは、駅番号－１がインデックスとなります。
########################################
++++++++++++++++++++++++++++++
２．データの入力例
++++++++++++++++++++++++++++++
例えば以下のようにして入力します。以下は半蔵門線の例です。
隣駅までの距離、乗換所要時間、の２データは実際の値ではなく、適当に入力しています。実際にはちゃんと正確な値を入力します。距離、時間ともに単位は分です（距離というより移動時間といったほうがいいかもしれません）
#------------------
# 半蔵門線の場合
# 半蔵門線の駅配列、乗換候補配列、路線データ本体
hanzomon = Line.new("半蔵門線", [], [])
# とりあえず半蔵門線だけでも動くように、他の路線も仮に定義しておく
ginza = Line.new("銀座線", [], [])
chiyoda = Line.new("千代田線", [], [])
ooedo = Line.new("大江戸線", [], [])
yurakucho = Line.new("有楽町線", [], [])
nanboku = Line.new("南北線", [], [])
marunouchi = Line.new("丸ノ内線", [], [])
tozai = Line.new("東西線", [], [])
shinjuku = Line.new("新宿線", [], [])
mita = Line.new("三田線", [], [])
asakusa = Line.new("浅草線", [], [])
# 半蔵門線の各駅
# 同じ部分をメソッド化（半蔵門線以外にも使えるメソッド）
def setStations(line, stations)
stations.each do |station|
line.stations << Station.new(station[0], line, station[1], station[2])
end
end
setStations(hanzomon, [
["渋谷", 1, [
Exchange.new(ginza, 0, 3)
]],
["表参道", 1, [
Exchange.new(ginza, 1, 0),
Exchange.new(chiyoda, 3, 2)
]],
["青山一丁目", 2, [
Exchange.new(ginza, 3, 1),
Exchange.new(ooedo, 23, 3)
]],
["永田町", 1, [
Exchange.new(yurakucho, 15, 3),
Exchange.new(ginza, 4, 3),
Exchange.new(marunouchi, 12, 3),
Exchange.new(nanboku, 6, 4)
]],
["半蔵門", 1, nil],
["九段下", 2, [
Exchange.new(tozai, 6, 2),
Exchange.new(shinjuku, 4, 2)
]],
["神保町", 1, [
Exchange.new(mita, 9, 3),
Exchange.new(shinjuku, 5, 1)
]],
["大手町", 2, [
Exchange.new(marunouchi, 17, 1),
Exchange.new(chiyoda, 10, 2),
Exchange.new(tozai, 8, 2),
Exchange.new(mita, 8, 3)
]],
["三越前", 2, [
Exchange.new(ginza, 11, 1)
]],
["水天宮前", 1, nil],
["清澄白河", 1, [
Exchange.new(ooedo, 13, 2)
]],
["住吉", 2, [
Exchange.new(shinjuku, 12, 1)
]],
["錦糸町", 1, nil],
["押上", 0, [
Exchange.new(asakusa, 19, 2)
]]
])
# 半蔵門線全体の乗換候補
# これも処理をメソッド化（これも他路線に使えるメソッド）
# こちらは上の入力データから自動的に設定しています。
def setLineExchanges(line)
index = 0
line.stations.each do |station|
if(station.exchanges != nil)
station.exchanges.each do |exchange|
line.exchanges << LineExchange.new(index, exchange.dstLine, exchange.dstStationIndex)
end
end
index = index + 1
end
end
setLineExchanges(hanzomon)
# オワリ
#------------------
上のクラス定義とこの入力例だけでとりあえず通りました。データもちゃんと入力されます。
例）永田町駅の、銀座線への乗り換え所要時間
入力：p hanzomon.stations[3].exchanges[1].exchangeTime
出力：3
########################################
++++++++++++++++++++++++++++++
３．想定するアプリケーション
++++++++++++++++++++++++++++++
まず、このデータモデルでは（駅データから機械的に生成できるものですが）路線全体に対する乗換候補を持っているので、最も少ない乗換回数で行くルートなどの検索はしやすいはずです。
また、それに伴っていわゆる乗換検索も（時刻表などは利用していないので、所要時間はおおよその値となりますが）ある程度高速にできると思います。