Algoritma Brute Force Study Case (Grid Pathfinding)

 

TUGAS 2 ALGORITMA

ITA | D0224504 | INF D

 

PEMECAHAN KASUS (GRID PATHFINDING) DENGAN BRUTE FORCE

Apa itu Brute Force dalam Kasus Ini?

Brute force artinya:

Coba semua kemungkinan jalur dari titik awal ke titik akhir, dan pilih yang terbaik (misalnya: biaya paling kecil).

 Cara Brute Force-nya Bekerja di Kode Tadi:

1. Mulai dari titik (0,0) (start)
2. Coba semua arah: atas, bawah, kiri, kanan
3. Setiap kali kita melangkah:
• Dicek: apakah masih di dalam grid?
• Apakah itu bukan dinding (9)?
• Apakah belum pernah dikunjungi di jalur ini?
4. Jalur yang sampai ke tujuan (4,4) akan dihitung total biayanya
5. Jalur yang biayanya paling kecil akan disimpan sebagai jalur terbaik

Ciri-Ciri Brute Force di Kode Kita:

• Pakai rekursi + backtracking (DFS)
• Tidak ada heuristik (seperti di A* atau Dijkstra)
• Coba semua kemungkinan jalur yang valid
• Pruning sederhana: kalau biaya sudah lebih mahal dari minimum, stop

 Kelemahan Brute Force:

• Lambat untuk grid besar (karena eksplorasi semua kemungkinan)
• Bisa jadi ribuan bahkan jutaan jalur di grid yang besar
• Tapi cocok untuk kasus grid kecil kayak 5x5 ini

Kasus: (Grid Pathfinding) Menemukan jalan di peta (Grid Pathfinding)

Cerita: Ada peta berbentuk kotak 5×5. Setiap kotak punya biaya untuk dilewati. Ada juga kotak yang terblokir (tidak bisa dilewati). Dari posisi Start (S) di kiri atas, kita ingin sampai ke Goal (G) di kanan bawah dengan biaya total paling murah.

 

Contoh peta:                                    

 

Angka = 

9 = Dinding/halangan

Tujuan: Cari jalur dari S ke G dengan biaya minuman

 

Penyelesaian: Kode