Нахождение кратчайшего или самого длинного решения лабиринта - PullRequest
Новая
       70

Нахождение кратчайшего или самого длинного решения лабиринта

0 голосов
/ 26 января 2019

Я работаю над заданием, в котором справился с основной проблемой и изучаю упражнения по расширению.В настоящее время дана карта, и все возможные решения лабиринта указаны на сетке, которая напечатана следующим образом: 

    1 1 3 1 0 2 
    3 3 3 3 1 3 
    3 3 1 3 3 3 
    3 3 3 1 3 0 
    3 1 3 1 3 1 
    3 1 3 3 3 0

Где 0 - это пустое пространство, 1 - это стена, 2 - это стена.цель, а 3 посещаемое пространство.Задача расширения состоит в том, чтобы дать кратчайшее возможное решение лабиринту с любой заданной отправной точкой.Если отправной точкой является стена, то лабиринт не может быть решен.Это тоже хорошо.Это должно быть в состоянии работать для любого данного лабиринта.

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

В настоящее время это мой код: 

EMPTY = 0
WALL = 1
GOAL = 2
VISITED = 3


def solve(grid, x, y):
    if grid[x][y] == GOAL:
        show_grid(grid)
        return True
    elif grid[x][y] == WALL:
        return False
    elif grid[x][y] == VISITED:
        return False
    else:
       # mark as visited
       grid[x][y] = VISITED

       # explore neighbors clockwise starting by going up
       if      ((x < len(grid)-1  and solve(grid, x + 1, y))
             or (y > 0            and solve(grid, x, y-1))
             or (x > 0            and solve(grid, x-1, y))
             or (y < len(grid)-1  and solve(grid, x, y+1))):
           return True
       else:
           return False


def show_grid (grid):
    for i in range(len(grid), 0, -1):
        # print("i: ", i)
        for element in grid[i-1]:
            print (element, end=" ")
        print()


def main ():
    grid =    [[EMPTY, WALL, EMPTY, EMPTY, EMPTY, EMPTY],
               [EMPTY, WALL, EMPTY, WALL, EMPTY, WALL],
               [EMPTY, EMPTY, EMPTY, WALL, EMPTY, EMPTY],
               [EMPTY, EMPTY, WALL, EMPTY, EMPTY, EMPTY],
               [EMPTY, EMPTY, EMPTY, EMPTY, WALL, EMPTY],
               [WALL, WALL, EMPTY, WALL, EMPTY, GOAL]]

    solve(grid, 0, 0)

Расширение просит напечатать длину кратчайшего пути, где обход 1 квадрата равен 1 движению.Любая помощь с этой проблемой приветствуется.

Ответы [ 2 ]

0 голосов
/ 26 января 2019

Я согласен с ответом @ wwii: если вы изучаете все решения, просто верните длину каждого успешного пути, а затем найдите самый короткий. Это может быть достигнуто с помощью следующих изменений:

  1. изменение вашей решенной функции, чтобы она возвращала путь вместо true или false.
  2. в каждом узле вместо 3 для посещенных, вы можете указать минимальную длину от этого узла до решения (или источника), -1 для стены и узлов, которые не могут достичь решения. Узлы, которые не могут достичь решения, по сути являются стенами.

Например, 

GOAL = 'G'
WALL = 'W'
EMPTY = 'E'


def solve(grid, x, y):
    if grid[x][y] == WALL or grid[x][y].endswith(GOAL):
        return grid[x][y]

    candidates = []
    # explore neighbors clockwise starting by going down
    if x < len(grid)-1:
        candidates.append('d' + solve(grid, x + 1, y))
    if y > 0:
        candidates.append('l' + solve(grid, x, y - 1))
    if x > 0:
        candidates.append('u' + solve(grid, x - 1, y))
    if y < len(grid)-1:
        candidates.append('r' + solve(grid, x, y + 1))

    # get rid of none solutions from candidates
    candidates = [x for x in candidates if not x.endswith(GOAL)]
    if not candidates: # if no solution, it's essentially a wall
        grid[x][y] = 'W'
    else: 
        # getting shortest path
        grid[x][y] = sorted(candidates, key=lambda x: len(x))[0]

        # for longest path use code below instead of above
        # grid[x][y] = sorted(candidates, key=lambda x: len(x))[-1]
    return grid[x][y]

Если узел посещен и он достигает цели, значение в этом узле может быть чем-то вроде 'drrurG'. Это означает, что кратчайший путь идет вниз, вправо * 2, вверх, вправо, Цель. Условное обозначение направлено вниз, то есть идет вниз по строке, то есть x + 1.

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

Пища для размышлений

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

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

0 голосов
/ 26 января 2019

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

Выполните рефакторинг, чтобы функция возвращала местоположение сетки, если она жизнеспособна, и возвращаются значения из потомков экземпляра .

Ваши условия должны быть переосмыслены, и вы хотите убедиться, что все пути изучены (вверх, вниз, влево, вправо). Может быть полезно использовать тот факт, что кортеж оценивается True в условном выражении, bool((0,0)) -> True.

Наконец, вы можете:

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

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

Вы также можете просматривать сетку в виде графика, каждая точка является узлом с ребрами для узлов вокруг нее. Вы можете сначала проанализировать сетку в графе, а затем использовать любое количество четко определенных алгоритмов для обхода графа и поиска ответов. Для древовидного решения корень будет отправной точкой для поиска. У меня нет большого опыта с использованием графиков, поэтому я не чувствую, что могу дать подробный ответ на этот вопрос - может быть, кто-то ответит с лучшим объяснением .

...