C++の課題

質問

名古屋市の地下鉄について、２駅を選び、選んだ２駅間の所要時間を求めるプログラムを作りたいのですが、何から作っていけばいいか検討がつきません。
アドバイスや作り方などがわかる方がいたら教えてください。
ちなみに、駅間の所要時間は２分で路線の乗り換えには５分を要します。

例　自由ヶ丘と星ヶ丘を選択→所要時間１１分

路線図　http://www.kotsu.city.nagoya.jp/subway/sub_route.html

回答No.5

fonera

恐れ入ります。

この手の課題は、問題を正しく把握することからスタートしましょう。
「何から作る・どうプログラムするの？」という実装の問題ではなく、「どういう課題なの？」という設計の問題です。

・まず、問題の難しさを把握します。
名古屋市の地下鉄はwikipediaによれば6つの路線を持ち、全部で96の駅があります。
http://ja.wikipedia.org/wiki/%E5%90%8D%E5%8F%A4%E5%B1%8B%E5%B8%82%E5%96%B6%E5%9C%B0%E4%B8%8B%E9%89%84
但し、例えば名港線の金山駅と名城線の金山駅は、同じ駅だと見なせるので、重複を除くとと82の駅があります。

ここまで判れば、単純に駅間の所要時間を手作業で調べるのが現実的でないのは判るはずです。
(重複無しで82駅から2駅選び出す組み合わせ = 82C2 = 3321通り)

・次に、問題をモデル化（本質をとらえたまま単純化）します。
電車や車などの経路を考えるときには、どのように接続されているかが問題であって、図形としての意味はあまりありません。
一般的に、経路をモデル化する際には、「グラフ」を用います。グラフとは、「駅」とその駅同士を繋ぐ「路線」で問題をとらえる手法です。
例：[名古屋港]-2分-[築地口]-2分-[港区役所]

例示したグラフは、重み付き無向グラフと呼ばれるものです。（路線が一方通行ではなく、所要時間が設定されている）
このグラフをうまく使うと「乗り換え」も「所要時間」として置き換え可能です。
例：[日比野]-2分-[金山]-5分-[金山]-2分-[西高蔵]
____[東別院]------------2分---|

・そして、アルゴリズム（問題を解く方法）を選択します。
ここまで出来れば、後は総当たり法でも答えを得ることは出来ます。深さ優先探索や幅優先探索で調べれば、実装の方法も判ると思います。
（取り得るルートを全て調べ尽くす。その中で最も短い距離が答え。PCにやらせるならそれほど時間はかからない）

しかし、「ある２点間の距離を調べる」というのは良くある課題で、すでに先人の研究成果が蓄積されています。
例えば、ANo.1の方が書いておられる「ダイクストラ法」がよく使われます。文献も豊富ですので、調べれば理解は容易でしょう。
（よくわからなければ、理解できない点を明確にして補足質問していただければ、ご説明いたします）

・最後に、具体的な実装の方法を考えます。
具体的にC++でどのようにプログラミングすればよいかなどは、最後の最後に考えれば良いことです。
後は調べながら手を動かしましょう。

例えば無向グラフである地下鉄路線図を表現する方法として、
struct Station{
vector<int> nextStation;//次の駅番号
vector<int> backStation;//前の駅番号
vector<int> nextTime;//次の駅への所要時間
vector<int> backTime;//前の駅への所要時間
};
等が考えられるでしょう。vectorを使うのは、１駅から２方向に路線が延びている事があるからです。
（名古屋市の地下鉄では3路線が合流している[名古屋]駅が最多乗り換えなので、int[3]等の決めうちでも良いかもしれません）

課題を「把握」して「モデル化」して「アルゴリズムを選択」する事を覚えれば、「プログラミング」は単に参考書を引きながら手を動かすだけです。
***
ご質問のC++の課題は、かなり面白い部類かと思います。（私も試しに解いてみましたが、2時間ばかりかかってしまいました…）
この手の課題を何問かこなすと、大抵の問題をプログラミングできるようになります。
「この問題は、こう解けば良い」という一対一対応で覚えていては応用が利きません。「この問題は、どういう風にとらえることが出来るか。過去の研究成果はないか」など、自分で問題を捉えて解き方を調べられるようになれば、幅広く応用が利きます。
個人的には良い講義を受けておられるかと思います。是非、頑張ってみてくださいね。

回答No.4

redfox63

何から作って良いかわからないならわかるまで教授や講師から補習を受けてみましょう

すべての駅間の所要時間が2分なら 発駅と着駅が何区間かを算出できればよいことになります
その間に乗換えがあるなら5分を加算する
といったルーチンがメインになろうかと思います

発駅、着駅がどの路線に属しているのか
その路線はどの駅でどの路線に接続しているのか
といったデータをクラス(または構造体)に盛り込まないといけないでしょう

回答No.3

jacta

まずは一番簡単な方法から始めましょう。
具体的には、各駅に0～の連番を振ります。そして、乗車駅と下車駅を添え字とする所要時間の二次元配列を作ります。

const int 所要時間[乗車駅][下車駅] = { 調査した所要時間で初期化 };

ここまでできれば後は分かると思います。

回答No.2

asuncion

> 検討がつきません。

（誤）検討がつきません。
（正）見当がつきません。

回答No.1

bin-chan

「ダイクストラ法による最短経路検索」なんかが必要なんでしょうね。
キーワードを「ダイクストラ　アルゴリズム　８００」で検索してみてください。トップのサイトが面白い。

実際には、駅間の所要時間すべてを調査、からはじめる事になるでしょうね。