algorithm - 迷宫程序时间复杂度

Question

此处迷宫问题的实际时间复杂度是多少？

是 O(4 ^ (n ^ 2 ) ) (因为分支 ^ 深度)还是 O(n ^ 2) (因为像 dfs 在最坏的情况下会遍历矩阵)。我做了一些搜索并得到了这两种类型的答案。谁能给出这些 2 倍复杂度可实现代码之间的区别或示例？ code2 的时间复杂度是 O(n ^ 2) 而第一个是 O(4 ^ (n ^ 2 ) ) 吗？ 代码1是回溯，代码2是dfs吗？

https://www.codesdope.com/blog/article/backtracking-to-solve-a-rat-in-a-maze-c-java-pytho/

代码1

#include <stdio.h>

#define SIZE 5

//the maze problem
int maze[SIZE][SIZE] = {
    {0,1,0,1,1},
    {0,0,0,0,0},
    {1,0,1,0,1},
    {0,0,1,0,0},
    {1,0,0,1,0}
};

//matrix to store the solution
int solution[SIZE][SIZE];

//function to print the solution matrix
void printsolution()
{
    int i,j;
    for(i=0;i<SIZE;i++)
    {
        for(j=0;j<SIZE;j++)
        {
            printf("%d\t",solution[i][j]);
        }
        printf("\n\n");
    }
}

//function to solve the maze
//using backtracking
int solvemaze(int r, int c)
{
    //if destination is reached, maze is solved
    //destination is the last cell(maze[SIZE-1][SIZE-1])
    if((r==SIZE-1) && (c==SIZE-1))
    {
        solution[r][c] = 1;
        return 1;
    }
    //checking if we can visit in this cell or not
    //the indices of the cell must be in (0,SIZE-1)
    //and solution[r][c] == 0 is making sure that the cell is not already visited
    //maze[r][c] == 0 is making sure that the cell is not blocked
    if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0)
    {
        //if safe to visit then visit the cell
        solution[r][c] = 1;
        //going down
        if(solvemaze(r+1, c))
            return 1;
        //going right
        if(solvemaze(r, c+1))
            return 1;
        //going up
        if(solvemaze(r-1, c))
            return 1;
        //going left
        if(solvemaze(r, c-1))
            return 1;
        //backtracking
        solution[r][c] = 0;
        return 0;
    }
    return 0;

}

int main()
{
    //making all elements of the solution matrix 0
    int i,j;
    for(i=0; i<SIZE; i++)
    {
        for(j=0; j<SIZE; j++)
        {
            solution[i][j] = 0;
        }
    }
    if (solvemaze(0,0))
        printsolution();
    else
        printf("No solution\n");
    return 0;
}

代码2

变化

int visited[SIZE][SIZE];
int solvemaze(int r, int c)
{
    //if destination is reached, maze is solved
    //destination is the last cell(maze[SIZE-1][SIZE-1])
    if((r==SIZE-1) && (c==SIZE-1))
    {
        solution[r][c] = 1;
        return 1;
    }
    //checking if we can visit in this cell or not
    //the indices of the cell must be in (0,SIZE-1)
    //and solution[r][c] == 0 is making sure that the cell is not already visited
    //maze[r][c] == 0 is making sure that the cell is not blocked
    if(r>=0 && c>=0 && r<SIZE && c<SIZE && visited[r][c] == 0 && maze[r][c] == 0)
    {
    visited[r][c] = 1;
        //if safe to visit then visit the cell
        solution[r][c] = 1;
        //going down
        if(solvemaze(r+1, c))
            return 1;
        //going right
        if(solvemaze(r, c+1))
            return 1;
        //going up
        if(solvemaze(r-1, c))
            return 1;
        //going left
        if(solvemaze(r, c-1))
            return 1;
        //backtracking
        solution[r][c] = 0;
        return 0;
    }
    return 0;

}

Answer 1

我还没有详细考虑过，但这里是我开始讨论的想法。

考虑以下迷宫:

0 0 0 0 .... 0 0 0 0 0
0 1 1 1 .... 1 1 1 1 0
0 0 0 0 .... 0 0 0 1 0
.                    .
.                    .
.                    .
0 0 0 0 .... 0 0 0 1 0

你的算法会先往下走，然后尝试每一种可能性来填充下面的方 block 。这显然是指数级的。所以该算法显然不在 O(n^2) 中。

O(4^(n^2)) 似乎是一个有效的上限，但我敢肯定，这不是最低上限。例如，你不能后退，所以你在每个位置只有 3 个选择。