Tugas 5 Algoritma

Tugas 5 Algoritma 

Ada sebuah peta berukuran 5×5.

Setiap petak memiliki angka yang menunjukkan biaya perjalanan. Jika sebuah petak bernilai 9, berarti petak tersebut adalah dinding yang tidak bisa dilewati.

Tujuannya adalah mencari jalur dari Start (0,0) di pojok kiri atas menuju Goal (4,4) di pojok kanan bawah dengan menggunakan algoritma BFS (Breadth First Search).

Strategi BFS :

BFS menelusuri peta lapis demi lapis, dari titik awal ke semua tetangga, lalu ke tetangga berikutnya.

Dengan cara ini, BFS selalu menemukan jalur dengan jumlah langkah paling sedikit, walaupun biayanya belum tentu paling kecil.

Urutan arah gerakan yang dipakai: kanan → bawah → kiri → atas.

Code java :

import java.util.*;

public class BFSPathfinding {
    static int N = 5;
    static int[][] map = {
            {1, 1, 3, 9, 2},
            {2, 9, 2, 4, 3},
            {3, 2, 1, 9, 2},
            {9, 3, 2, 1, 4},
            {4, 2, 3, 2, 1}
    };

    // arah gerakan: kanan, bawah, kiri, atas
    static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};

    static class Node {
        int r, c;
        List<int[]> path;
        int cost;

        Node(int r, int c, List<int[]> path, int cost) {
            this.r = r;
            this.c = c;
            this.path = path;
            this.cost = cost;
        }
    }

    public static void main(String[] args) {
        bfs(0, 0, 4, 4);
    }

    static void bfs(int sr, int sc, int gr, int gc) {
        boolean[][] visited = new boolean[N][N];
        Queue<Node> q = new LinkedList<>();

        List<int[]> startPath = new ArrayList<>();
        startPath.add(new int[]{sr, sc});

        q.add(new Node(sr, sc, startPath, map[sr][sc]));
        visited[sr][sc] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            if (cur.r == gr && cur.c == gc) {
                System.out.println("Jalur BFS:");
                for (int[] p : cur.path) {
                    System.out.print("(" + p[0] + "," + p[1] + ") ");
                }
                System.out.println("\nTotal biaya: " + cur.cost);
                return;
            }

            for (int[] d : dir) {
                int nr = cur.r + d[0];
                int nc = cur.c + d[1];

                if (nr >= 0 && nr < N && nc >= 0 && nc < N && map[nr][nc] != 9 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    List<int[]> newPath = new ArrayList<>(cur.path);
                    newPath.add(new int[]{nr, nc});
                    q.add(new Node(nr, nc, newPath, cur.cost + map[nr][nc]));
                }
            }
        }

        System.out.println("Tidak ada jalur ke Goal!");
    }

}

OUTPUT :

 Jalur yang Ditempuh

1. Mulai di (0,0).

2. Bergerak ke kanan (0,1).

3. Dari (0,1) ke kanan (0,2).

4. Dari (0,2) turun ke (1,2).

5. Dari (1,2) ke kanan (1,3).

6. Dari (1,3) lanjut ke kanan (1,4).

7. Dari (1,4) turun ke (2,4).

8. Dari (2,4) turun ke (3,4).

9. Dari (3,4) turun ke (4,4) sebagai Goal .

Jalur BFS

(0,0) → (0,1) → (0,2) → (1,2) → (1,3) → (1,4) → (2,4) → (3,4) → (4,4)

Total Biaya

(0,0) = 1

(0,1) = 1

(0,2) = 3

(1,2) = 2

(1,3) = 4

(1,4) = 3

(2,4) = 2

(3,4) = 4

(4,4) = 1

Total biaya = 21

Dengan algoritma BFS, jalur dari Start ke Goal berhasil ditemukan.

Total biaya perjalanan yang didapat adalah 21.

BFS bekerja dengan menelusuri peta lapis demi lapis hingga menemukan Goal, sehingga jalur yang dipilih selalu memiliki langkah paling sedikit.

Subscribe to receive free email updates: