Нахождение кратчайшего пути в лабиринте

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, так что это не похоже на матрично-ориентированную задачу. Вам дана конечная комната, и вы должны найти кратчайший путь из начальной комнаты (сравнивая названия комнат). Результат должен быть «таким», как:

Начало: Кухня

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

Путь: Кухня, Гостиная, Коридор, Спальня, Туалет

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

Могут ли некоторые из вас, ребята из CS, помочь мне? Спасибо

Answer 1

Вы ищете BFS .

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

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

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

Answer 2

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