Рекурсия в древовидной структуре

Question

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

Параметры задачи:

• Лабиринт, представленный в матрице, который имеет несколько способов добраться до одной и той же конечной точки
• Начальная точка

Используемый язык:

• F #

Вывод кода:

████████████████████
█     █           ██
█ ███ ███ █████ █ ██
█   █   █   █   █ ██
█ █ █ █ █ █ █ ███ ██
█     █Sxxxx  █   ██
█ █████ █ █x███ █ ██
█     █   █xxx█   ██
█ █ █ ███████x██████
█ █ █   █   █x    ██
█ █ ███ █ █ █x███ ██
█   █   █ █  x█   ██
█ ███ ███ █ █x█ █ ██
█            x█   ██
███ █████████x███ ██
███ █     █xxx█ █ ██
███ █ █ █ █x███ █ ██
███   █ █xxx█     ██
█████████x██████████
█████████E██████████

#: Стены
: Пути
E: Конечная точка
S: Начальная точка

Часть кода:

let rec dfs(x,y,path,visited) =
        let rec checkVisited point visited = 
            match visited with
            | [] -> false
            | (x,y)::xs -> if point = (x,y) then true else checkVisited point xs
        let adjacents = [(x,y+1);(x+1,y);(x,y-1);(x-1,y)]
        for point in adjacents do
            if point = this.endPoint then
                this.solutionPath <- path
            else
                if checkVisited point visited = false && this.checkPoint point && this.isWall point = false then
                    dfs(fst(point),snd(point),(path@[point]),(visited@[(x,y)]))

Это другой способ (более оптимизированный) поиска решения в лабиринте

let rec dfs(x,y,path) =
            // setting the point in the matrix visited (setting it to 'false')
            matrix.[y].[x] <- (fst(matrix.[y].[x]),false)
            // getting the adjacents of the point
            let adjacents = [(x,y+1);(x+1,y);(x,y-1);(x-1,y)]
            // iterate the adjacents
            for (x1,y1) in adjacents do
                // if the adjacent is the end point set the soultion path
                if (x1,y1) = this.endPoint then
                    this.solutionPath <- path
                else
                    // else check if the point is in the matrix and is not yet visited
                    if this.checkPoint(x1,y1) && snd(matrix.[y1].[x1]) <> false && this.isWall(x1,y1) = false then
                        // execute recursively the method in the point and add the current poisition to the path
                        dfs(x1,y1,((x1,y1)::path))
        dfs(x,y,[])

Я сделал это! если у вас возникнут проблемы, я помогу вам (даже на других языках)!

Answer 1

Ваш текущий подход выглядит в основном хорошо. Но поскольку вы вначале выполняете глубокий поиск, основная проблема, с которой вы столкнулись, заключается в том, что ничто не мешает вам застрять, пробуя бесконечно длинные пути, например [(1,1);(1,2);(1,1);...], вместо того, чтобы идти к более продуктивным путям. Чтобы избежать этого, вы можете либо отсканировать путь, чтобы увидеть, есть ли в нем предложенная следующая точка (которая занимает самое большее линейное время в длине списка, что может подойти для небольших задач), либо пропустить набор посещенных точек. в качестве дополнительного аргумента для рекурсивной функции (которая должна позволять более быстрые запросы членства).

Другая проблема, с которой вы сталкиваетесь, заключается в том, что у вас нет никакого способа объединить результаты различных ветвей, которые вы могли бы использовать. Один простой подход состоит в том, чтобы изменить тип возвращаемого значения вашей внутренней функции на тип параметра, и вернуть Some(path) из верхней части if и переписать else на что-то более похожее на

[x, y+1
 x, y-1
 x+1, y
 x-1, y]
|> List.tryPick (fun (x',y') -> if this.checkPoint(x',y') then 
                                    sol(x', y', (x,y)::path)
                                else None)

Это рекурсивная попытка каждого возможного направления по очереди и возврат того, что является первым успешным. Это не обязательно вернет кратчайший путь, потому что это поиск в глубину. Вы также можете легко создать вариант, который возвращает список всех возможных путей вместо использования опции (самое большое изменение будет использовать List.collect вместо List.tryPick), и в этом случае вы можете выбрать самое короткое решение из списка, если Вы хотели, хотя это потребовало бы много промежуточных вычислений.

Более сложным изменением было бы переключение на поиск в ширину вместо поиска в глубину, что позволило бы вам очень легко вернуть кратчайший путь. , Концептуально, вот как один из подходов к этому состоит в том, чтобы отслеживать кратчайший путь ко всем «видимым» точкам (начиная с [S,[]], вместе с набором точек, чьи дети еще не исследованы (снова начиная с просто *). 1014 *). Затем, пока есть точки, которые нужно исследовать, соберите всех их отдельных потомков, для каждого, у которого еще нет известного пути, добавьте путь и поместите его в следующий набор детей для исследования.