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

Question

Я любитель программист, который учится программировать. я никогда не имел какие-либо компьютерные курсы науки, так что я несладко с этой тривиальной задачей:

class Room { 
    String name; 
    ArrayList<Room> neighbors = new ArrayList<Room>(); 

    // constructor with name 
    // getters 
    void addNeighbor(Room room) { 
     neighbors.add(room); 
    } 
} 

class Finder { 
    void findShortestPath(Room start, Room end) { 
     // ? 
    } 
} 

В каждом номере есть несколько соседей. Более 4, так что это не похоже на матричную задачу. Вам предоставляется конечная комната, и вы должны найти кратчайший путь из стартовой комнаты (сравнивая названия комнат). Результат должен быть "путь", как:

Start: кухня

Конец: Туалет

Путь: Кухня, гостиная, коридор, спальня, туалет

Я думаю, что я должен использовать некоторые рекурсии для комнаты, и я думаю, что я должен сэкономить, где я уже был в каком-то штабеле. Но я не знаю, как начать.

Может ли кто-нибудь из вас, ребята, помочь мне? Спасибо

Answer 1

Вы ищете BFS.

В вашем случае график G = (V,E) фактически V= { all rooms } и E = {(u,v), (v,u) | u and v are neighboring rooms }

Обратите внимание, что вы не заботитесь вы не имеете все ребра [соседей] до начала алгоритм - вы знаете, как рассчитать соответствующий набор краев [и комнат] на лету, используя поле neighbors.
Это верно, так как каждый «край», который вам нужно использовать для вашего пути, был «обнаружен», когда вы обнаружили комнату, которая ближе к пути к источнику.

Вы можете посмотреть this post - как вы можете найти фактический путь после запуска BFS.

Answer 2

Вы хотите написать поиск по ширине. На эту тему имеется много ресурсов.