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

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

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

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

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


c path adjacency-matrix
person vauge    schedule 18.03.2013    source источник
comment
36x36 не большой.   -  person Anirudh Ramanathan    schedule 18.03.2013
comment
посмотрите en.wikipedia.org/wiki/A *. Следуйте указаниям, завершите поиск, в конце концов вы наткнетесь на математику и, возможно, на какой-то код для нее.   -  person YvesLeBorg    schedule 18.03.2013
comment
Это широко известно как проблема коммивояжера. Вы можете узнать больше об этом и решениях в Википедии: en.wikipedia.org/wiki/Travelling_salesman_problem   -  person Ed Rowlett-Barbu    schedule 18.03.2013
comment
@Zadirion: нет, коммивояжер - совсем другая проблема.   -  person n. 1.8e9-where's-my-share m.    schedule 18.03.2013

Ответы (2)


arrow_upward
1
arrow_downward

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

Итак, вам понадобится:

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

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

person unwind    schedule 18.03.2013
comment
Флаг исследован / неисследован может понадобиться для планирования пути. - person Clifford; 18.03.2013

arrow_upward
1
arrow_downward

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

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

person Michael Aquilina    schedule 18.03.2013