C Программирование: как найти кратчайший путь?

Question

Представьте меня 6х6 квадрат, состоящий из 36 вершин (то есть 6 вершин в строку и 6 вершин в столбец), выглядит примерно так:

• • • • • • 
• • • • • • 
• • • • • • 
• • • • • • 
• • • • • • 
• • • • • • 

Каждой вершина либо связно с 1, 2, 3 или 4 close-by vertexes - поэтому мы в основном получаем граф с вершинами и ребрами. Моя проблема заключается в следующем: я хочу, чтобы робот прошел через этот «лабиринт» краев, пока не найдет определенный объект, размещенный на некоторой вершине. Как только он обнаружит этот объект, он должен вернуться к исходной точке, используя быстрый путь .

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

Answer 1

Вы, кажется, нужно четыре бита на вершине, чтобы выразить, что любой из {вверх, вправо, вниз, влево} являются «открытыми» направления, то есть действительные двигаться.

Итак, вам нужно будет грандиозная общая сумма:

6 * 6 
----- = 18 bytes 
    2 

Чтобы сохранить все ваши данные о подключении. Трудно представить, что это становится намного более эффективным.

Answer 2

Я бы порекомендовал вам изучить алгоритм A *, который часто используется в решениях Pathfinding.

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html