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
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.1.3.
Penerapan
BFS dalam Algoritma
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.
DAFTAR PUSTAKA
dir.unikom.ac.id/s1-final-project/...dan.../6-12.unik-2.pdf
MakalahSTMIK2007-081
bahasa
Indonesia, ensiklopedia bebas
www.google.com
Tidak ada komentar:
Posting Komentar