Рубрики

Крыса в лабиринте | Откат-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.

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

while there are untried paths
{
   generate the next path
   if this path has all blocks as 1
   {
      print this path;
   }
}

Алгоритм возврата

If destination is reached
    print the solution matrix
Else
   a) Mark current cell in solution matrix as 1. 
   b) Move forward in the horizontal direction and recursively check if this 
       move leads to a solution. 
   c) If the move chosen in the above step doesn't lead to a solution
       then move down and check if this move leads to a solution. 
   d) If none of the above solutions works then unmark this cell as 0 
       (BACKTRACK) and return false.

Внедрение решения Backtracking

C / C ++

/ * C / C ++ программа для решения Rat in Maze с помощью задачи

   возвращение назад * /

#include <stdio.h>

  
// Размер лабиринта
#define N 4

  

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

  
/ * Вспомогательная функция для печати решения матрицы sol [N] [N] * /

void printSolution(int sol[N][N])

{

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++)

            printf(" %d ", sol[i][j]);

        printf("\n");

    }

}

  
/ * Полезная функция для проверки, является ли x, y допустимым индексом для N * N лабиринта * /

bool isSafe(int maze[N][N], int x, int y)

{

    // if (x, y вне лабиринта) возвращает false

    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)

        return true;

  

    return false;

}

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

   решает проблему с помощью solveMazeUtil (). Возвращает false если нет

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

   форма 1с. Обратите внимание, что может быть более одного решения,

   эта функция печатает одно из возможных решений. * /

bool solveMaze(int maze[N][N])

{

    int sol[N][N] = { { 0, 0, 0, 0 },

                      { 0, 0, 0, 0 },

                      { 0, 0, 0, 0 },

                      { 0, 0, 0, 0 } };

  

    if (solveMazeUtil(maze, 0, 0, sol) == false) {

        printf("Solution doesn't exist");

        return false;

    }

  

    printSolution(sol);

    return true;

}

  
/ * Рекурсивная функция полезности для решения задачи Лабиринта * /

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])

{

    // если (x, y - цель), верните true

    if (x == N - 1 && y == N - 1) {

        sol[x][y] = 1;

        return true;

    }

  

    // Проверяем, действительно ли maze [x] [y]

    if (isSafe(maze, x, y) == true) {

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

        sol[x][y] = 1;

  

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

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

            return true;

  

        / * Если движение в направлении х не дает решения, то

           Двигаться вниз в направлении y * /

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

            return true;

  

        / * Если ни одно из вышеперечисленных движений не сработало, тогда НАЗАД:

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

        sol[x][y] = 0;

        return false;

    }

  

    return false;

}

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

int main()

{

    int maze[N][N] = { { 1, 0, 0, 0 },

                       { 1, 1, 0, 1 },

                       { 0, 1, 0, 0 },

                       { 1, 1, 1, 1 } };

  

    solveMaze(maze);

    return 0;

}

Джава

/ * Java-программа для решения Rat in Maze с помощью задачи
возвращение назад * /

  

public class RatMaze {

  

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

    static int N;

  

    / * Утилита для печати матрицы решения

    sol [N] [N] * /

    void printSolution(int sol[][])

    {

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < N; j++)

                System.out.print(" " + sol[i][j] + " ");

            System.out.println();

        }

    }

  

    / * Утилита для проверки правильности значений x, y

        индекс для N * N лабиринт * /

    boolean isSafe(int maze[][], int x, int y)

    {

        // if (x, y вне лабиринта) возвращает false

        return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);

    }

  

    / * Эта функция решает проблему лабиринта, используя

    Откат. Он в основном использует solveMazeUtil ()

    решить проблему. Возвращает false если нет

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

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

    что может быть более одного решения, это

    Функция печатает одно из возможных решений. * /

    boolean solveMaze(int maze[][])

    {

        int sol[][] = new int[N][N];

  

        if (solveMazeUtil(maze, 0, 0, sol) == false) {

            System.out.print("Solution doesn't exist");

            return false;

        }

  

        printSolution(sol);

        return true;

    }

  

    / * Рекурсивная функция полезности для решения Maze

    проблема * /

    boolean solveMazeUtil(int maze[][], int x, int y,

                          int sol[][])

    {

        // если (x, y - цель), верните true

        if (x == N - 1 && y == N - 1) {

            sol[x][y] = 1;

            return true;

        }

  

        // Проверяем, действительно ли maze [x] [y]

        if (isSafe(maze, x, y) == true) {

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

            sol[x][y] = 1;

  

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

            if (solveMazeUtil(maze, x + 1, y, sol))

                return true;

  

            / * Если движение в направлении х не дает

            решение затем двигаться вниз в направлении у * /

            if (solveMazeUtil(maze, x, y + 1, sol))

                return true;

  

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

            ОБРАТНАЯ СВЯЗЬ: снять отметку с x, y как часть решения

            путь */

            sol[x][y] = 0;

            return false;

        }

  

        return false;

    }

  

    public static void main(String args[])

    {

        RatMaze rat = new RatMaze();

        int maze[][] = { { 1, 0, 0, 0 },

                         { 1, 1, 0, 1 },

                         { 0, 1, 0, 0 },

                         { 1, 1, 1, 1 } };

  

        N = maze.length;

        rat.solveMaze(maze);

    }

}
// Этот код предоставлен Abhishek Shankhadhar

python3

# 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 значения показывают путь для крысы

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

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

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

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

Крыса в лабиринте | Откат-2

0.00 (0%) 0 votes