Nama : Burhanudin
Alif Rahmat
NPM : 12114255
Kelas : 3KA31
METODE PENCARIAN
Blind
Search dan Heuristic Search merupakan sub bahasan yang sifatnya fundamental
dalam mata kuliah Kecerdasan Buatan (Artificial Intelligence). Bahkan dalam
dunia nyata, kita sering dituntut untuk berpikir dengan cara-cara tersebut.
Seperti ketika bermain puzzle, catur, kubus cerdas, atau mengira-ngira rute
perjalanan mana yang akan kita tempuh. Semua itu terkait dengan otak kita yang
sudah otomatis berpikir dengan algoritma blind search atau heuristic search,
atau bahkan lebih kompleks lagi.
Blind Search
Blind
Search merupakan pencarian asal ketemu. Jika solusi sudah ketemu, maka
pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal
tiga bagian, [masalah]-[pencarian]-[solusi]. Misalkan dalam kotak ada 3
kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu
kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian
didapat satu kelereng warna merah, nah, itulah solusinya.
Contoh lainnya
adalah mari anggap seseorang berangkat dari Arad menuju Bucharest, dengan
metode blind search, rencana keberangkatan akan dimulai secara acak mulai dari
Zerind, Sibiu atau Timosoara yang kemudian mengikuti alur acak sampai ke bucharest,
blind search tidak berpengaruh kepada seberapa jauh jarak yang harus ditempuh,
jika sudah sampai Bucharest, maka rencana keerangkatan selesai.
·
Breadth-First Search
BREADTH-FIRST
SEARCH (BFS) adalah sebuah algoritma pencarian graf yang dimulai dari node pangkal dan
menjelajahi semua node yang berdekatan.dan untuk setiap node yang berdekatan,
bfs menjelajahi node-node yang tidak terlihat sebelumnya (unexplored) dan
seterusnya
BFS adalah sebuah
metode pencarian yang bertujuan untuk memperluas dan memeriksa semua node dari
sebuah graf atau kombinasi dari urutan dengan menggunakan semua solusi secara
sistematis. dengan kata lain, bfs mencari ke seluruh graf atau urutan secara
mendalam tanpa mempertimbangkan tujuannya (goal) sampai tujuan itu tercapai.
bfs tidak menggunakan algoritma heuristis.
Contoh Algoritma Breadth First Search :
Dalam algoritma Breadth First Search, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk memperjelas cara kerja algoritma Breadth First Search beserta antrian yang digunakannya, berikut langkah-langkah algoritma Breadth First Search:
Dalam algoritma Breadth First Search, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk memperjelas cara kerja algoritma Breadth First Search beserta antrian yang digunakannya, berikut langkah-langkah algoritma Breadth First Search:
- Masukkan simpul
ujung (akar) ke dalam antrian.
- Ambil simpul dari
awal antrian, lalu cek apakah simpul merupakan solusi.
- Jika simpul
merupakan solusi, pencarian selesai dan hasil dikembalikan.
- Jika simpul bukan
solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut
(simpul anak) ke dalam antrian.
- Jika antrian kosong
dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil
solusi tidak ditemukan.
- Ulangi pencarian
dari langkah kedua.
Keuntungan :
·
Tidak
akan menemui jalan buntu
·
Jika
ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada
lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan :
·
Membutuhkan
memori yang cukup banyak, karena menyimpan semua node dalam satu pohon
·
Membutuhkan
waktu yang cukup lama.
·
Depth-First Search (DFS)
Depth-First Search (DFS) adalah pencarian dilakukan pada satu node dalam setiap level
dari yang paling kiri. Jika pada level yang paling dalam, solusi belum
ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri
dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan
solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya
sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan
proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).
Keuntungan:
• Pemakain memori hanya sedikit, berbeda jauh dengan BFS
yang harus menyimpan semua node yang pernah dibangkitkan.
• Jika solusi yang dicari berada pada level yang dalam
dan paling kiri, maka DFS akan menemukannya secara cepat.
Kelemahan:
• Jika pohon yang dibangkitkan mempunyai level yang dalam
(tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak
Complete).
• Jika terdapat lebih dari satu solusi yang sama tetapi
berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan
solusi yang paling baik (Tidak Optimal).
Sumber :
No comments:
Post a Comment