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

 

先日、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路線)について実行してみたいと思います。一体、どれだけの経路が生成されてしまうのでしょうか。それでは、次回をお楽しみに。