Алгоритм искусственного интеллекта для нахождения кратчайшего пути в лабиринте может использовать искусственный аналог нейронов решётки. 12 Эти клетки входят в сеть мозга, обеспечивающую навигацию у всех млекопитающих, включая человека. 1

Учёные разработали две искусственные рекуррентные нейросети, в которых связи между элементами образуют направленную последовательность. 2 То есть программа использует свои предыдущие шаги, чтобы спланировать следующее действие, то есть реализует собственную память. 2

Также для поиска кратчайшего пути в лабиринте можно использовать вариацию алгоритма Дейкстры. 3 В нём сохраняются и обновляются три структуры данных: 3

1. tentative — карта предварительного пути от начальной точки до конечной позиции. 3 Путь называется предварительным, поскольку это самый короткий известный на данный момент путь, его можно улучшить. 3
2. certain — множество точек, для которых путь, определяемый картой tentative, является кратчайшим из возможных. 3
3. candidates — куча, составленная позициями-кандидатами, по которым может пройти путь. 3 Ключ сортировки — длина пути. 3

На каждом шаге алгоритм выполняет следующие действия: 3

1. Выталкивает позицию-кандидата из кучи candidates. 3
2. Добавляет кандидата в множество certain. 3
3. Находит кратчайший известный путь к текущему кандидату. 3
4. Для каждого из ближайших соседей текущего кандидата рассматривает, даёт ли проход через кандидата более короткий путь, чем текущий путь tentative. 3 Если это так, обновляет путь tentative и кучу candidates этим новым путём. 3

Перечисленные шаги выполняются в цикле до тех пор, пока в множество certain не попадёт позиция пункта назначения. 3 Результатом алгоритма является путь, состоящий из точек, перечисленных в certain, который теперь точно является кратчайшим из возможных путей. 3