DFS解迷宫的一些想法


写在前面:私不是程序员,也不是学信科的,也只是最近开始没事的时候翻翻C语言的书。因此阁下很可能会觉得下文所述的想法很原始或是阁下早已用过了。私在此只是记录一下自己的想法。

现阶段私学C语言用的书是宋劲杉的《Linux C编程一站式学习》,里面讲深度优先搜索的时候讲的是个走迷宫问题,用1表示墙,0表示路,从左上走到右下。代码如下:

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5 

struct point { int row, col; } stack[512];
int top = 0;

void push(struct point p)
{
    stack[top++] = p;
}

struct point pop(void)
{
    return stack[--top];
}

int is_empty(void)
{
    return top == 0;
}

int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

void print_maze(void)
{
    int i, j;
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++)
            printf("%d ", maze[i][j]);
        putchar('\n');
    }
    printf("*********\n");
}

struct point predecessor[MAX_ROW][MAX_COL] = {
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
};

void visit(int row, int col, struct point pre)
{
    struct point visit_point = { row, col };
    maze[row][col] = 2;
    predecessor[row][col] = pre;
    push(visit_point);
}

int main(void)
{
    struct point p = { 0, 0 };

    maze[p.row][p.col] = 2;
    push(p);

    while (!is_empty()) {
        p = pop();
        if (p.row == MAX_ROW - 1  /* goal */
            && p.col == MAX_COL - 1)
            break;
        if (p.col+1 < MAX_COL     /* right */
            && maze[p.row][p.col+1] == 0)
            visit(p.row, p.col+1, p);
        if (p.row+1 < MAX_ROW     /* down */
            && maze[p.row+1][p.col] == 0)
            visit(p.row+1, p.col, p);
        if (p.col-1 >= 0          /* left */
            && maze[p.row][p.col-1] == 0)
            visit(p.row, p.col-1, p);
        if (p.row-1 >= 0          /* up */
            && maze[p.row-1][p.col] == 0)
            visit(p.row-1, p.col, p);
        print_maze();
    }
    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
        printf("(%d, %d)\n", p.row, p.col);
        while (predecessor[p.row][p.col].row != -1) {
            p = predecessor[p.row][p.col];
            printf("(%d, %d)\n", p.row, p.col);
        }
    } else
        printf("No path!\n");

    return 0;
}

大概意思就是每次弹出一个栈,找到周围所有的合法步骤然后把它们栈压进栈区,下一轮时再弹出最后压入的栈,如果走入死路就再次弹栈,找另外一条可能路线,直到找到迷宫的解。如果栈空了就说明无路可走,打出“No path !”。
但是找到解之后就比较麻烦。如何输出路径呢?这段代码使用的方法是建立一个predecessor数组,用来表示每个点的前趋,然后从最后一个点顺藤摸瓜往前找,逐渐打印出来。但这个predecessor数组占用的空间很大,且只能从后向前找,不便于找到其中的某个特定步骤。怎么解决这一问题呢?作者宋劲杉出了一道思考题,还问读者能够想出几种方法,可见方法是不止一种的。

在正确理解这段代码之前,私一直认为栈区中至少应该存有正确路径走过的所有的点,后来才明白这个想法是有问题的。由于每个循环开始时栈顶已经弹出了,此时如果再在这一点继续向深处找,新压入的栈就会把刚才弹出的栈顶覆盖掉,这样找到最后整个栈中在极端情况下(例如整个迷宫都没有岔路)可能一个点也不剩。此外一个循环内是4个方向均会搜索,所以如果有岔路,就会压入多个点,但弹出时只会弹出一个点,所以栈中会残留错误道路的点。

怎么修改呢?其实很容易。原来每个循环会从栈顶弹出一个栈,其实找到路径之后,完全可以把这一栈再压回去,比如这样:

int main(void)
{
    struct point p = { 0, 0 };

    maze[p.row][p.col] = 2;
    push(p);

    while (!is_empty()) {
        p = pop();
        if (p.row == MAX_ROW - 1  /* goal */
            && p.col == MAX_COL - 1)
            break;
        if (p.col+1 < MAX_COL     /* right */
            && maze[p.row][p.col+1] == 0) {
            top++;
            visit(p.row, p.col+1, p);
        } else if (p.row+1 < MAX_ROW     /* down */
            && maze[p.row+1][p.col] == 0) {
            top++;
            visit(p.row+1, p.col, p);
        } else if (p.col-1 >= 0          /* left */
            && maze[p.row][p.col-1] == 0) {
            top++;
            visit(p.row, p.col-1, p);
        } else if (p.row-1 >= 0          /* up */
            && maze[p.row-1][p.col] == 0) {
            top++;
            visit(p.row-1, p.col, p);
        }
        print_maze();
    }

    int i;
    if (!is_empty()) {
        for (i=0; i<top; i++)
            printf("(%d, %d)\n", stack[i]);
    } else
        printf("No path.\n");

    return 0;
}

