Как я могу оптимизировать свой алгоритм поиска по ширине для решения больших лабиринтов

Question

Я работаю над проектом, в котором мне нужно решить лабиринт, и выводит решение на стандартный вывод:

Из этого:

Для этого:

Для этого я использовал алгоритм A * (astar), без проблем с затратами, потому что меня не волнует поиск кратчайшего пути, так как Лабиринт решен. Так что у меня просто есть два связанных списка, которые содержат узлы, которые являются позициями на карте.

В любом случае, это сейчас работает, но я хочу улучшить свое время на больших лабиринтах, потому что это занимает более 10 секунд. в лабиринтах 500x500 и более минуты в лабиринтах 1000x1000 я уже сделал несколько вещей, таких как оптимизация моей функции add_node или вызов функции in_list, которая выполняет поиск, если узел уже находится в закрытом списке, но даже если он имел удвоить или утроить скорость, этого явно недостаточно. Алгоритм * должен быть намного быстрее.

Вот моя реализация программы в 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) bestcase , где n - количество пробелов в сетке. Судя по всему, вы создали очень сложный код, который, вероятно, имеет наихудший случай O (n ^ 2) или O (pathLength * n).

Вы должны иметь возможность использовать только BFS. Код ниже находится в Java и работает в O (n).

Вот вывод моего решения на случай 10 на 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();
    }

}

Это выполняется менее чем за 0,6 секунды для сетки 1000 на 1000, и большая часть этого времени уходит на печать выходной сетки. Он также всегда находит кратчайший путь, так как график невзвешенный.