Рубрики

Программа Python для крыс в лабиринте | Откат-2

Мы обсудили проблему с возвратом и туром Найта в Сете 1 . Давайте обсудим Крысу в Лабиринте как еще одну примерную проблему, которую можно решить с помощью Backtracking.

Лабиринт задается в виде N * N двоичной матрицы блоков, где исходный блок является самым верхним левым блоком, т. Е. Лабиринт [0] [0], а целевой блок является самым правым нижним блоком, т. Е. Лабиринт [N-1] [N-1] , Крыса начинается с источника и должна достигнуть места назначения. Крыса может двигаться только в двух направлениях: вперед и вниз.
В матрице лабиринта 0 означает, что блок является тупиком, а 1 означает, что блок может использоваться на пути от источника к месту назначения. Обратите внимание, что это простая версия типичной проблемы лабиринта. Например, более сложная версия может заключаться в том, что крыса может двигаться в 4 направлениях, а более сложная версия может иметь ограниченное количество ходов.

Ниже приведен пример лабиринта.

 Gray blocks are dead ends (value = 0). 

Ниже приведено двоичное матричное представление вышеуказанного лабиринта.

                {1, 0, 0, 0}
                {1, 1, 0, 1}
                {0, 1, 0, 0}
                {1, 1, 1, 1}

Далее идет лабиринт с выделенным путем решения.

Ниже приведена матрица решения (вывод программы) для вышеуказанного входного матрицы.

                {1, 0, 0, 0}
                {1, 1, 0, 0}
                {0, 1, 0, 0}
                {0, 1, 1, 1}
 All enteries in solution path are marked as 1.

# Python3 программа для решения Rat in Maze
# проблема с использованием возврата

  
# Размер лабиринта

N = 4

  
# Полезная функция для печати решения матрицы соль

def printSolution( sol ):

      

    for i in sol:

        for j in i:

            print(str(j) + " ", end ="")

        print("")

  
# Полезная функция для проверки правильности x, y
# индекс для N * N Maze

def isSafe( maze, x, y ):

      

    if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1:

        return True

      

    return False

  
"" "Эта функция решает проблему лабиринта с помощью Backtracking.

    Для решения проблемы в основном используется solveMazeUtil (). Это

    возвращает false, если путь невозможен, в противном случае возвращает

    true и печатает путь в виде 1с. пожалуйста, обратите внимание

    что может быть более одного решения, эта функция

    печатает одно из выполнимых решений. «»»

def solveMaze( maze ):

      

    # Создание 4 * 4 2-D списка

    sol = [ [ 0 for j in range(4) ] for i in range(4) ]

      

    if solveMazeUtil(maze, 0, 0, sol) == False:

        print("Solution doesn't exist");

        return False

      

    printSolution(sol)

    return True

      
# Рекурсивная функция полезности для решения проблемы лабиринта

def solveMazeUtil(maze, x, y, sol):

      

    # if (x, y является целью) вернуть True

    if x == N - 1 and y == N - 1:

        sol[x][y] = 1

        return True

          

    # Проверьте, действителен ли лабиринт [x] [y]

    if isSafe(maze, x, y) == True:

        # пометить x, y как часть пути решения

        sol[x][y] = 1

          

        # Двигаться вперед в направлении х

        if solveMazeUtil(maze, x + 1, y, sol) == True:

            return True

              

        # Если движение в направлении х не дает решения

        # затем двигайтесь вниз в направлении у

        if solveMazeUtil(maze, x, y + 1, sol) == True:

            return True

          

        # Если ни одно из вышеперечисленных движений не сработало,

        # BACKTRACK: снять отметку с x, y как часть пути решения

        sol[x][y] = 0

        return False

  
# Программа драйвера для проверки вышеуказанной функции

if __name__ == "__main__":

    # Инициализация лабиринта

    maze = [ [1, 0, 0, 0],

             [1, 1, 0, 1],

             [0, 1, 0, 0],

             [1, 1, 1, 1] ]

               

    solveMaze(maze)

  
# Этот код предоставлен Shiv Shankar

Выход:

1 0 0 0 
1 1 0 0 
0 1 0 0 
0 1 1 1

Пожалуйста, обратитесь полную статью о крысе в лабиринте | Backtracking-2 для более подробной информации!

Рекомендуемые посты:

Программа Python для крыс в лабиринте | Откат-2

0.00 (0%) 0 votes