C中的分段错误（递归永无止境）

Question

我正在尝试解决这个问题：

Given a Maze, it desired to find a path from a given starting position to the location with cheese (target position). Maze is visualized as a rectangular grid containing walls (represented as 1) or free ways (represented as 0). The program must print a path that starts from starting location to the ending location. The target location will have value 9 stored in it. In this program, it is assumed that cyclic paths are not possible in the grid. (You need not check for cyclic paths.)

这就是我正在做的事情：

#include<stdio.h>

typedef struct Maze
{
    int ** values;
    int size;
} Maze;

int traverse (Maze M, int n, int posi, int posj, char **path_so_far,
        int past_i, int past_j)
{
    int k;
    printf("Hello\n");
    int i=0;
    int temp;  

    if (M.values[posi][posj] == 9)
    {
        path_so_far[i][0] = posi + '0';
        path_so_far[i][1] = posj + '0';
        path_so_far[i][2] = '[=10=]';
        printf("%s\n", path_so_far[i]); 
        i++;
        return 1;    
    }
    else if (posi - 1 >= 0 && M.values[posi - 1][posj] != 1
            && posi - 1 != past_i)
    {      
        temp = traverse(M, n, posi - 1, posj, path_so_far, past_i, past_j);
        if (temp == 1)
        {
            path_so_far[i][0] = posi + '0';
            path_so_far[i][1] = posj + '0';
            path_so_far[i][2] = '[=10=]';      
            printf("%s\n", path_so_far[i]);               
            i++;
            return 1;
        }
    }
    else if (posi + 1 < n && M.values[posi + 1][posj] != 1 && posi + 1 != past_i)
    {
        temp = traverse(M, n, posi + 1, posj, path_so_far, past_i, past_j);
        if (temp == 1)
        {
            path_so_far[i][0]=posi+'0';
            path_so_far[i][1]=posj+'0';
            path_so_far[i][2]='[=10=]';  
            printf("%s\n",path_so_far[i]);                    
            i++;
            return 1;
        }
    }
    else if(posj - 1 >=0 && M.values[posi][posj - 1] !=1 && posj - 1 != past_j)
    { 
        temp = traverse(M, n, posi, posj - 1, path_so_far, past_i, past_j);
        if(temp==1)
        {
            path_so_far[i][0] = posi + '0';
            path_so_far[i][1] = posj + '0';
            path_so_far[i][2] = '[=10=]';   
            printf("%s\n", path_so_far[i]);                  
            i++;
            return 1;
        }
    }
    else if (posj + 1 < n && M.values[posi][posj + 1] != 1 && posj + 1 != past_j)
    { 
        temp = traverse(M, n, posi, posj + 1, path_so_far, past_i, past_j);
        if(temp == 1)
        {
            path_so_far[i][0] = posi + '0';
            path_so_far[i][1] = posj + '0';
            path_so_far[i][2] = '[=10=]';     
            printf("%s\n", path_so_far[i]);                   
            i++;
            return 1;
        }
    }
    else
    {
        return 0;
    }                     
}

Maze M 已被处理，即它在另一个函数中初始化，此处未显示。我正在使用参数 (M, 0, 0, 0, path, 0, 0) 调用 traverse，但它会产生分段错误。我尝试添加 printf("Hello\n")，如我代码的第 10 行所示，以查看错误发生的位置；它多次打印 "Hello"，最后给出 segmentation fault。我做错了什么？

Answer 1

你似乎在使用参数 past_i 和 past_j 来避免重复返回，但是当你递归时，你没有像这样的方案所要求的那样传递先前位置的坐标有效。例如，这似乎...

temp = traverse(M, n, posi - 1, posj, path_so_far, past_i, past_j);

...应该是...

temp = traverse(M, n, posi - 1, posj, path_so_far, posi, posj);

。如果不这样做，您可能（并且确实）会在两个位置之间来回卡住（看起来可能在 0,1 和 1,1 之间）。您的代码还有其他问题，例如没有正确记录路径，但分段错误可能是由于递归深度足以耗尽堆栈 space.

Answer 2

不是所有路径都在traverse()return一个值。每个包含

的代码块

if(temp == 1)
    {
    ...
    return 1;
    }

将无法return 任何函数值，当

(temp != 1)

您必须在您的编译器上启用所有警告...尤其是当事情不工作时。

Answer 3

您的代码设计中存在一些重要错误。其中之一是 i 变量使用（见我的评论）。另一种是打印路径步骤的方法：首先，从递归 traverse 打印第 i 步 after you return 是错误的（因为所有后面的步骤已经在递归中打印出来了！）；但是你也不能在之前递归打印它（因为你不知道你是否走在正确的道路上）。那么，该怎么做呢？

那么，您应该在 path_so_far[i] 中标记下一步，然后进入递归。您还需要将递增的步骤编号 i+1 传递给递归步骤，以便函数始终知道它正在执行哪个步骤，以及它应该填充 path_so_far 的哪一项。

当你到达目标点时，你只需打印整个累积的 path_so_far，这是目前的最终路径，然后 return 1 表示成功。此结果向上渗透递归，最终导致计算结束。

另一方面，如果您发现自己没有进一步行动的可能，那么您 return 0 就失败了。递归的这个结果 traverse 应该会让你在当前级别测试另一种可能性。

所以：

int traverse(Maze M, int n, int posi, int posj,char **path_so_far, int i)
{
    int temp;
    if(M.values[posi][posj]==9)  // target found
    {
        int j;                   // print the complete path
        for(j=0; j<i; j++)
            printf("%s\n",path_so_far[j]);
        return 1;
    }

    // mark the current position as 'visited'

    M.values[posi][posj] = 2;

    // try next possible move
    // test if adjacent cell is empty or is target

    if(posi-1>=0 && (M.values[posi-1][posj]==0 || M.values[posi-1][posj]==9))
    {      
        path_so_far[i][0]=posi-1+'0';
        path_so_far[i][1]=posj+'0';
        path_so_far[i][2]='[=10=]';      
        temp=traverse(M,n,posi-1,posj,path_so_far,i+1);
        if(temp==1)
            return 1;
    }

    if(posi+1<n && (M.values[posi+1][posj]==0 || M.values[posi+1][posj]==9))
    {      
        path_so_far[i][0]=posi+1+'0';
        path_so_far[i][1]=posj+'0';
        path_so_far[i][2]='[=10=]';      
        temp=traverse(M,n,posi+1,posj,path_so_far,i+1);
        if(temp==1)
            return 1;
     }

     // similary for posj-1 and posj+1...

    if(posj-1>=0 && (M.values[posi][posj-1]==0 || M.values[posi][posj-1]==9))
    {
        ...
    }

    if(posj+1<n && (M.values[posi][posj+1]==0 || M.values[posi][posj+1]==9))
    {
        ...
    }

    // none of the tested paths returned success...
    // mark the current position as no longer 'visited'

    M.values[posi][posj] = 0;

    //return the failure status

    return 0;
}

C中的分段错误（递归永无止境）

Segmentation fault (recursion never ending) in C

c

recursion

maze

backtracking