TUGAS 2 MK ALGORITMA

Algoritma: Greedy Best-First Search (GBFS) Mencari jalan dari titik A (Start) ke B (Goal) dengan biaya minimum, menggunakan heuristik (estimasi biaya ke tujuan). --- Contoh Kasus: Misalnya kita punya peta seperti ini (biaya aktual di setiap simpul dan estimasi jarak ke goal di dalam kurung):

- Angka di sisi panah = biaya nyata antar simpul - Angka dalam kurung = heuristik (estimasi jarak ke Goal, misalnya dari jarak Euclidean) --- Langkah-langkah Algoritma Greedy: 1. Mulai di A, lihat tetangga: - C (heuristik = 4) - B (heuristik = 6) → Pilih C (karena 4 < 6) 2. Dari C, lihat tetangga: - D (heuristik = 2) → Pilih D 3. Dari D, lihat tetangga: - E (heuristik = 0) → Pilih E (tujuan) --- Jalur yang Diambil: A → C → D → E Biaya Aktual Total: A–C = 1 C–D = 1 D–E = 3 → Total: 5

contoh visual

package soal;

import java.util.*;

public class JalurGreedy {

    // arah: kanan, bawah, kiri, atas

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

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

    static int[][] peta = {

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

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

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

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

        {9,1,1,1,0}

    };

    static class Titik {

        int baris, kolom;

        Titik(int baris, int kolom){this.baris=baris;this.kolom=kolom;}

        public String toString(){return "("+baris+","+kolom+")";}

    }

    public static void main(String[] args){

        Titik awal = new Titik(0,0);

        Titik tujuan = new Titik(4,4);

        cariJalurGreedy(awal, tujuan);

    }

    static void cariJalurGreedy(Titik awal, Titik tujuan){

        int jumlahBaris = peta.length, jumlahKolom = peta[0].length;

        boolean[][] dikunjungi = new boolean[jumlahBaris][jumlahKolom];

        int biaya = 0;

        List<Titik> jalur = new ArrayList<>();

        Titik sekarang = awal;

        jalur.add(sekarang);

        dikunjungi[sekarang.baris][sekarang.kolom] = true;

        while(!(sekarang.baris==tujuan.baris && sekarang.kolom==tujuan.kolom)){

            List<Titik> tetangga = new ArrayList<>();

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

                int nb = sekarang.baris + dBaris[k];

                int nk = sekarang.kolom + dKolom[k];

                if(nb<0 || nb>=jumlahBaris || nk<0 || nk>=jumlahKolom) continue;

                if(peta[nb][nk]==9 || dikunjungi[nb][nk]) continue;

                tetangga.add(new Titik(nb,nk));

            }

            if(tetangga.isEmpty()){

                System.out.println("Algoritma Greedy gagal: jalan buntu.");

                return;

            }

            // pilih tetangga dengan biaya paling kecil

            Titik terbaik = tetangga.get(0);

            for(Titik t: tetangga){

                if(peta[t.baris][t.kolom] < peta[terbaik.baris][terbaik.kolom]){

                    terbaik = t;

                }

            }