Labirentteki fare algotirmasi nedir?

Bir labirent N*N olarak verilir. Bu labirentte başlangıç noktası sol en üst bölümdür. Yani [0][0] çıkış(hedef) ise en sağ alttaki [N-1][N-1] yani dizinin son elamanıdır. Fare başlangıç noktasından başlar çıkışa ulaşmaya çalışır. Fare yalnızca iki yöne hareket edebiliyor. İleriye ve aşağıya.

Labirent matrisinde 0, bloğun çıkmaz bir yol olduğu anlamına gelir ve 1, bloğun başlangıçtan hedefe giden yolda kullanılabileceği anlamına gelir. Bunun tipik Labirent probleminin basit bir versiyonu olduğunu unutmayın. Örneğin, daha karmaşık bir versiyon, farenin 4 yönde hareket edebilmesi ve daha karmaşık bir versiyonun sınırlı sayıda hareket ile olabilmesi olabilir.

Aşağıda örnek bir labirent verilmiştir.

Gri bloklar çıkmaz noktalardır (değer = 0).

Aşağıda, yukarıdaki labirentin ikili bir matris temsilidir.

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

Aşağıda vurgulanan çözüm yolu olan bir labirent var.

Yukarıdaki giriş matrisi için çözüm matrisi (programın çıktısı) aşağıdadır.

{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}
Çözüm yolundaki tüm girişler 1 olarak işaretlenir.

Geriye dönük izleme, aşamalı olarak bir çözüm oluşturmaya çalışarak sorunları özyinelemeli olarak çözmek için kullanılan algoritmik bir tekniktir.Her seferinde tek bir parçayı çözmek ve herhangi bir zamanda problemin kısıtlamalarını karşılayamayan çözümleri kaldırmak (burada zamanla arama ağacının herhangi bir seviyesine ulaşana kadar geçen süre kastedilmektedir) geri izleme işlemidir.

Yaklaşım: Bir yolu takip edecek ve yolun hedefe ulaşıp ulaşmadığını kontrol edecek özyinelemeli bir işlev oluşturun. Yol hedefe ulaşmazsa, geri dönün ve diğer yolları deneyin.

Algoritma:

1. Başlangıçta 0’larla doldurulmuş bir çözüm matrisi oluşturun.
2. Kendini tekrar eden bir fonksiyon oluşturun matrisin değerlerini alan ve çıktı olarak farenin matristeki pozisyonunu veren.[i][j]
3. Pozisyon matrisin dışındaysa veya pozisyon geçerli değilse geri dönün.
4. Pozisyon çıkışını [i] [j] 1 olarak işaretleyin ve mevcut pozisyonun hedef olup olmadığını kontrol edin. Hedefe ulaşılırsa çıktı matrisini yazdırın ve geri dönün.
5. (İ + 1, j) ve (i, j + 1) konumlarını özyinelemeli olarak arayın.
6. Pozisyonun işaretini kaldır (i, j), yani çıktı [i] [j] = 0.

Java Kodu:

/* Java program to solve Rat in
 a Maze problem using backtracking */
 
public class RatMaze {
 
    // Size of the maze
    static int N;
 
    /* A utility function to print
    solution matrix 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();
        }
    }
 
    /* A utility function to check
        if x, y is valid index for N*N maze */
    boolean isSafe(
        int maze[][], int x, int y)
    {
        // if (x, y outside maze) return false
        return (x >= 0 && x < N && y >= 0
                && y < N && maze[x][y] == 1);
    }
 
    /* This function solves the Maze problem using
    Backtracking. It mainly uses solveMazeUtil()
    to solve the problem. It returns false if no
    path is possible, otherwise return true and
    prints the path in the form of 1s. Please note
    that there may be more than one solutions, this
    function prints one of the feasible solutions.*/
    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;
    }
 
    /* A recursive utility function to solve Maze
    problem */
    boolean solveMazeUtil(int maze[][], int x, int y,
                          int sol[][])
    {
        // if (x, y is goal) return true
        if (x == N - 1 && y == N - 1
            && maze[x][y] == 1) {
            sol[x][y] = 1;
            return true;
        }
 
        // Check if maze[x][y] is valid
        if (isSafe(maze, x, y) == true) {
              // Check if the current block is already part of solution path.   
              if (sol[x][y] == 1)
                  return false;
           
            // mark x, y as part of solution path
            sol[x][y] = 1;
 
            /* Move forward in x direction */
            if (solveMazeUtil(maze, x + 1, y, sol))
                return true;
 
            /* If moving in x direction doesn't give
            solution then Move down in y direction */
            if (solveMazeUtil(maze, x, y + 1, sol))
                return true;
           
            /* If moving in y direction doesn't give
            solution then Move backwards in x direction */
            if (solveMazeUtil(maze, x - 1, y, sol))
                return true;
 
            /* If moving backwards in x direction doesn't give
            solution then Move upwards in y direction */
            if (solveMazeUtil(maze, x, y - 1, sol))
                return true;
 
            /* If none of the above movements works then
            BACKTRACK: unmark x, y as part of solution
            path */
            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);
    }
}

Çıktı:

1 numaralı çıktılar farenin çıkış yolunu gösteriyor.

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