bug/ basis path算法错误，我找不到

Question

下面将查看二维数组以查找基本集路径。它应该打印出单独的路径，但不重复任何路径，并在找到所有路径时结束。然而，它并没有停止在最后一条路径上，并且在它的某个地方有一个bug，其中发生了以下情况:它在路径中进行了一半，然后转到零，然后由于某种原因结束了路径。

例如，表中填充了以下内容:全0，除了

1、1、2、2、3、4、5、6

它们都有一个1。所需路径为P1：%1%2%4%6%0

P2: 1 3 5 6 0

P3: 1 2 5 6 0。

当我运行这个程序时，我得到的输出是12460

13560

1250

124

这方面的任何帮助都是非常感谢的，这只是一个扫描数组查找路径的函数，如果对我有帮助，我可以添加整个程序。谢谢..

void find_path(int map[][MAX], int x){
 int path =0;
 int m=1;
 int blah=0;
 bool path_found = false;

 do
 {
  for(int n=0;n<(x+1);n++){
   if(map[m][n]==-1){
    blah=(n+1);
    if(blah<(x+1)){
     for(blah;blah<(x+1);blah++){
      if(map[m][blah]==1){
       map[m][blah]=-1;
       path=m;
       path_found = true;
       cout<<path;
       m=blah;
       n=0;
      }
     }
    }
    else{  
    path=m;
    path_found=false;
    cout<<path;
    m=n;
    if(m==0){
     path=0;
     cout<<path<<endl;
     m=1;
     path_found=false;
     }
    } 
   }
   else if(map[m][n]==1){
    map[m][n]=-1;
    path=m;
    path_found = true;
    cout<<path;
    m=n;
    if(m==0){
     path=0;
     cout<<path<<endl;
     m=1;
     path_found=false;
    }
   }

  }
 } 
 while(m<(x+1) && path_found);
}

Answer 1

你犯了一个非常常见的错误。太多的人认为编写软件的主要目标是告诉计算机要做什么。这是不正确的。主要的目标是清楚地告诉一个人对其他人做了什么。第二个目标是告诉计算机该做什么。

