BAB
I
PENDAHULUAN
1.1
Latar
Belakang
Dalam
ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas adalah sebuah
algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah
solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa
kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan
komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari
sebuah masalah disebut ruang pencarian. Algortima pencarian brute-force atau
pencarian naif/uninformed menggunakan metode yang sederhana dan sangat intuitif
pada ruang pencarian, sedangkan algoritma pencarian informed menggunakan
heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian
untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian. Adapun
dalam metode pencarian blind atau buta digunakan karena memang tidak ada
informasi awal yang digunakan dalam proses pencarian. Algoritma Pencarian ini
menggunakan Metode BFS, DFS, dll.
1.2
Batasan
Masalah
Makalah ini membahas tentang
Algoritma Pencarian hanya pada Metode Pemecahan Masalah yaitu Breadth-first
Search (BFS), Depth-first Search (DFS) dan Metode Pencarian Heuristik.
1.3
Tujuan
Tujuan dari Pembuatan Makalah ini,
antara lain agar :
1. Mahasiswa
mampu memahami apa itu DFS, BFS dan Heuristik
2. Mahasiswa
mampu membedakan DFS, BFS dan Heuristik
1.4
Metode
Metode
yang digunakan penulis dalam pembuatan Makalah ini adalah dengan mencari
referensi di internet.
BAB II
PEMBAHASAN
2.1.
Breadth-First
Search (BFS)
Breadth-first
search (BFS) melakukan proses searching pada semua
node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum
melanjutkan proses searching pada node di level berikutnya. Urutan proses
searching BFS ditunjukkan dalam Gambar 2.1 adalah: A,B,C,D,E,F, ...
Breadth-first
search adalah algoritma yang melakukan pencarian secara melebar yang
mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian
mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih
dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan
simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk
pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum
simpul-simpul pada ras d+1.
Algoritma
ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi.
Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang
bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam
antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk
menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang
dikunjungi lebih dari satu kali.
2.1.1. Cara Kerja Algoritma
BFS
Dalam algoritma
BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian
ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan
dikunjungi kemudian sesuai urutan pengantrian.
Untuk
memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut
langkah-langkah algoritma BFS:
1.
Masukkan simpul ujung
(akar) ke dalam antrian
2.
Ambil simpul dari awal
antrian, lalu cek apakah simpul merupakan solusi
3.
Jika simpul merupakan
solusi, pencarian selesai dan hasil dikembalikan.
4.
Jika simpul bukan
solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul
anak) ke dalam antrian
5.
Jika antrian kosong dan
setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi
tidak ditemukan
6.
Ulangi pencarian dari
langkah kedua
Contohnya
terlihat dibawah ini:
Maka
penyelesaiannya adalah:
Gambar (a)
BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.
Gambar (b)
BFS(1): 1, 2, 3, 4, 5, 6, 7, 1
Gambar (c)
BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9
2.1.2. Contoh Pencarian
Lintasan Terpendek Dengan BFS
Adapun contoh
untuk mencari lintasan terpendek dengan menggukan algoritma BFS adalah sebagai
berkut:
Diketahui sebuah
kota, dengan memiliki inisial seperti yang ditunjukkan dibawah ini. Jarak antar
kota dibentuk dengan sebuah graph terlihat dibawah:
Pertanyaan:
sebutkan rute yang akan ditempuh untuk mencapai kota no. 8. Titik awal
perjalanan adalah kota no. 1. Gunakan algoritma BFS!
Maka dengan
menggunakan algoritma BFS, rute tercepat yang didapat adalah sebagai berikut:
1 – 2 – 3 – 4 –
5 – 6 – 7 – 8
Rute tersebut
didapat dari pencarian secara melebar. Hal; tersebut dapat dijabarkan sebagai
berikut:
·
Pertama-tama, pointer
menunujuk pada daun yang ada sebelah kanan, yaitu no.2 (1 – 2)
·
Setelah itu, proses
dilanjutkan pada tetangga no.2 yaitu no.3 (1-2-3) dan selanjutnya mengarah pada
tetangga terdekat, yakni no.4 (1-2-3-4).
·
Pointer mencari
teteangga no.4, namun karna tidak ada, maka pointer kembali ke kota no.2 dan
masuk ke daun berikutnya, yakni no.5.
·
Proses diulang hingga
pointer menunjuk angka 8
2.2.
Depth-First
search (DFS)
Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi
sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi
terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai
menemukan goal atau dead end. Apabila proses searching menemukan dead-end, DFS
akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut
memiliki path cabang yang belum dieksplorasi. Apabila cabang ditemukan, DFS
akan melakukan cabang tersebut. Apabila sudah tidak ada lagi cabang yang dapat
dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching
terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan
penyelesaian masalah. Urutan proses searching DFS ditunjukkan dalam Gambar 1.5
adalah: A, B, E,F, G, C, ... Figure
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).
2.2.1.
Kelebihan
dan Kelemahan DFS
Kelebihan
DFS adalah:
• 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 DFS adalah:
• 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)..
2.2.2.
Cara
Kerja DFS
Pencarian
rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik
awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari
tujuan atau sebagai simpul yang dicari.
Dalam
algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan
(stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi
sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses
runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman
maksimal).
Untuk
memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya,
berikut langkah-langkah algoritma DFS:
1. Masukkan
simpul ujung (akar) ke dalam tumpukan
2. Ambil
simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi
3. Jika
simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika
simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul
tersebut (simpul anak) ke dalam tumpukan
5. Jika
tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan
mengembalikan hasil solusi tidak ditemukan
6. Ulangi
pencarian dari langkah kedua
2.3. Pencarian Heuristik
Heuristic search adalah suatu istilah yang
berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah
suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang
menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga
sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada
pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu
mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.
George Poyla (dalam
Kristanto. A, 2003) mendefinisikan heuristik sebagai ”studi tentang sebuah
metode dan aturan discovery serta invention” dalam pencarian state
space, heuristik didefinisikan sebagai aturan untuk memilih cabang-cabang
dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang
dapat diterima .
Pemecahan masalah AI
menggunakan heuristik dalam dua situasi dasar (Setiawan. S, 1993), yaitu :
1. Permasalahan
yang mungkin tidak mempunyai solusi yang pasti disebabkan oleh ambiguitas
(keraguan/ketidakpastian) mendasar dalam pernyataan permasalahan atau data yang
tersedia, contohnya diagnosa kedokteran.
2. Permasalahan
yang boleh jadi memiliki solusi pasti, tetapi biaya komputasinya untuk
mendapatkan solusi tersebut mungkin sangat tinggi. Dalam banyak problema
(misalnya saja catur), pertumbuhan state space adalah secara kombinatorial
eksplosif dengan bayak state yang mungkin meningkat secara eksponensial
atau faktorial dengan kedalaman pencarian. Dalam hal ini, exhaustive,
yakni teknik pencarian brute force seperti pencarian mendalam pertama
dan pencarian meluas pertama mungkin gagal menemukan solusi sehingga heuristik
akan menangani kerumitan permasalahan ini dengan panduan pencarian pada
sepanjang lintasan yang memeberi harapan melewati state. Dengan mengeliminasi
state yang tidak memberi harapan dan turunannya dari ruang tersebut maka
algoritma heuristik dapat mengalahkan ledakan kombinatorial dan menemukan
penyelesaian yang dapat diterima.
Pencarian terbimbing (heuristic
search) dibutuhkan karena pencarian buta (blind search) tidak selalu
dapat diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama
serta besarnya memori yang diperlukan. Dalam pencarian ruang keadaan, heuristik
dinyatakan sebagai aturan untuk melakukan pemilihan cabang-cabang dalam ruang
keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat
diterima.
Heuristik dapat
digunakan pada beberapa kondisi berikut ini (Siswanto, 2010):
1. Mengatasi combinatorial explosion.
Ada masalah yang kemungkinan arah penyelesaiannya berkembang pesat
(bersifat faktorial) sehingga menimbulkan combinatorial explosion.
Heuristik merupakan cara untuk menentukan kemungkinan arah penyelesaian masalah
secara efisien.
2. Solusi paling optimal mungkin tidak diperlukan.
Dalam suatu keadaan, mungkin lebih baik mendapatkan solusi yang
mendekati optimal dalam waktu yang singkat daripada solusi yang paling optimal
dalam waktu yang lama.
3. Pada umumnya hasilnya cukup baik.
Sekalipun tidak optimal, tetapi biasanya mendekati optimal. Membantu pemahaman bagi orang yang
menyelesaikan persoalan.
4. Banyak alternatif heuristik yang dapat diterapkan dalam suatu
percobaan. Orang yang menyelesaikan persoalan tersebut akan lebih mengerti
persoalannya jika mencoba heuristik yang diterapkannya.
Salah satu contoh dari
heuristik yang baik untuk tujuan umum yang berguna untuk beragam kombinasi
permasalahan adalah the nearest neighbour heuristic, yang bekerja dengan
cara menyeleksi alternatif yang paling tinggi secara lokal pada setiap
langkahnya. Untuk permasalahan perjalanan salesman, prosedur-prosedur yang
harus dilakukan adalah sebagai berikut :
1.
Memilih sebuah kota awal (starting cities)
2.
Melihat kota berikutnya, kemudian melihat semua kota yang
belum dikunjungi dan memilih salah satu kota yang paling dekat dengan kota yang
dipilih pada saat itu.
3.
Ulangi langkah 2 sampai semua kota dikunjungi.
Sebuah fungsi heuristik
mengevaluasi keadaan permasalahan tersendiri dan menentukan bagaimana
diperlukan fungsi ini dalam memecahkan suatu permasalahan. Sebuah fungsi
heuristik adalah sebuah fungsi yang memetakan keadaan permasalahan, yang
mendeskripsikan daya tarik dan digambarkan dalam sebuah angka (Pearl, 1984).
Fungsi heuristik yang
dirancang dengan baik dapat berperan dalam sebuah bagian yang penting untuk
memandu secara efisien proses pencarian menuju ke sebuah solusi. Tabel 2.1
menunjukkan beberapa fungsi heuristik sederhana untuk beberapa permasalahan.
Kadang kala sebuah nilai tinggi dari fungsi heuristik mengindikasikan
sebuah posisi yang baik secara relatif (terlihat pada catur dan tic tac toe),
di lain waktu sebuah nilai rendah mengindikasikan sebuah situasi yang
menguntungkan (terlihat pada perjalanan salesman). Program yang menggunakan
nilai (value) dari fungsi dapat mengusahakan minimal atau maksimal secara
tepat.
Tujuan dari sebuah fungsi heuristik adalah untuk memandu proses
pencarian tujuan yang menguntungkan dengan menganjurkan jalur yang mana yang
diikuti pertama kali ketika tersedia lebih dari satu tujuan. Setelah proses
berlangsung, akan bisa dihitung sebuah fungsi heuristik yang sempurna dengan
cara melakukan sebuah pencarian yang lengkap dari simpul dalam pertanyaan dan
menentukan apakah fungsi ini menuju ke sebuah solusi yang baik.
Sayangnya, seperti semua kaidah penemuan lainnya, heuristik juga dapat
salah. Heuristik hanyalah panduan informasi untuk menebak langkah berikutnya
yang harus diambil dalam menyelesaikan suatu permasalahan, dan sering dilakukan
berdasarkan eksperimen/percobaan atau secara intuisi. Oleh karena menggunakan informasi
yang terbatas, heuristik jarang dapat memprediksi tingkah laku yang eksak dari
ruang keadaan saat dilakukan pencarian. Heuristik dapat membimbing algoritma
pencarian untuk mendapatkan solusi suboptimal atau gagal menemukan solusi
apapun, karena tidak ada solusi yang dapat menuju keadaan akhir.
Heuristik dan perancangan algoritma untuk mengimplementasikan pencarian
heuristik telah menjadi inti permasalahan penelitian AI. Game playing dan
pemecahan teorema (theorem solving) adalah dua aplikasi paling tua dari AI,
kedua-duanya memerlukan heuristik untuk memangkas ruang dari solusi yang
mungkin.
BAB 3
PENUTUP
3.1. Kesimpulan
Dari pembahasan diatas dapat ditarik
kesimpulan yaitu :
1.
Breadth-first search (BFS) melakukan proses searching pada
semua node yang berada pada level atau hirarki yang sama terlebih dahulu
sebelum melanjutkan proses searching pada node di level berikutnya.
2.
Depth-first search (DFS) adalah proses searching sistematis
buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah
sebelum melakukan ekplorasi terhadap path yang lain.
3. Heuristic search adalah suatu istilah yang
berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah
suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang
menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga
sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada
pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu
mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.