кратчайший путь через лабиринт

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


java graph shortest-path maze
person Zieklecknerizer    schedule 27.07.2010    source источник
comment
Вы можете использовать матрицу смежности или список массивов (список смежности). Не уверен, что вы имели в виду под правилом левой руки, но я полагаю, что алгоритм Дейкстры сработает.   -  person Enrico Susatyo    schedule 27.07.2010
comment
Не все лабиринты можно решить с помощью правила левой руки. Тесей ошибался.   -  person Borealid    schedule 27.07.2010
comment
@Borealid: Все идеальные лабиринты могут; Я предполагаю, что ОП имеет в виду ...   -  person Dagg Nabbit    schedule 27.07.2010
comment
lol, да, я знаю, что не все лабиринты могут быть решены с помощью правила левой руки (петель), но лабиринты, которые мы используем, не имеют петель и могут быть решены с помощью правила левой руки.   -  person Zieklecknerizer    schedule 27.07.2010

Ответы (1)


arrow_upward
2
arrow_downward

Попробуйте что-то вроде этого, должно работать:

0 - create an empty "solution path" stack of location objects.

1 - if current position is maze exit, return "solution path" stack.

2 - wall in front? turn left and repeat 2, else continue to 3.

3 - if current position is at top of "solution path" stack, 
       pop it off of the stack
       else push it onto the stack 

4 - move forward.

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

person Dagg Nabbit    schedule 27.07.2010
comment
вау, на самом деле это хорошая идея, вам не нужно использовать график, чтобы найти кратчайший путь. - person Zieklecknerizer; 27.07.2010
comment
Шаг 2 не совсем правильный, следует повернуть налево, даже если вы можете идти прямо ... повернуть налево или пойти прямо, или повернуть направо и толкнуть, или вернуться и хлопнуть ... пора бежать, нет времени обновлять его :) - person Dagg Nabbit; 27.07.2010
comment
да, идея, которая у вас есть, работает, к сожалению, мне нужно найти кратчайший путь с использованием графиков и алгоритма diijkstas ... любые идеи, как это сделать, мне как-то в недоумении. Я подумал, что, может быть, я смогу настроить граф, добавляя ребро каждый раз, когда программа достигает пересечения. затем каждый раз, когда вы перемещаетесь между этим местом и другим перекрестком. но это не работает ... возможно, я не реализую его правильно или что-то в этом роде. (не очень разбираюсь в графах, ха-ха), я добавлю код, чтобы показать, что я делаю, если я добьюсь прогресса! - person Zieklecknerizer; 27.07.2010