我建议您不要使用硬编码数字(map=-1中的-1)。枚举就是为此而生的。变量名可以更具描述性。(“废话”？)您可以将for子句留空，例如for(；blah<(x+1)；blah++)。(即使for(;;)也是有效的。)通常数组从0..LIMIT-1开始，所以你可以说for(；blah添加评论！解释你在做什么。当你在它的时候，添加空格。紧凑代码不是任何人的朋友。至少，记录您正在更改MAP中的值。

话虽如此..。从哪里开始...

在更改节点后，我将从第一个路径选项开始，而不是从当前节点加1开始。(例如，从1跳到2，从2跳到4，然后开始查找map4，而不是map4或map4。

我不会将特殊的大小写0作为退出条件。

您的" for (blah;blah<(x+1);blah++){“行在找到mapm==1匹配项时不会退出(中断)，而是将其标记为-1并继续查找其他匹配项。这应该会用前面的"for(int n=0;n<(x+1);n++){“行创建一个有趣的效果。

一旦你点击M=6，N=1，你就永远不能点击你的特殊情况下的0退出条件并打印出来。(你知道你有n=0，后面跟着n++？)

一旦你有了一个满是-1的地图，你就再也不能继续下去了。当你的一些路径共享相同的链接时，这是一个真正的问题。例如，1-2-4-6-0和1-3-5-6-0共享6-0。

你不会检测到一个满是-1的地图，你会有一个无限的循环。(如果您要将path_found设置为false，请在" do {“之后，在"for(int n=0;n<(x+1);n++){”之前执行此操作。而不是嵌套在if语句中的一些容易遗漏的退出点。

当我运行你的程序时，我看不到输出12460,13560,1250,124。我看到12460,135，然后它就挂了。(而且只有在我修改了您的软件以在每次写入后刷新输出之后才会发生这种情况。)

您没有显示脚手架代码。类似于：

void printMap(int theMap[][MAX] )
{
  for( int i=0; i<MAX; ++i )
  {
    cout << "[" << i << "] ";
    for ( int j=0;  j<MAX;  ++j )
      cout << "  " << theMap [i] [j];
    cout << endl;
  }  /* for( int i=0; i<MAX; ++i )  */
  cout << endl;
}

再加上一个调试器(在gdb中使用"call printMap(map)")将会对您有所帮助。(对我来说肯定是这样。)

你的代码会自我复制。这通常是一个错误的信号。例如"if(m==0){ path=0；cout<

尽管如此，我不得不使用更糟糕的代码(在专业的情况下也是如此)。(虽然不常见，但确实会发生。)坚持下去，你会变得更好。我们都是从一个糟糕的地方开始的。练习，不断提问，你就会进步。

对此处评论的响应...

我有特殊的0的唯一原因是，当它到达0时，它刚刚挂起，因为那一行是空的，它停留在一个无限的循环中。

您需要针对退出条件进行更好的测试。

当我编译并运行它时，我得到了我所描述的输出，而不是你得到的。

我使用了g++版本3.4.4，其中包含：

#define MAX 7
                      /* 0  1  2  3  4  5  6 */
int  map[MAX][MAX] = { { 0, 0, 0, 0, 0, 0, 0 }, /*0*/
                       { 0, 0, 1, 1, 0, 0, 0 }, /*1*/
                       { 0, 0, 0, 0, 1, 1, 0 }, /*2*/
                       { 0, 0, 0, 0, 0, 1, 0 }, /*3*/
                       { 0, 0, 0, 0, 0, 0, 1 }, /*4*/
                       { 0, 0, 0, 0, 0, 0, 1 }, /*5*/
                       { 1, 0, 0, 0, 0, 0, 0 }  /*6*/
                     };

find_path( map, 6 );

也许你的输入条件是不同的？

我不明白为什么它会到达m=6 n=1，除了6，其余的行都是0。

下面的代码是您的(只做了一些小的修饰)。

Line=25上出现了N=0。当Line=16处的for循环完成时，我们在Line=9处恢复for循环。第一步是最终迭代(n++)组件。因此，Line=10的下一个for循环迭代具有m=blah=6和n=1。在这个阶段，您的任何条件测试(==-1，==1)都不可能为真。

您真的应该尝试在调试器中单步执行代码。看看代码实际在做什么，而不是你期望它做什么。

/* 0*/   void find_path( int map[][MAX], int x )
/* 1*/   {
/* 2*/     int  path = 0;
/* 3*/     int  m    = 1;
/* 4*/     int  blah = 0;
/* 5*/     bool path_found = false;
/* 6*/   
/* 7*/     do
/* 8*/     {
/* 9*/       for ( int n=0;  n < (x+1);  n++ )
/*10*/       {
/*11*/         if ( map [m] [n] == -1 )
/*12*/         {
/*13*/           blah = (n+1);
/*14*/           if ( blah < (x+1) )
/*15*/           {
/*16*/             for ( ;  blah < (x+1);  blah++ )
/*17*/             {
/*18*/               if ( map [m] [blah] == 1 )
/*19*/               {
/*20*/                 map [m] [blah] = -1;
/*21*/                 path = m;
/*22*/                 path_found = true;
/*23*/                 cout << path;
/*24*/                 m = blah;
/*25*/                 n = 0;
/*26*/               } /* if ( map [m] [blah] == 1 ) */
/*27*/             } /* for ( ;  blah < (x+1);  blah++ ) */
/*28*/           } /* if ( blah < (x+1) ) */
/*29*/           else
/*30*/           {
/*31*/             path = m;
/*32*/             path_found = false;
/*33*/             cout << path;
/*34*/             m = n;
/*35*/             if ( m == 0 )
/*36*/             {
/*37*/               path = 0;
/*38*/               cout << path << endl;
/*39*/               m = 1;
/*40*/               path_found = false;
/*41*/             } /* if ( m == 0 ) */
/*42*/           } /* if ( blah < (x+1) ) ... ELSE ... */
/*43*/         } /* if ( map [m] [n] == -1 ) */
/*44*/         else if ( map [m] [n] == 1 )
/*45*/         {
/*46*/           map [m] [n] = -1;
/*47*/           path = m;
/*48*/           path_found = true;
/*49*/           cout << path;
/*50*/           m = n;
/*51*/           if ( m == 0 )
/*52*/           {
/*53*/             path = 0;
/*54*/             cout << path << endl;
/*55*/             m = 1;
/*56*/             path_found = false;
/*57*/           } /* if ( m == 0 ) */
/*58*/         } /* if(map[m][n]==-1) ... ELSE IF (map[m][n]==1) ... */
/*59*/         
/*60*/       } /* for ( int n=0;  n < (x+1);  n++ ) */
/*61*/       
/*62*/     } /* do { ... } */ while(m<(x+1) && path_found);
/*63*/     
/*64*/   } /* void find_path( int map[][MAX], int x ) */

Answer 2

当我使用你发布的I get 12460作为输出编译函数时，它挂起在一个无限的循环中，除非我去掉if ( blah < (x+1)和相应的else，然后我得到我第一次描述的输出。

我已经尝试过了，并想出了下面的代码，输出为124601356，然后结束。

void find_path(int map[][MAX], int x){
    int path =0;
    int m=1;
    int rest_of_row=0;
    bool path_found;
    do
    {
        path_found = false;
        for(int n=0;n<(x+1);n++){
            //check to see if the node is already used on a path
            if(map[m][n]==-1){
                rest_of_row=(n+1);
                path=m;

                //check to see there are any unused nodes for the path from found node +1 to end of row
                do{
                    if(map[m][rest_of_row]==1){
                        map[m][rest_of_row]=-1;
                        path_found = true;
                    }
                    else{
                        ++rest_of_row;
                    }
                }
                while(!path_found);

                m=n;


                if(path_found){
                    m=(rest_of_row);
                }

                cout<<path;
            }
            //else check to see if the node hasn't been used in the path
            else if(map[m][n]==1){
                map[m][n]=-1;
                path=m;
                path_found = true;
                cout<<path;
                m=n;
            }
            //if the node is at 0 path is complete, go back to 1 to check for new path
            if(m==0){
                path=m;
                m=1;
                path_found=false;
                cout<<path;
            }
        }
    }
    while(m<(x+1) && path_found);

}

Answer 3

以下是可用的代码(使用足够高级的C++，你不能将其作为自己的工作提交，这也要感谢mrree，我从mrree的答案中“举起”了map的初始化器)。我建议你更深入地思考这个问题，从为什么我的正确解决方案使用递归开始，而你的解决方案既没有递归也没有堆栈。我认为实际上可以避免堆栈，因为路径数组具有回溯所需的所有状态，但您确实需要某种形式的回溯。

// enumpaths.cpp : Prints all longest paths given a digraph connectivity matrix
//

const size_t MAX = 7;

typedef void (*path_completed_cb)( const size_t (&path)[MAX], size_t const currentLength );

void follow_path( size_t (&path)[MAX], size_t const currentLength, const bool (&map)[MAX][MAX], path_completed_cb const callback )
{
 size_t currentEnd = path[currentLength-1];

 /* check for loops, if a loop exists then every finite path is
    a subpath of a longer (looped more often) path */
 for( size_t i = 0; i < currentLength; i++ ) {
  if (map[currentEnd][path[i]]) return; /* found a loop */
 }

 bool extended = false;
 /* look for continuances */
 for( size_t next = 0; next < MAX; next++ ) {
  if (map[currentEnd][next]) {
   extended = true;
   path[currentLength] = next;
   follow_path(path, currentLength+1, map, callback);
  }

 }
 if (!extended) {
  /* there were no outgoing arcs, this is a longest path */
  (*callback)(path, currentLength);
 }
}

void enum_paths( const bool (&map)[MAX][MAX], path_completed_cb const callback )
{
 for ( size_t start = 0; start < MAX; start++ ) {
  bool isSource = true;
  /* if any incoming arcs to node "start", then any paths
     starting at start are subpaths of longer paths */
  for (size_t pred = 0; pred < MAX; pred++ )
   if (map[pred][start]) isSource = false;

  if (isSource) {
   size_t path[MAX] = { start };
   follow_path(path, 1, map, callback);
  }
 }
}

#include <iostream>
#include <iomanip>

void print_path( const size_t (&path)[MAX], size_t const currentLength )
{
 using namespace std;
 cout << path[0];
 for( size_t i = 1; i < currentLength; i++ ) {
  cout << '-' << path[i];
 }
 cout << endl;
}

int main()
{                   
 const bool map[MAX][MAX] =
  /* 0  1  2  3  4  5  6 */
 { { 0, 0, 0, 0, 0, 0, 0 }, /*0*/
   { 0, 0, 1, 1, 0, 0, 0 }, /*1*/
   { 0, 0, 0, 0, 1, 1, 0 }, /*2*/
   { 0, 0, 0, 0, 0, 1, 0 }, /*3*/
   { 0, 0, 0, 0, 0, 0, 1 }, /*4*/
   { 0, 0, 0, 0, 0, 0, 1 }, /*5*/
   { 1, 0, 0, 0, 0, 0, 0 }  /*6*/
 };

 enum_paths(map, &print_path);

 return 0;
}

编辑:在没有递归的情况下进行了尝试，虽然简单地删除递归只是一个机械转换，但在不引入gotos的情况下完成它并不容易。将“路径开始”的情况与“路径的中间”逻辑合并也是如此。