Tugas 3 Algoritma

 Tugas 3 Agoritma greedy

Di sebuah negeri jauh, ada seorang penjelajah bernama Riana.

Ia menemukan sebuah peta misterius berukuran 5×5.

Setiap petak di peta itu memiliki angka yang menunjukkan biaya perjalanan yang harus dikeluarkan untuk melewatinya.

Namun, ada juga petak dengan angka 9, yang merupakan dinding batu dan tidak bisa ditembus.

Riana harus berangkat dari titik Start (S) di pojok kiri atas (0,0) dan keluar lewat titik Goal (G) di pojok kanan bawah (4,4).

Ia punya aturan sederhana:

• Setiap kali berhenti di sebuah petak, Riana melihat ke kanan, bawah, kiri, dan atas.

• Dari semua petak yang bisa dilalui (belum pernah dilewati dan bukan dinding), Riana akan memilih jalan dengan biaya paling murah.

Langkah-langkah Riana

1. Dari Start (0,0)
   Riana melihat ke kanan (0,1)=1 dan ke bawah (1,0)=2.
   Karena ia selalu memilih biaya terkecil, ia melangkah ke kanan (0,1).

2. Di (0,1) biaya 1
   Pilihan: kanan (0,2)=1, bawah (1,1)=9 (dinding), kiri (0,0) sudah dilewati.
   Riana memilih kanan (0,2).

3. Di (0,2) biaya 1
   Pilihan: bawah (1,2)=1, kanan (0,3)=9, kiri (0,1) sudah dilewati.
   Riana turun ke (1,2).

4. Di (1,2) biaya 1
   Pilihan: kanan (1,3)=1, bawah (2,2)=2, kiri (1,1)=9, atas (0,2) sudah dilewati.
   Riana memilih kanan (1,3).

5. Di (1,3) biaya 1
   Pilihan: kanan (1,4)=1, bawah (2,3)=9, kiri (1,2) sudah dilewati.
   Riana maju ke kanan (1,4).

6. Di (1,4) biaya 1
   Pilihan: bawah (2,4)=1, atas (0,4)=2, kiri (1,3) sudah dilewati.
   Riana turun ke (2,4).

7. Di (2,4) biaya 1
   Pilihan: bawah (3,4)=1, kiri (2,3)=9, atas (1,4) sudah dilewati.
   Riana turun lagi ke (3,4).

8. Di (3,4) biaya 1
   Pilihan: bawah (4,4)=Goal, kiri (3,3)=1, atas (2,4) sudah dilewati.
   Riana tentu saja memilih langsung menuju Goal (4,4).

Dengan algoritma greedy, Juhariana selalu memilih jalan dengan biaya paling kecil di setiap langkah.

Strategi ini berhasil membawanya sampai ke tujuan dengan total biaya 14.

Namun, karena greedy hanya fokus pada pilihan terbaik saat ini, jalur yang dipilih belum tentu jalur paling hemat secara keseluruhan. Pada grid lain, bisa saja ada jalan lain yang lebih murah, tetapi tidak dipilih oleh algoritma greedy.

CODE JAVA

OUTPUT

Subscribe to receive free email updates: