BFS, DFS, dan Uniform-Cost Search

Yang akan kamu pahami

Pilih pencarian sesuai biaya sisi dan ukuran solusi. Bedakan menemukan goal sebagai kandidat dengan mengeluarkannya dari frontier.

Konsep inti

BFS menggunakan antrean FIFO dan optimal untuk biaya langkah seragam. DFS menggunakan stack, bisa cepat menemukan solusi dalam, dan perlu penanganan siklus. Depth-limited search membatasi kedalaman. Iterative deepening menaikkan batas berulang kali. UCS mengambil node dengan $g(n)$ terkecil dan menguji goal saat node itu diambil dari frontier. Pada contoh dengan biaya positif, goal yang baru ditemukan masih bisa punya jalur lebih murah.

Coba langkahnya

Graf memiliki sisi S→G = 8, S→A = 2, dan A→G = 2. Jalankan UCS dari S.

Uniform-cost search pada sisi berbobot

↺‹▶›

BFS akan memilih S → G karena kedalaman satu. Untuk menjawab soal, tulis aturan tie-break ketika dua nilai prioritas sama. Pada implementasi priority queue tanpa operasi decrease key, simpan entri baru dan abaikan entri lama yang sudah kalah saat keluar.

Cek pemahaman

Cek pemahaman

1. 1. Kapan UCS berhenti pada contoh ini?

   A.Saat G berbiaya 8 dimasukkanB.Saat A pertama kali ditemukanC.Saat G berbiaya 4 dikeluarkan

2. 2. Jika semua sisi berbiaya sama, apa yang diminimalkan BFS?

   A.Jumlah sisiB.Nilai heuristikC.Jumlah simpul yang tersimpan