如何优化广度搜索算法来解决更大的迷宫

Question

我正在一个需要解决迷宫的项目中，并将解决方案打印在标准输出上：

从此：

对此：

为此，我使用了A *（astar）算法，没有成本问题，因为自从迷宫解决以来，我不在乎寻找最短路径。因此，我只有两个链接列表，其中包含在地图上位置的节点。

无论如何，现在它可以正常工作，但是我想改善大型迷宫的表现，因为在500x500迷宫上花费超过10秒的时间，而在1000x1000迷宫上花费整整一分钟的时间，我已经做了一些事情，例如优化我的add_node函数或in_list函数的调用，该函数搜索某个节点是否已经在关闭列表中，但是，即使它的速度增加了一倍或三倍，这显然还不够，A *算法应该更快。

这是我在C语言中对程序的实现：

//my header's structures:
typedef struct node_s
{
    int x;
    int y;
} node_t;

typedef struct maze_s
{
    char **map;
    int dim[2];
    node_t start;
    node_t objective;
    node_t *current;
    bool states[4];
} maze_t;

typedef struct linked_list_s
{
    node_t node;
    node_t *parent;
    struct linked_list_s *next;
} linked_list_t;```

//And here The Most Important Utils Functions:
void in_closed(linked_list_t *closed_list, maze_t *maze)
{
    linked_list_t *tmp = closed_list;
    node_t *crt = maze->current;

    if (!tmp)
        return;
    while (tmp) {
        if (tmp->node.x == crt->x + 1 && tmp->node.y == crt->y) {
            maze->states[0] = true;
        }
        if (tmp->node.x == crt->x && tmp->node.y == crt->y + 1) {
            maze->states[1] = true;
        }
        if (tmp->node.x == crt->x && tmp->node.y == crt->y - 1) {
            maze->states[2] = true;
        }
        if (tmp->node.x == crt->x - 1 && tmp->node.y == crt->y) {
            maze->states[3] = true;
        }
        tmp = tmp->next;
    }
}

linked_list_t *add_node(linked_list_t *list, node_t node, node_t *parent)
{
    linked_list_t *new = malloc(sizeof(linked_list_t));

    new->node = node;
    new->parent = parent;
    new->next = list;
    return (new);
}

linked_list_t *remove_node(linked_list_t *list, node_t *node)
{
    linked_list_t *head = list;

    if (list->node.x == node->x && list->node.y == node->y) {
        list = list->next;
        return (list);
    }
    while (list->next) {
        if (list->next->node.x == node->x && list->next->node.y == node->y) {
            list->next = list->next->next;
            return (head);
        } else {
            list = list->next;
        }
    }
    return (NULL);
}

//And then the main algorithm (all the functions that I didn't show were not important for my problem) :

linked_list_t *check_neighbour(int neighbour, maze_t *maze,
                    linked_list_t *list, linked_list_t *closed_list)
{
    node_t *crt = maze->current;

    if (neighbour == 1 && crt->x + 1 < maze->dim[0] && !maze->states[0]
        && maze->map[crt->x + 1][crt->y] == '*') {
        list = add_node(list, (node_t){crt->x + 1, crt->y}, crt);
    }
    if (neighbour == 2 && crt->y + 1 < maze->dim[1] && !maze->states[1]
        && maze->map[crt->x][crt->y + 1] == '*') {
        list = add_node(list, (node_t){crt->x, crt->y + 1}, crt);
    }
    if (neighbour == 0 && crt->y > 0 && !maze->states[2]
        && maze->map[crt->x][crt->y - 1] == '*') {
        list = add_node(list, (node_t){crt->x, crt->y - 1}, crt);
    }
    if (neighbour == 3 && crt->x > 0 && !maze->states[3]
        && maze->map[crt->x - 1][crt->y] == '*') {
        list = add_node(list, (node_t){crt->x - 1, crt->y}, crt);
    }
    return (list);
}

void end(maze_t *maze, linked_list_t *closed_list)
{
    linked_list_t *tmp = closed_list;
    bool cond = true;

    for (int x = maze->objective.x, y = maze->objective.y; tmp->next;) {
        if (tmp->node.x == x && tmp->node.y == y) {
            maze->map[x][y] = 'o';
            x = tmp->parent->x;
            y = tmp->parent->y;
            closed_list = remove_node(closed_list, &tmp->node);
            tmp = closed_list;
            cond = false;
        }
        if (cond) {
            tmp = tmp->next;
        } else {
            cond = true;
        }
    }
    maze->map[0][0] = 'o';
}

linked_list_t *solve_maze(maze_t *maze, linked_list_t *list,
                                linked_list_t *closed_list)
{
    while (list) {
        if (list->node.x == maze->objective.x
            && list->node.y == maze->objective.y)
            return (closed_list);
        maze->current = &list->node;
        closed_list = add_node(closed_list, list->node, list->parent);
        in_closed(closed_list, maze);
        for (int i = 0; i < 4; i++)
            list = check_neighbour(i, maze, list, closed_list);
        for (int i = 0; i < 4; i++)
            maze->states[i] = false;
        list = remove_node(list, maze->current);
    }
    return(NULL);
}

int solver(char **av)
{
    int *dim = get_dimensions(av[1]);
    maze_t maze = {.dim = {dim[0], dim[1]}, .map = get_map(av[1], dim),
        .start = {0, 0}, .objective = {dim[0] - 1, dim[1] - 1}, .states =
        {false, false, false, false}};
    linked_list_t *list = get_open_list(&maze);
    linked_list_t *closed_list = NULL;

    if (maze.map[0][0] == 'X' || maze.map[dim[0] - 1][dim[1] - 1] == 'X')
        return (printf("no solution found\n"));
    closed_list = solve_maze(&maze, list, closed_list);
    if (!closed_list)
        return (printf("no solution found\n"));
    closed_list = add_node(closed_list, maze.objective, &closed_list->node);
    printf("algorithm done\n");
    end(&maze, closed_list);
    printf("end finished\n");
    print_map_color(&maze);
    return (0);
}

Answer 1

如果您的整个目标只是解决一次迷宫，那么A *完全是过大的。 A *的主要优点是，很多时候您不需要查看迷宫上的一堆空间。在这种情况下，您无论如何都要将整个迷宫读取到内存中（加上您的迷宫大小仅为〜10 ^ 6平方，这非常小）。 如果仍然必须将整个网格读入内存，则解决方案将是O（n）最佳情况其中n是网格中的空格数。从外观上看，您编写了一些非常复杂的代码，可能是O（n ^ 2）或O（pathLength * n）最坏的情况。

您应该只能使用BFS。下面的代码在Java中，并且在O（n）中运行。

这是我的解决方案在10 x 10情况下的输出：

Possible
oX********
ooo*X***X*
**oX****X*
XXoX**X**X
X*ooX*****
*X*ooooooX
****X***oX
*****X**oo
*X***X***o
*****X***o
1

这是Java中的代码：

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

public class BFS {

    public static void main(String[] args) {
        int w=1000, h=1000;
        long time=System.currentTimeMillis();
        Random r=new Random();
        char[][] board=new char[w][h];
        for (int x=0; x<w; x++)
            for (int y=0; y<h; y++) 
                board[x][y]=r.nextInt(5)<1?'X':'*';

        int[] dx= {1, 0, -1, 0};
        int[] dy= {0, -1, 0, 1};
        int[][] cameFrom=new int[w][h];
        boolean[][] visited=new boolean[w][h];
        Queue<Integer> xs=new LinkedList<>(), ys=new LinkedList<>();
        xs.add(0);
        ys.add(0);
        cameFrom[0][0]=-1;
        visited[0][0]=true;
        while (!xs.isEmpty()) {
            int fromX=xs.remove(), fromY=ys.remove();
            for (int d=0; d<4; d++) {
                int nx=fromX+dx[d], ny=fromY+dy[d];
                if (nx<0||ny<0||nx>=w||ny>=h||visited[nx][ny]||board[nx][ny]=='X') continue;
                visited[nx][ny]=true;
                cameFrom[nx][ny]=d;
                xs.add(nx);
                ys.add(ny);
            }
        }
        PrintWriter out=new PrintWriter(System.out);
        if (!visited[w-1][h-1]) {
            out.println("Impossible...");
        }
        else {
            out.println("Possible");
            int x=w-1, y=h-1;
            while (cameFrom[x][y]!=-1) {
                board[x][y]='o';
                int d=cameFrom[x][y];
                x-=dx[d];
                y-=dy[d];
            }
            for (y=0; y<h; y++) {
                for (x=0; x<w; x++) out.print(board[x][y]);
                out.println();
            }
        }
        out.println(System.currentTimeMillis()-time);
        out.close();
    }

}

对于1000 x 1000的网格，此操作在0.6秒内完成，并且大部分时间用于打印输出网格。由于该图未加权，因此它也总是找到最短的路径。