執行尋找路徑遞歸函數的問題

Question

我試圖打印出從A到L有地鐵站的地鐵系統中的所有可能路徑。換句話說，目標是找出一個人可以採用多少路線通過地鐵系統不會超過一次軌道。自從我在前面的C中使用一個鄰接矩陣編寫此程序後，我知道有640條可能的路徑。現在我試圖編寫相同的程序，除了在C++中使用類而不使用鄰接矩陣。

我遇到的問題是，我似乎無法正確實現我的遞歸函數SearchRoute，因爲我需要打印路徑，標記路徑，然後再次取消標記路徑以允許回溯。當我打印出最終結果時，我只能得到一條從A到B的軌跡，這顯然意味着明顯的錯誤。

這就是我認爲的問題是：我知道在我的SubwaySystem :: SearchRoute函數中，我使用了一個if和else語句，它明顯不允許我的遞歸函數被調用，但我試着把另一個if語句而不是其他的但我不太確定條件是什麼。

void SubwaySystem::SearchRoute(int Current_Station_ID) 
{ 
    while(Current_Station_ID < 33) 
    { 
     cout << "In while loop\n"; 
     // \\ Checking progress 
     if(Current_Station_ID == 0) //Find a successful route to Station L 
     { 
      count_routes++; //Add 1 into the variable 「count_routes」 
      cout << "In if statement\n"; 
      // \\Checking progress 
      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 
       { 
        cout << "In recursive part of function\n"; 
        // \\ Checking progress 
        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] << endl; //save this track 
        SearchRoute(Current_Station_ID + 1); //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 
       } 
      } 
     } 
    } 
} 

此外，我還嘗試在打印報表中一路追蹤整個程序的進度。我的遞歸函數永遠不會因爲我上面指定的原因而被調用（至少這就是爲什麼我認爲它不起作用）。由於某種原因，我無法弄清楚爲什麼我的默認和重載軌道構造函數被多次調用。

如果你能幫我弄清楚我的代碼中的問題區域/以正確的方式顯示我，我將不勝感激。我厭倦了這個想法。提前致謝。

下面是程序中的一個單一的TU休息：

//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; 
    char node_2; 
    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; 
    //cout << "Default Track has been called\n"; 
    //\\ Checking progress 
} 


Track::~Track() 
{ 
} 


Track::Track(char pass_track1, char pass_track2) 
{ 
    node_1 = pass_track1; 
    node_2 = pass_track2; 
    visited = false; 
    //cout << "Overload Track constructor has been called\n"; 
    // \\ Checking progress 
} 


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; 
    //cout << "Overload station has been called\n"; 
    // \\ Checking progress 
} 


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; 
    //cout << "SubwaySystem constructor called\n"; 
    // \\ Checking progress 
} 


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(int argc, char **argv) 
{ 
    SubwaySystem Test; 
    Test.SearchRoute(0); 
} 

對不起，如果「檢查進度」打印報表，使其難以閱讀的代碼。

Answer 1

你永遠不會進入遞歸：

// this method is called with value 0 
void SubwaySystem::SearchRoute(int Current_Station_ID) 
{ 
    while(Current_Station_ID < 33) 
    { 
     cout << "In while loop\n"; 
     // \\ Checking progress 
     if(Current_Station_ID == 0) //Find a successful route to Station L 
     { 
      count_routes++; //Add 1 into the variable 「count_routes」 
      cout << "In if statement\n"; 
      // \\Checking progress 
      cout << count_routes << " " << my_track[Current_Station_ID] << endl; //Print out this route 
      return; // ERROR: here you return from the very 1st method call, breaking the search 
     } 

Answer 2

基本上無需編寫代碼爲你我的建議是：

你的遞歸函數不應該在所有的while語句（遞歸函數的整點這本身就是一種時間聲明）。

遞歸函數中的第一件事應該是檢查您的站ID是否與'L'站直接相鄰，或者是否已採取唯一的路徑。如果它是相鄰的，則可以返回從該站到L的軌跡。

如果不存在，則對所有相鄰站的遞歸函數進行調用，這些站具有未到達它們的路徑然後將它們的結果作爲您當時所在電臺計算的一部分。

要根據您的數據的例子闡明：

1. 你先調用函數與「一」作爲參數。
2. 該函數首先檢查'a'是否有'l'路徑（它不會使函數不返回）。
3. 該功能然後自動調用與所有站有我們當前站'a'的路徑。 （僅'b'）
4. 從'b'仍然沒有直接跟蹤'l'，所以函數這次繼續以'a'，'c'，'d'，'e'，' F'。
5. 從新調用函數'a'，第一個檢查發現唯一可用的路由，'b'已被採用，因此它應該返回一個否定的響應，而不是打印任何東西。
6. 當用站發出的函數調用發現它具有'l'的直接路徑時，它應該打印（或存儲）該路徑段並返回true。
7. 遞歸函數從它自己的遞歸調用收集所有結果並將路徑添加到這些工作站的結果。
8. 確切的實施取決於您從程序中需要的輸出。如果需要打印出所有路徑，則可以保存一個有效路徑列表，每當發生新的分支（多個連接的站點）時添加一個路徑，並在您從遞歸函數收到負面返回值時移除路徑。當最後的通話返回時，您可以打印出您收集的路徑。

這是澄清事情嗎？