c++ - 基础集路径算法中的错误/错误，我无法弄清楚

Question

以下内容通过2D数组进行查找以找到基本集路径。应该打印出单个路径，但不重复任何路径，并在找到所有路径时结束。但是，它不会在最后一条路径处停止，而在其中发生错误的地方会发生以下错误:它经过路径的一半，然后变为零，并出于某种原因结束了路径。

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

[1] [2]，[1] [3]，[2] [4]，[2] [5]，[3] [5]，[4] [6]，[5] [6]，[ 6] [0]

里面都有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)。为此进行了枚举。变量名称可能更具描述性。 (“blah”？)。您可以将for子句留空，例如for(; blah <(x + 1); blah ++)。 (即使for(;;)也有效。)通常数组从0..LIMIT-1开始，因此您可以说for(; blah 添加评论! 解释您在做什么。随时随地添加空格。紧凑的代码是没人的 friend 。至少要记录您要更改MAP中的值。

所有这些...从哪里开始...

好吧，更改节点后，我将从第一个路径选项开始，而不是从当前节点加1开始。(例如，从1跳到2，从2跳到4，然后开始查看 map [4] [5]代替了map [4] [0]或map [4] [1]。

我没有特殊情况下的0作为退出条件。

找到map [m] [blah] == 1匹配项时，您的“for(blah; blah <(x + 1); blah ++){”行不会退出(中断)，但将其标记为-1并继续查找其他比赛。前面的“for(int n = 0; n <(x + 1); n ++){”行应该会产生有趣的效果。

一旦您达到M = 6，N = 1，您将永远无法达到特殊情况的0退出标准并打印。 ( 您确实意识到自己有n = 0，然后是n ++ ??? )

一旦您的 map 充满了-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 << path << endl; m = 1; path_found = false;}”位。或“if(map [m] [FOO] == 1){map [m] [FOO] =-1; path = m; path_found = true; cout << path; m = FOO;”部分，其中FOO是“blah”或“n”。

综上所述，我不得不处理更糟糕的代码(在专业情况下同样如此)。 (不经常发生，但确实会发生。)坚持下去，您会变得更好。我们都从同一个坏地方开始。练习，不断提问，您会有所进步。



在这里回应评论...

The only reason I had the special 0 case in there is because it was just hanging when it reached 0 because that row is empty and it stayed in an endless loop.

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

When I compile and run it i get the output I described, not what you get.

我将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 );

也许您的输入条件不同？

I don't understand why it would reach m=6 n=1, other than [6][0], the rest of the row is 0s.

下面的代码是您的(外观有微小变化)。

N = 0出现在Line = 25。当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 ) */