このプログラムの目的は、線路を何度も通過せずに駅 A から駅 L に地下鉄でたどり着けるすべての可能な経路を列挙することです。インストラクターが私たちに言ったように、640の可能なパスがあることを知っており、隣接行列を使用してCで以前の課題としてこのプログラムを書きました。ここでの目標は、同じことを行うことです。これは、すべての可能なルートを列挙し、各ルートを出力することですが、今回はマトリックスを使用せずに、クラス (具体的には 3: SubwaySystem、Station、および Track) を使用して実行することを除きます。これは、地下鉄システム自体の概略図です。
このプログラムとその取り組み方について、TA と話し合いました。彼は、配列を使用して駅や路線を表すなどのアイデアをいくつか教えてくれました。私は、投稿の下部にあるコード全体で示したアプローチを使用することにしました。
私が解決できなかった私のコードの問題領域をお見せしましょう (再帰は私にとって初めてのことです)。
void SubwaySystem::SearchRoute(int Current_Station_ID)
{
if(my_station[Current_Station_ID].track_starting_ID == 33) // Find a successful route to Station L.
//The condition is set to check for 33 because a track_starting_ID of 33 would correspond to station L.
{
count_routes++; //Add 1 into the variable “count_routes”
cout << count_routes << " " << my_track[Current_Station_ID] << endl; //Print out this route
return;
}
else //Get into recursive Function Body
{
for(int i = my_station[Current_Station_ID].track_starting_ID; i < my_station[Current_Station_ID].track_starting_ID + my_station[Current_Station_ID].track_size; i++)
{
if(my_track[Current_Station_ID].visited == 0) //if this track is not visited before
{
my_track[Current_Station_ID].visited = 1; //mark this track as visited
my_track[Current_Station_ID].node_2 = 1; //mark its corresponding track as visited
cout << my_track[Current_Station_ID].node_1; //save this track
SearchRoute(Current_Station_ID++); //Recursive
i--; //Backtrack this track
my_track[Current_Station_ID].visited = 0;//mark this track as unvisited
my_track[Current_Station_ID].node_2 = 0;//mark its corresponding track as unvisited
}
}
}
}
}
変数が何を表しているか説明しましょう:
Current_Station_IDは基本的に i のようなカウンターです。
my_stationは、12 個のステーションすべてを保持するサイズ 12 の配列です。
my_trackは、それぞれのステーション間のトラックのすべての可能な組み合わせを保持するサイズ 34 の配列です。
track_starting_IDは、my_track 配列内で特定のステーションの可能なトラックが始まる位置を表します。申し訳ありませんが、これをより良い方法で表現する方法がわかりません。たとえば、投稿の下部にあるコード部分全体で SubwaySystem コンストラクターで初期化した駅配列と線路配列を参照するとします。track_starting_IDがわかります特定の駅のトラックが始まる場所の開始位置を指します。つまり、starting_ID 0 は、ステーション「A」からのトラックの先頭である my_track[0] に対応し、starting_ID 1 は、ステーション「B」からのトラックの先頭である my_track(1) を参照します。また、starting_ID 6 は、位置 [6] にある my_track 配列のステーション「C」から始まるトラックに対応します。等々。（うまくいけば、これにより混乱するのではなく、より明確になります）。
track_sizeは、画像からわかるように、各ステーションから出ているトラックの数を表します。たとえば、ステーション B から 5 本のトラックが出ているため、ステーション B のトラック サイズは
5になります。自明です。Visited は、ステーションが訪問されたかどうか、およびノードが現在のトラックの両側にあるステーションであるかどうかを確認するブール変数です。
問題は、再帰が発生するように関数を修正する方法がわからないことです。数日前、これについて TA と話し合い、自分の役割で何を達成しようとしているのかを話しました。私が作成しようとしていた関数の目的を明確にするために、いくつかの疑似コードを一緒に書きました。
SearchRoute(int Current_Station_ID)
{
if ( ) //Find a successful route to Station L
{
… //Add 1 into the variable “count_routes”
… //Print out this route
return;
}
else //Get into recursive Function Body
{
//Use the track array to get all of its connected stations
for(int i = starting_ID; i < starting_ID + current size; i++)
{
if() // if this track is not visited before
{
… //mark this track as visited
… //mark its corresponding track as visited
… //save this track
SearchRoute( nextStaton_ID); // Recursive
… //Backtrack this track
… //mark this track as unvisited
… //mark its corresponding track as unvisited
}
}
}
}
これが私が問題を理解していることです。パスを出力し、パスにフラグを付けてから、バックトラッキングを可能にするためにパスのフラグを再度外す必要があるため、再帰関数 SearchRoute を適切に実装できないようです。最終結果を印刷すると、再帰呼び出し自体に何を入れようとしているかに応じて、無限ループに陥ったり、A to B などの単一のトラックを取得したりします。
わかりやすくするために上で投稿した再帰部分を除いたプログラム全体を次に示します。
//Function Declarations
#include <iostream>
#include <string>
using namespace std;
#ifndef SUBWAY_H
#define SUBWAY_H
class Track
{
public:
//Default Constructor
Track();
//Overload Constructor
Track(char, char);
//Destructor
~Track();
//Member variables
char node_1; // node_1 and node_2 represent stations (for example
char node_2; // node_1 would be station A and node_2 would be station B)
bool visited;
};
class Station
{
public:
//Default Constructor
Station();
//Destructor
~Station();
//Overload Constructor
Station(char, int, int);
//Member variables
char station_name;
int track_starting_ID;
int track_size;
};
class SubwaySystem
{
public:
//Default Constructor
SubwaySystem();
//Destructor
~SubwaySystem();
//Recursive function
void SearchRoute(int);
//Other member functions
friend ostream& operator<<(ostream& os, const Track& my_track);
friend ostream& operator<<(ostream& os, const Station& my_station);
//Member variables
Track my_track[34];
Station my_station[12];
int count_routes;
int Current_Station_ID;
//String to save found route
};
#endif
// **cpp**
//Function Definitions
#include <iostream>
#include <string>
//#include "subway.h"
using namespace std;
Track::Track()
{
visited = 0;
}
Track::~Track()
{
}
Track::Track(char pass_track1, char pass_track2)
{
node_1 = pass_track1;
node_2 = pass_track2;
visited = false;
}
Station::Station()
{
}
Station::~Station()
{
}
Station::Station(char pass_station_name, int pass_start, int pass_size)
{
station_name = pass_station_name;
track_starting_ID = pass_start;
track_size = pass_size;
}
SubwaySystem::SubwaySystem()
{
//Initialize tracks
//node_1, node_2
my_track[0] = Track('a', 'b');
my_track[1] = Track('b', 'a');
my_track[2] = Track('b', 'c');
my_track[3] = Track('b', 'd');
my_track[4] = Track('b', 'e');
my_track[5] = Track('b', 'f');
my_track[6] = Track('c', 'b');
my_track[7] = Track('c', 'e');
my_track[8] = Track('d', 'b');
my_track[9] = Track('d', 'e');
my_track[10] = Track('e', 'b');
my_track[11] = Track('e', 'c');
my_track[12] = Track('e', 'd');
my_track[13] = Track('e', 'g');
my_track[14] = Track('e', 'h');
my_track[15] = Track('f', 'b');
my_track[16] = Track('f', 'h');
my_track[17] = Track('g', 'e');
my_track[18] = Track('g', 'k');
my_track[19] = Track('h', 'e');
my_track[20] = Track('h', 'f');
my_track[21] = Track('h', 'i');
my_track[22] = Track('h', 'j');
my_track[23] = Track('h', 'k');
my_track[24] = Track('i', 'h');
my_track[25] = Track('i', 'k');
my_track[26] = Track('j', 'h');
my_track[27] = Track('j', 'k');
my_track[28] = Track('k', 'g');
my_track[29] = Track('k', 'h');
my_track[30] = Track('k', 'i');
my_track[31] = Track('k', 'j');
my_track[32] = Track('k', 'l');
my_track[33] = Track('l', 'k');
//Initialize stations
//station_name, track_starting_ID, track_size
my_station[0] = Station('a', 0, 1);
my_station[1] = Station('b', 1, 5);
my_station[2] = Station('c', 6, 2);
my_station[3] = Station('d', 8, 2);
my_station[4] = Station('e', 10, 5);
my_station[5] = Station('f', 15, 2);
my_station[6] = Station('g', 17, 2);
my_station[7] = Station('h', 19, 5);
my_station[8] = Station('i', 24, 2);
my_station[9] = Station('j', 26, 2);
my_station[10] = Station('k', 28, 5);
my_station[11] = Station('l', 33, 1);
//Initiaize other members
count_routes = 0;
Current_Station_ID = 0;
}
SubwaySystem::~SubwaySystem()
{
}
ostream& operator<<(ostream& os, const Track& my_track)
{
os << my_track.node_1 << '.' << my_track.node_2;
return os;
}
ostream& operator<<(ostream& os, const Station& my_station)
{
os << my_station.station_name << '.' << my_station.track_starting_ID << '.' << my_station.track_size;
return os;
}
//This is where the above recursive function SearchRoute goes. I posted it separately so it's easier to read.
// **main**
#include <iostream>
#include <string>
//#include "subway.h"
using namespace std;
int main()
{
SubwaySystem findPaths;
findPaths.SearchRoute(0);
}