GREEDY

 

Bayangkan kamu sedang berada di sebuah peta kotak-kotak 5x5. Setiap kotak punya angka tertentu. Angka itu menunjukkan biaya yang harus dibayar kalau kamu ingin melewatinya. Ada juga beberapa kotak dengan angka 9, yang artinya ada rintangan dan kamu tidak bisa lewat di situ.

Tugasmu adalah berangkat dari pojok kiri atas (0,0) dan harus sampai ke pojok kanan bawah (4,4). Kamu ingin mencari jalan dengan biaya sekecil mungkin, tapi kamu memakai strategi Greedy.

Strategi Greedy itu seperti orang yang selalu bilang:
"Ambil saja pilihan yang paling murah sekarang, nanti urusan berikutnya belakangan."

Bagaimana langkahnya?
1. Kamu mulai dari kotak awal (0,0) dengan biaya 0.
2. Dari sini ada beberapa pilihan jalan. Kamu melihat semua tetangga, lalu langsung memilih kotak dengan angka paling kecil.
3. Setelah berpindah, kamu ulangi lagi langkah tadi: lihat tetangga, pilih yang paling kecil.
4. Kamu terus melakukannya sampai akhirnya tiba di tujuan (4,4).

Apa hasilnya?
- Jalur yang kamu lalui adalah:
  (0,0) → (0,1) → (0,2) → (1,2) → (1,3) → (1,4) → (2,4) → (3,4) → (4,4)
- Total biaya perjalananmu adalah 10.


Walaupun mungkin ada jalur lain yang sebenarnya lebih murah, dengan strategi Greedy kamu berhasil menemukan jalan yang valid dan bisa sampai tujuan. Greedy memang selalu memilih langkah terbaik saat itu, sehingga jalur akhirnya wajar saja jika tidak selalu paling optimal.

code: 

import java.util.*;

public class greedy {

    static int N = 5;

    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, 2, 1, 0} // Goal dianggap biaya 0

    };

   

    static int[] dx = {0, 1, 0, -1};

    static int[] dy = {1, 0, -1, 0};

    static class Node {

        int x, y, cost;

        Node(int x, int y, int cost) {

            this.x = x; this.y = y; this.cost = cost;

        }

    }

    public static void greedySearch(int startX, int startY, int goalX, int goalY) {

        boolean[][] visited = new boolean[N][N];

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

        int totalCost = 0;

        int x = startX, y = startY;

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

        while (!(x == goalX && y == goalY)) {

            visited[x][y] = true;

            Node nextNode = null;

            // cari tetangga dengan biaya terkecil (ikuti prioritas arah)

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

                int nx = x + dx[i];

                int ny = y + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < N &&

                    !visited[nx][ny] && grid[nx][ny] != 9) {

                    if (nextNode == null || grid[nx][ny] < nextNode.cost) {

                        nextNode = new Node(nx, ny, grid[nx][ny]);

                    }

                }

            }

            if (nextNode == null) {

                System.out.println("Greedy gagal: jalur buntu!");

                System.out.println("Jalur yang ditempuh: " + path);

                System.out.println("Total biaya: " + totalCost);

                return;

            }

            x = nextNode.x;

            y = nextNode.y;

            totalCost += nextNode.cost;

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

        }

        System.out.println("Greedy berhasil!");

        System.out.println("Jalur: " + path);

        System.out.println("Total biaya: " + totalCost);

    }

    public static void main(String[] args) {

        greedySearch(0, 0, 4, 4);

    }

}

Output :