Самый короткий путь для гигантского лабиринта (ОГРОМНЫЙ)

Question

Мне нужно решить задачу алгоритма кратчайшего пути (в C).

В основном мне предоставляется файл, который содержит общее количество строк и столбцов (разреженной) матрицы, количество ненулевых записей (называемых дверями) и, наконец, положение и значение этих записей (строка, столбец, стоимость). В этом лабиринте я должен узнать «самый дешевый» путь от входа (0,0) к любой другой точке (позиция также читается из файла). Каждый раз, когда я пересекаю одну дверь, стоимость увеличивается, а ячейки, которые 0, ничего не стоят.

Есть несколько правил, которые вы не можете пройти через две или более двери подряд, а некоторые двери, значение которых -1, не могут быть пересечены. в конце концов мне приходится печатать положение дверей, через которые я проходил прогиб (те, которые указаны в файле). Неважно, сколько пустых ячеек я пересек.

Во всяком случае, проблема здесь заключается в том, что матрица может быть 10⁵ * 10⁵ или больше ... Я хранила не ноль записей в то, что называется разреженная матрица, я предполагаю, и это работает:

typedef struct node { 
    struct node* down; 
    struct node* right; 

    long int PL, PC, PV; 
}node ; 

typedef struct _Mat{ 
    long int NL, NC,P,x,y; //Number of lines,columns,non zero cells, and position of destination 
    node** rowList; 
    node** colList;   
}Mat 

Дело в том, что мне трудно понять, что делать дальше. С такой структурой я не думаю, что смогу решить лабиринт.

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

Если это лучшее решение, как его реализовать? Или я совершенно неправ? Является ли моя структура данных бесполезной?

Answer 1

Может быть, A * может помочь вам:

http://www.policyalmanac.org/games/aStarTutorial.htm

Этот алгоритм может найти оптимальный путь в графе, который вы можете преобразовать ваш лабиринт.