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