TUGAS 3 MK ALGORITMA

saya ingin menelusuri peta dari petak S di sudut kiri atas dan sampai pada petak G sudut kanan bawah dengan biaya perjalanan sekecil mungkin. dengan prinsip DFS yaitu menyelam satu cabang sedalam mungkin kemudian Backtracking untuk kembali ke persimpangan jika jalan buntu atau sudah terlalu mahal,semua jalur dari S ke G di coba dan Setelah semua jalur selesai dicoba, saya memilih biaya paling murah. Saya mulai dari S(0,0) dengan biaya 0,saya memilih arah pertama kanan (0,1) dengan biaya 1. Dari(0,1) saya lanjut ke kanan (0,2) dengan total biaya 2. kemudian dari(0,2) saya ke kanan(0,3) tetapi disana ada dinding(9). Backtrack ke (0,2) saya kebawah (1,2) dengan total biaya 3. Kemudian dari(1,2) saya ke kanan(1,3) dngan total biaya 4. Dari (1,3) saya lanjut ke kanan(1,4) dengan total biaya 5. Selanjutnya dari(1,4) saya kebawah(2,4) dengan total biaya = 6. Dari(2,4) saya kebawah(3,4) dengan total biaya = 7. Dan Terakhir dari(3,4) saya ke bawah atau Ke G(4,4).sampai tujuan dengan total biaya = 7.Setelah Menemukan G Jadi jalur pertama yang saya lalui adalah dari S(0,0), (0,1), (0,2), (1,2), (1,3), (1,4), (2,4),(3,4), G(4,4) dengan total biaya = 7. Saya tidak langsung berhenti. saya mundur lagi dan mencoba cabang lain dari titik sebelumnya, untuk memastikan tidak ada jalur yang lebih murah. Tetapi setiap kali saya menemukan jalur lain yang biayanya sudah ≥7, saya menghentikan cabang itu (pruning) karena tidak mungkin lebih murah. Semua jalur lain mengandung angka 2 atau lebih panjang, jadi semuanya lebih mahal.

 CONTOH VISUAL :

package javaapplication42;

    

 import java.util.*;

public class DFSPathfinding {

    static int[][] grid = {

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

        {1, 2, 1, 1, 1},

        {1, 9, 2, 9, 1},

        {1, 1, 2, 1, 1},

        {1, 1, 1, 2, 0} // 0 di sini = Start/Goal, 9 = dinding

    };

    static int rows = grid.length;

    static int cols = grid[0].length;

    static int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}}; // bawah, atas, kanan, kiri

    static int bestCost = Integer.MAX_VALUE;

    static List<String> bestPath = new ArrayList<>();

    static boolean[][] visited = new boolean[rows][cols];

    public static void main(String[] args) {

        List<String> path = new ArrayList<>();

        dfs(0, 0, 0, path); // Start di (0,0)

        if (bestCost < Integer.MAX_VALUE) {

            System.out.println("Biaya minimum: " + bestCost);

            System.out.println("Jalur yang dilalui: " + bestPath);

        } else {

            System.out.println("Tidak ada jalur ditemukan.");

        }

    }

    static void dfs(int x, int y, int cost, List<String> path) {

        // Cek batas

        if (x < 0 || x >= rows || y < 0 || y >= cols) return;

        // Cek dinding atau sudah dikunjungi

        if (grid[x][y] == 9 || visited[x][y]) return;

        // Hitung biaya (S dan G dianggap 0)

        int cellCost = (x == 0 && y == 0) || (x == rows-1 && y == cols-1) ? 0 : grid[x][y];

        int newCost = cost + cellCost;

        // Pruning

        if (newCost >= bestCost) return;

        // Tambahkan posisi ke path

        path.add("(" + x + "," + y + ")");

        visited[x][y] = true;

        // Jika sampai Goal

        if (x == rows-1 && y == cols-1) {

            if (newCost < bestCost) {

                bestCost = newCost;

                bestPath = new ArrayList<>(path); // Simpan jalur terbaik

            }

        } else {

            // Coba 4 arah

            for (int[] d : directions) {

                dfs(x + d[0], y + d[1], newCost, path);

            }

        }

        // Backtrack

        path.remove(path.size() - 1);

        visited[x][y] = false;

    }

}