实现函数(递归)的麻烦

Question

该计划的目的是列举一个人可以通过地铁系统从A站到L站的所有可能的路径，而不超过一次。我知道有640条可能的路径，就像老师告诉我们的那样，我们用邻接矩阵作为C语言的早期作业编写了这个程序。现在的目标是做同样的事情，这就是枚举所有可能的路由并打印出每个路由，除了使用类(具体地说是3: SubwaySystem、Station和Track)之外，这次不使用矩阵。这是地铁系统本身的示意图。

​

​

我和我的助教讨论了这个项目，以及如何处理这个项目。他给了我一些想法，比如使用数组来表示站点和轨道，我决定使用我在文章底部的整个代码中所显示的方法。

让我向您展示我的代码中那些我无法解决的问题区域(递归对我来说是新的)。

 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和我一样基本上是个计数器。

my_station是一个大小为12的数组，可容纳所有12个站点。

my_track是一个大小为34的数组，它在每个站之间保持所有可能的轨道组合。

track_starting_ID表示某个站点的可能轨道从my_track数组中开始的位置。对不起，我不知道怎么用更好的方式表达这句话。例如，如果您引用站点数组和跟踪数组，则在post底部的整个代码部分中，我在SubwaySystem构造函数中初始化。您可以看到，track_starting_ID指的是某个站点轨道开始的起始位置。即，starting_ID =0对应于从"A“站引向轨道的起点的my_track，而starting_ID为1的starting_ID是指从站"B”引导的轨道的起始点my_track(1)。starting_ID = 6对应于位于6位置的my_track阵列中从"C“站引导的轨道，依此类推。(希望这能让它更清晰，而不是更令人困惑)。

track_size表示从图片中可以看到的每个站点的轨道数。例如，B站的轨道大小为5，因为从B站冒出5条轨道。

访问和node_1和node_2是不言自明的。访问是一个布尔变量，它检查是否已经访问了一个站点，并且节点分别是当前轨道两侧的站点。

问题是，我不知道如何修复递归发生的函数。几天前，我和我的助教讨论过这件事，我告诉他我想用我的功能完成什么。我们一起编写了一些伪代码，以便更清楚地了解我试图编写的函数的目标是什么，我提供了：

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到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);
}

Answer 1

好的，这是一个可行的解决方案，它给出了605个解决方案，我认为是正确的

// RandomTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <iostream>
#include <string>
using namespace std;






class Track
{
public:
    //Default Constructor
    Track();

    //Overload Constructor
    Track(char, char, int station, int opposite);

    //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;

    int connected_station;
    int opposite_track;
};

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

    void SearchRoute(int Current_Station_ID, int from_track_id, Track **currentPath, int pathCount);
};





// **cpp**


//#include "subway.h"

using namespace std;

Track::Track()
{
    visited = 0;
}


Track::~Track()
{
}


Track::Track(char pass_track1, char pass_track2, int station, int opposite)
{
    node_1 = pass_track1;
    node_2 = pass_track2;
    connected_station = station;
    opposite_track = opposite;

    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', 1, 1);
    my_track[1] = Track('b', 'a', 0, 0);
    my_track[2] = Track('b', 'c', 2, 6);
    my_track[3] = Track('b', 'd', 3, 8);
    my_track[4] = Track('b', 'e', 4, 10);
    my_track[5] = Track('b', 'f', 5, 15);
    my_track[6] = Track('c', 'b', 1, 2);
    my_track[7] = Track('c', 'e', 4, 11);
    my_track[8] = Track('d', 'b', 1, 3);
    my_track[9] = Track('d', 'e', 4, 12);
    my_track[10] = Track('e', 'b', 1, 4);
    my_track[11] = Track('e', 'c', 2, 7);
    my_track[12] = Track('e', 'd', 3, 9);
    my_track[13] = Track('e', 'g', 6, 17);
    my_track[14] = Track('e', 'h', 7, 19);
    my_track[15] = Track('f', 'b', 1, 5);
    my_track[16] = Track('f', 'h', 7, 20);
    my_track[17] = Track('g', 'e', 4, 13);
    my_track[18] = Track('g', 'k', 10, 28);
    my_track[19] = Track('h', 'e', 4, 14);
    my_track[20] = Track('h', 'f', 5, 16);
    my_track[21] = Track('h', 'i', 8, 24);
    my_track[22] = Track('h', 'j', 9, 26);
    my_track[23] = Track('h', 'k', 10, 29);
    my_track[24] = Track('i', 'h', 7, 21);
    my_track[25] = Track('i', 'k', 10, 30);
    my_track[26] = Track('j', 'h', 7, 22);
    my_track[27] = Track('j', 'k', 10, 30);
    my_track[28] = Track('k', 'g', 6, 18);
    my_track[29] = Track('k', 'h', 7, 23);
    my_track[30] = Track('k', 'i', 8, 25);
    my_track[31] = Track('k', 'j', 9, 27);
    my_track[32] = Track('k', 'l', 11, 33);
    my_track[33] = Track('l', 'k', 10, 32);
    //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()
{
}



void SubwaySystem::SearchRoute(int Current_Station_ID, int from_track_id, Track **currentPath, int pathCount)
{
    if(my_station[Current_Station_ID].track_starting_ID == 33)
    {
        count_routes++; //Add 1 into the variable “count_routes”
        cout << count_routes << " ";
        for(int i= 0; i < pathCount; i++)
        {
            cout << *currentPath[i]; 
        }
        cout << endl;
        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++)
        {
                    //check all the tracks that we have visited before
            bool visited = false;
            for(int n = 0; n < pathCount; n++)
            {
                if(currentPath[n] == &my_track[i] || i == currentPath[n]->opposite_track) visited = true;
            }


            if(!visited)
            {
                int nextStation = my_track[i].connected_station;
                currentPath[pathCount] = &my_track[i];
                SearchRoute(nextStation, i, currentPath, pathCount + 1); 
            }
        }  
    }
}




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 "subway.h"






