BFS & DFS
TRAVERSAL GRAF
Algoritma traversal graf: mengunjungi simpul dengan cara yang sistematik
*Pencarian melebar (breadth first search/BFS)
*Pencarian mendalam (depth first search/DFS)
*Asumsi: graf terhubung
Graf: representasi persoalan → Traversal graf: pencarian solusi
ALGORITMA PENCARIAN
Tanpa informasi (uninformed/blind search)
* Tidak ada informasi tambahan
* Contoh: DFS, BFS, Depth Limited Search, Iterative Deepening Search, Uniform Cost Search * Dengan informasi (informedSearch)
Pencarian berbasis heuristik
* Mengetahui non-goal state “lebih menjanjikan” daripada yang lain
* Contoh: Best First Search, A*
REPRESENTASI GRAF DALAM PROSES PENCARIAN
Dalam proses pencarian solusi, terdapat dua pendekatan:
Graf statis: graf yang sudah terbentuk sebelum proses pencarian dilakukan
Graf dinamis: graf yang terbentuk saat proses pencarian dilakukan
GRAF STATIS
Pencarian Melebar (BFS)
Traversal dimulai dari simpul v.
Algoritma:
1. Kunjungi simpul v
2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu.
3. Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya.
BFS : Struktur Data
1. Matriks ketetanggaan A = [aij] yang berukuran nxn,
aij= 1, jika simpul i dan simpul j bertetangga,
aij= 0, jika simpul i dan simpul j tidak bertetangga.
2. Antrian q untuk menyimpan simpul yang telah dikunjungi.
3. Tabel Boolean, diberi nama “dikunjungi”
dikunjungi : array[l..n] of boolean
dikunjungi[i] = true jika simpul i sudah dikunjungi
dikunjungi[i] = false jika simpul i belum dikunjungi
BFS : Ilustrasi
Pencarian Mendalam (DFS)
Traversal dimulai dari simpul v.
Algoritma:
1. Kunjungi simpul v
2. Kunjungi simpul w yang bertetangga dengan simpul v.
3. Ulangi DFS mulai dari simpul w.
4. Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.
5. Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi.
DFS : Ilustrasi
Contoh :
Penerapan BFS dan DFS : Web Spider
GRAF DINAMIS
Pencarian Solusi Dengan BFS & DFS
Menyelesaikanpersoalan denganmelakukan pencarian
Pencarian solusi → pembentukan pohon dinamis
- Setiap simpul diperiksa apakah solusi telah dicapai atau tidak. Jika simpul solusi , pencarian dapat selesai (satusolusi) atau dilanjutkan mencari solusi lain (semua solusi).
Representasi pohon dinamis:
- Pohon ruang status (state space tree)
- Simpul: problem state (layak membentuk solusi)
▪ Akar: initial state
▪ Daun: solution/goal state
- Cabang: operator/langkah dalam persoalan
- Ruang status (state space): himpunan semua simpul
- Ruang solusi: himpunan status solusi
Solusi: path ke status solusi
Pohon Dinamis : Permutasi A,B,C
• Operator: add X
• Akar : status awal (status “kosong”)
Simpul: problem state
- Status persoalan (problem state): simpul-simpul di dalam pohon dinamis yang memenuhi kendala (constraints).
Daun: status solusi
- Status solusi (solution state): satu atau lebih status yang menyatakan solusi persoalan.
Ruang solusi:
- Ruang solusi (solution space): himpunan semua status solusi.
Ruang status (state space): Seluruh simpul di dalam pohon dinamis dan pohonnya dinamakan juga pohon ruang status (state space tree).
Pembangkitan Status
Pembangkita status baru dengancara mengaplikasikan operator (langkah legal) kepada status (simpul) pada suatu jalur
Jalur dari simpul akar sampai ke simpul (daun) solusi berisi rangkaian operator yang mengarah pada solusi persoalan
BFS Untuk Pembentukan Ruang Status
Inisialisasi dengan status awal sebagai akar, lalu tambahkan simpul anaknya, dst.
Semua simpul pada level d dibangkitkan terlebih dahulu sebelum simpul-simpul pada level d+1
BFS Untuk Permutasi
DFS Untuk Pembentukan Pohon Ruang Status
DFS : Permutasi A,B,C
Tidak ada komentar:
Posting Komentar