Materi5 blind search_bfs-dfs
Download as PPTX, PDF
0 likes281 views
1. BFS dan DFS adalah dua algoritma pencarian pohon yang berbeda dalam cara melakukan penelusuran. 2. BFS melakukan penelusuran secara lebar terlebih dahulu sehingga menemukan solusi terpendek, sedangkan DFS melakukan penelusuran sedalam mungkin terlebih dahulu. 3. Keduanya memiliki kelebihan dan kekurangan tergantung sifat graf masalah yang dihadapi.
![Prosedur BFS
Inisialisasi :
open = [start]; closed []
While open = [] do
Begin
Hapuskan keadaan paling kiri dari keadaan open, sebutlah keadaan itu dengan X;
Jika X merupakan tujuan then return (sukses);
Buatlah semua child dari X;
Ambillah X dan masukkan pada closed;
Eliminasilah setiap child X yang telah berada
pada open atau closed, yang akan menyebabkan loop dalam search;
Ambillah turunan di ujung kanan open sesuai urutan penemuan-nya;
End;](https://image.slidesharecdn.com/materi5blindsearchbfs-dfs-101122093858-phpapp02/85/Materi5-blind-search_bfs-dfs-4-320.jpg)
![Prosedur DFS
prosedur depth_first_search
inisialisasi: open = [Start]; closed = []
while open x [] do
begin
hapuskan keadaan berikutnya dari sebelah kiri
open, sebutlah keadaan itu dengan X;
jika X merupakan tujuan then return(sukses);
buatlah semua child yang dimungkinkan dari X;
ambilah X dan masukkan pada closed;
eliminasilah setiap child X yang telah berada
pada open atau closed, yang akan menyebabkan
loop dalam search;
ambilah child X yang tersisa di ujung kanan open
sesuai urutan penemuannya;
end.](https://image.slidesharecdn.com/materi5blindsearchbfs-dfs-101122093858-phpapp02/85/Materi5-blind-search_bfs-dfs-9-320.jpg)
Materi5 blind search_bfs-dfs
- 1. DFS vs BFS
- 2. Breadth First Search Prosedur pencarian melebar pertama (breadth-first search) merupakan prosedur yang menjamin diperolehnya sebuah solusi jika solusi itu memang ada, dimana tersedia sejumlah percabangan pohon (tree) yang berhingga
- 4. Prosedur BFS Inisialisasi : open = [start]; closed [] While open = [] do Begin Hapuskan keadaan paling kiri dari keadaan open, sebutlah keadaan itu dengan X; Jika X merupakan tujuan then return (sukses); Buatlah semua child dari X; Ambillah X dan masukkan pada closed; Eliminasilah setiap child X yang telah berada pada open atau closed, yang akan menyebabkan loop dalam search; Ambillah turunan di ujung kanan open sesuai urutan penemuan-nya; End;
- 5. Kelebihan dan kekurangan Karena proses pencarian breadth-first mengamati setiap simpul di setiap tingkat graf sebelum bergerak menuju ruang yang lebih dalam, maka mula-mula semua keadaan akan dicapai lewat lintasan yang terpendek dari keadaan awal. Karena itu, proses pencarian ini menjamin ditemukannya lintasan terpendek dari keadaan awal ke keadaan tujuan.
- 6. Karena proses pencarian Breadth-First selalu memeriksa setiap simpul (node) pada tingkat n sebelumnya memproses tingkat n + 1, maka pencarian tersebut selalu mendapatkan lintasan terpendek menuju simpul tujuan
- 7. Depth First Search DFS melakukan penelusuran dari Root menuju node paling kiri kemudian meneruskan level di bawahnya (ke dalam) sampai ditemukan daun (leaf), Jika daun (leap) tersebut merupakan goal-nya maka berhenti (sukses), jika bukan goal maka proses dilanjutkan ke leap yang lain (melebar) atau backtracking ke node di level atasnya sampai ditemukanya goal.
- 9. Prosedur DFS prosedur depth_first_search inisialisasi: open = [Start]; closed = [] while open x [] do begin hapuskan keadaan berikutnya dari sebelah kiri open, sebutlah keadaan itu dengan X; jika X merupakan tujuan then return(sukses); buatlah semua child yang dimungkinkan dari X; ambilah X dan masukkan pada closed; eliminasilah setiap child X yang telah berada pada open atau closed, yang akan menyebabkan loop dalam search; ambilah child X yang tersisa di ujung kanan open sesuai urutan penemuannya; end.
- 10. Kelebihan dan Kekurangan Proses pencarian Depth-First akan dengan cepat mencapai kedalaman ruang pencarian. Jika diketahui bahwa lintasan solusi problema akan panjang, maka pencarian depth_first tidak akan memboroskan waktu untuk melakukan pencarian sejumlah besar keadaan dangkal dalam graf problema.
- 11. Pencarian depth-first jauh lebih efisien untuk ruang pencarian dengan banyak percabangan, karena tidak perlu harus mengevaluasi semua simpul pada suatu tingkat tertentu.