int _tmain(int argc, _TCHAR* argv[])
{

    Track *tempTracks[34];
    SubwaySystem findPaths;
    findPaths.SearchRoute(0, -1, tempTracks, 0);

    getchar();

    return 0;
}

Answer 2

我认为你的主要问题是：

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++); <<<<<<<< PROBLEM 
i--; //Backtrack this track  <<<<<<< Also this will do nothing
my_track[Current_Station_ID].visited = 0; <<<<<<< Now Current_Station_ID is 1 more than you are expecting it to be.
my_track[Current_Station_ID].node_2 = 0;//mark its corresponding track as unvisited

您在块中间执行Current_Station_ID++，然后再次使用它，就好像它与前面的值一样，++操作符实际上将Current_Station_ID的值增加了1。

您也不需要在for循环中锁定此项。所以应该是这样的：

void SubwaySystem::SearchRoute(int Current_Station_ID, int from_track_id, Track *currentPath, int pathCount)
{
    if(my_station[Current_Station_ID].track_starting_ID == 33)
    {
        count_routes++; //Add 1 into the variable “count_routes”
        cout << count_routes << " ";
        for(int i= 0; i < pathCount; i++)
        {
             cout << my_track[i]; 
        }
        cout << endl;
        return;
    }
    else //Get into recursive Function Body
    {

         if(from_track_id >= 0) my_track[from_track_id].visited = 1; 

        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++)
        {
            int nextStation = my_track[i].node_2;   ///<<<<<<< But you will need to change node_2 to be an int, and use the station number, not letter when you set them up
            if(my_track[i].visited == 0)
            {
                currentPath[pathCount] = my_track[i];
                SearchRoute(nextStation, i, currentPath, pathCount + 1); 


            }
        }

       if(from_track_id >= 0) my_track[from_track_id].visited = 0; 
    }
}

然后在您的主要功能中执行以下操作：

int main()
{
    Track tempTracks[34];
    SubwaySystem findPaths;
    findPaths.SearchRoute(0, -1, tempTracks, 0);
}

Answer 3

我找到640条路线：

#include <stdio.h>

const char *connectom[] = {
"B",            // A
"ACDEF",        // B
"BE",           // C
"BE",           // D
"CDBGH",        // E
"BH",           // F
"EK",           // G
"EFJKI",        // H
"HK",           // I
"HK",           // J
"HIJGL",        // K
"K"             // L
};

char tracks[0x100];
char strout[0x100];

void path(char x, char *s) {
  *s++ = x;
  if(x == 'L') {
    *s = 0;
    printf("path=%s\n", strout);
  } else {
    for(const char *p = connectom[x - 'A']; *p; p++) {
       unsigned char track_ndx = x > *p? (x << 4) ^ *p : (*p << 4) ^ x;
       if(tracks[track_ndx] == 0) {
         tracks[track_ndx] = 1;
         path(*p, s);
         tracks[track_ndx] = 0;
       } // if
    } // for
  } // else
} // path

int main(int argc, char **argv) {
  path('A', strout);
} // main