Algoritma Depth First Search dan Breadth FirstSearch adalah algoritma pencarian buta yang digunakan dalam kecerdasan buatan. Algoritma ini berfungsi untuk menemukan tujuan pada suatu kasus dimana tidak ada informasi tambahan yang dimiliki untuk membantu melakukan pencarian. Pada pencarian buta, pencarian dilakukan dengan cara menjalani satu per satu kemungkinan yang ada. Algoritma tersebut digunakan pada aplikasi Rat Race dan Web Peta. Rat Race adalah sebuah permainan dimana terdapat labirin dengan satu jalan masuk dan satu jalan keluar. Terdapat karakter tikus yang bertugas untuk mencari jalan keluar pada labirin. Permainan ini memiliki beberapa aturan, antara lain tikus hanya dapat berjalan satu langkah demi satu langkah. Tikus tidak dapat melihat dan berjalan secara diagonal. Pada labirin hanya terdapat satu jalan masuk dan satu jalan keluar. Aplikasi Web Peta juga menggunakan algoritma pencarian buta. Tetapi pada aplikasi Web Peta, algoritma yang digunakan adalah algoritma Depth First Search. Tujuan utama dari aplikasi ini adalah untuk mencari rute dari satu lokasi ke lokasi lainnya yang terdapat dalam peta. Selain itu juga aplikasi harus dapat menemukan rute alternatif dan rute terpendek untuk mencapai tujuan.adapun macam-macam pencarian algoritma yaitu:
A. MACAM-MACAM ALGORITMA PENCARIAN
Permasalahan pencarian adalah merupakan yang sering dijumpai oleh peneliti di bidang Kecerdasan Buatan. Permasalahan ini merupakan hal penting dalam menentukan keberhasilan system kecerdasan buatan. Dalam bab ini akan dipelajari 3 bagian dalam metode pencarian, yang pertama adalah metode yang sederhana yang hanya berusaha mencari kemungkinan penyelesaian. Metode yang termasuk pada bagian ini adalah dept-first search, hill climbing, breadth-first search, beam search dan best-first search.
Yang kedua, kita akan mempelajari metode yang lebih kompleks yang akan mencari jarak terpendek. Metode ini adalah British Museum Procedure, Branch and Bound, Dynamic Programming dan A*. Metode-metode ini digunakan pada saat harga perjalanan untuk mencari kemungkinan menjadi perhitungan
Yang ketiga, kita akan mempelajari beberapa prosedur/metode yang kita terapkan saat kita berhadapan dengan musuh. Prosedur ini adalah minimax search, alpha-beta prunning. Metode ini banyak digunakan pada program-program permainan seperti catur dsb. Dalam gambar 4.1 terdapat bagan untuk Metode Searching.
Metode pencarian dikatakan penting untuk menyelesaikan permasalahan karena setiap state(keadaan) menggambarkan langkah-langkah untuk menyelesaikan permasalahan.
Metode pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, dimana setiap state menggambarkan kemungkinan posisi pada suatu saat.
Metode pencarian adalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif.
B. POHON PELACAKAN
Untuk menghindari kemungkinan adanya proses pelacakan suatu node secara berulang, maka digunakan struktur pohon. Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis. Pohon juga terdiri dari beberapa node. Node yang terletak pada level-0 disebut juga “akar”. Node akar menunjukkan keadaan awal yang biasanya merupakan topik atau obyek. Node akar ini terletak pada level ke-0. Node akar mempunyai beberapa percabangan yang terdiri atas beberapa node successor yang sering disebut dengan nama “anak” dan merupakan node-node perantara. Namun jika dilakukan pencarian mundur, maka dapat dikatakan bahwa node tersebut memiliki predecessor. Node-node yang tidak mempunyai anak sering disebut dengan nama node “daun” yang menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).
1. Pencarian Melebar Pertama (Breadth-First Search)
Pada metode Breadth-First Search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi
Algoritma
1. Buat sebuah Antrian, inisialisasi node pertama dengan Root dari tree
2. Bila node pertama, jika Ç GOAL, diganti dengan anak-anaknya dan diletakkan di belakang PER LEVEL
3. Bila node pertama = GOAL, selesai
o Keuntungan
1. Tidak akan menemui jalan buntu
2. Jika ada satu solusi, maka breadth first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
o Kelemahan
1. Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
2. Kemungkinan ditemukan optimal lokal.
2. Pencarian Mendalam Pertama (Depth-First Search)
Pada Depth First Search, proses pencarian akan dilaksanakan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukaannya solusi.
o Algoritma
1. Buat sebuah Antrian, inisialisasi node pertama dengan Root dari tree
2. Bila node pertama, jika Ç GOAL, node dihapus diganti dengan anak-anaknya dengan urutan LChild
3. Bila node pertama = GOAL, selesai
o Keuntungan
1. Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
2. Menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.
o Kelemahan
1. Kemungkinan terjebak pada optimal lokal.
Download PowerPoint >>Klik Here<<
Dosen Pengampuh Matakuliah : Algoritma dan Pemrograman 3
Download PowerPoint >>Klik Here<<
Dosen Pengampuh Matakuliah
Nama : M.Ropianto, M.Kom
NIDN : 1028067804
Status : Dosen Tetap YAPISTA/STT Ibnu Sina
Dosen Pengampuh Matakuliah : Algoritma dan Pemrograman 3
Masih kurang jelas gan, tapi sedikit membantu :)
BalasHapus