Как я могу изменить алгоритм поиска в ширину, чтобы также включить путь решения?

Question

У меня в книге следующий псевдокод для поиска в ширину:

function breadth_first_search:
    begin
        open := [Start]
        closed := [];
        while open != [] do
            begin
                remove leftmost state from open, call it X;
                    if X is a goal then return SUCCESS
                        else begin
                            generate children of X;
                            put X on closed;
                            discard children of X if already on open or closed;
                            put remaining children on right end of open;
                        end
            end
       return FAIL;
    end

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

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

Answer 1

Установите Parent[childNode] = currentNode при постановке в очередь каждого узла (при установке Visible[Node] = 1).

Затем рекурсивно ищите массив Parent, начиная с нужного вам узла, и добавляйте каждый путь, который вы видите в массиве Parent, к пути. Parent[root] равно nil, и рекурсия на этом остановится.

Answer 2

Есть ли возможность изменить древовидную структуру? Если это так, вы можете добавить указатель parent в каждом узле / листе, поэтому, когда вы найдете решение, вы переходите по указателям от родителей до корня.