如果找到了可用的路,由于有了top++,相当于仅仅是读取到栈顶的数据(而栈没有弹出),这样在搜索路径压栈的时候就不会把原来的栈顶覆盖掉,从而保证了栈中存在所有正确路径上的点。解决残留错误道路的点的问题也很容易,只需让一个循环内如果搜索到了一条可以深入的路径就停止(用else实现),否则再搜索下一条路径。如果找到死路栈会逐个弹出,直到岔路口,所以不用担心找不到正解。到最后如果迷宫存在解的话,栈中所保存的就是正确的路径。由于例子中的“栈”是一个数组(当然您可能会反驳说这个例子中stack[]并不是真正意义上的栈,“栈”在理论上应该只能访问顶端的元素,但那只是个形式问题),于是可以很容易地访问任何一步的点,输出的时候正着打反着打跳着打均可,程序中所有和predecessor有关的内容便可以删去了。

但是事实上这个办法在程序效率上是劣化而不是优化,首先虽然不需要predecessor了,但是栈空间消耗变得更大。原本栈空间的消耗和分岔路的多少有关,现在则是和路径的长度有关而与有多少岔路无关。那么栈空间的最小值应该是多大呢?私还没考虑好,但分配为整个迷宫的大小肯定是足够的。还有个问题是原来的方式由于覆盖了之前走过的路径,只保留岔路上其他方向的点,如果找到死路,弹栈后会直接跳到另外一个可能的岔路继续搜索,而修改后的方法如果找到死路,必须沿原路一步步跳回岔路口。再加上top++所用的时间,程序效率比原来要低,而且岔路越多越深入,效率上的差距越明显。

前几天看到个好玩的推,说“情人节我玩一天连连看,消灭一对是一对”。私寻思既然学了DFS和BFS,不如自己也写个文本连连看玩玩?再说吧。

另:为嘛我Tag里写C,wordpress会给自动补全成C++?

Advertisements

6 thoughts on “DFS解迷宫的一些想法

  1. int visit(int x, int y) //尝试通过(x,y)
    {
        if(x < 0 || y < 0 || MAX_ROW == x || MAX_COL == y || maze[x][y]) return 0; //墙
        if((MAX_ROW == (x+1)) && (MAX_COL == (y+1))) {printf("Goal!\n"); return 1;} //终点
    
        maze[x][y] = 2; //标记当前位置为走过
        int next = (visit(x, y+1) || visit(x+1, y) || visit(x, y-1) || visit(x-1, y)); //走下一步
        if(next) printf("(%d,%d)\n", x, y); //打印此步
        return next; //下一步的状态即为此步状态
    }
    
    int main()
    {
        if(!visit(0,0))
            printf("No path!\n");
        //printf("Hello world!\n");
        return 0;
    }
    
  2. struct point { int x, y; } stack[512];
    int len = 0;
    
    int visit(int x, int y, int l) //尝试通过(x,y),步骤为l
    {
        if(x < 0 || y < 0 || MAX_ROW == x || MAX_COL == y || maze[x][y]) return 0; //墙
        if((MAX_ROW == (x+1)) && (MAX_COL == (y+1))) return 1; //终点
    
        maze[x][y] = 2; //标记当前位置为走过
        int next = (visit(x, y+1, l+1) || visit(x+1, y, l+1) || visit(x, y-1, l+1) || visit(x-1, y, l+1)); //走下一步
        if(next){
            stack[l]= (struct point){x,y};
            if(len<l)len = l; //标记解长度
        }
        return next; //下一步的状态即为此步状态
    }
    
    int main(){
        if(visit(0,0,0)){
            int i = 0;
            while(i<=len){
                printf("(%d,%d)\n",stack[i].x,stack[i].y);
                i++;
            }
            printf("Goal!\n");
        }
        else
            printf("No path!\n");
        return 0;
    }
    
  3. 一般而言最快的方法必然是种子染色法,说白了就是BFS。
    记录路径的话,其实我觉得记录前一个节点的位置然后逆推的方式就很好了嘛。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s