鉄道とグラフ理論 (2)

技術研究所のまつけんです。

先日、part 1として大回り乗車のルートを列挙するC++プログラムを作り、架空の路線図について実行してみました。今回は、実際の路線図で実行してみたいと思います。路線図については、前回も紹介したサイト (http://noritetsu.net/omawari/2015/03/sozai-download/) のものを参考にしました。

まず、比較的シンプルなものから実行してみましょう。仙台近郊と福岡近郊の路線図を簡略化して、隣接行列にしてみました(詳しくは、part 1参照)。見やすくするため、隣接行列の「ゼロ」になっている部分は空白としています。括弧が付いている駅は、乗り換えの余地が無い、分岐点になり得ない駅です。

仙台近郊について経路を列挙するには、49~53行目を以下の内容で置き換えます:

names = { “羽前千歳”, “小牛田”, “塩釜”, “高城町”, “仙台”, “(福島)” };
matrix.push_back(vector<int>{ 0, 1, 0, 0, 1, 1 });
matrix.push_back(vector<int>{ 1, 0, 1, 1, 0, 0 });
matrix.push_back(vector<int>{ 0, 1, 0, 1, 1, 0 });
matrix.push_back(vector<int>{ 0, 1, 1, 0, 1, 0 });
matrix.push_back(vector<int>{ 1, 0, 1, 1, 0, 1 });
matrix.push_back(vector<int>{ 1, 0, 0, 0, 1, 0 });

同様に、福岡近郊について経路を列挙するには、49~53行目を以下の内容で置き換えます:

names = { “吉塚”, “香椎”, “折尾”, “(西小倉)”, “長老原”, “新飯塚”, “桂川” };
matrix.push_back(vector<int>{ 0, 1, 0, 0, 1, 0, 1 });
matrix.push_back(vector<int>{ 1, 0, 1, 0, 1, 0, 0 });
matrix.push_back(vector<int>{ 0, 1, 0, 1, 0, 1, 0 });
matrix.push_back(vector<int>{ 0, 0, 1, 0, 0, 1, 0 });
matrix.push_back(vector<int>{ 1, 1, 0, 0, 0, 0, 1 });
matrix.push_back(vector<int>{ 0, 0, 1, 1, 0, 0, 1 });
matrix.push_back(vector<int>{ 1, 0, 0, 0, 1, 1, 0 });

仙台近郊の結果です:

6つの駅、9本の路線でも、実に106もの経路があります。では、7駅10路線の福岡近郊は、どのようになるかというと、以下のようになります:

こちらは、122の経路が生成されています。

次回は、いよいよ東京近郊の路線図(49駅77路線)について実行してみたいと思います。一体、どれだけの経路が生成されてしまうのでしょうか。それでは、次回をお楽しみに。

 

  • このエントリーをはてなブックマークに追加