Secara garis besar, Pencarian dibedakan menjadi :
Uninformed search (blind search).
Tidak ada informasi mengenai jarak/cost dari current state ke goal state.
Informed search.
Ada informasi mengenai jarak/cost dari current state ke goal state.
TEKNIK PENCARIAN
Teknik-teknik uninformed search antara lain :
Breadth-first search (BFS).
Uniform cost search.
Depth-first search (DFS).
Depth-limited search.
Iterative deepening search (IDS).
Bidirectional search.
3. TEKNIK PENCARIAN
Untuk mengukur performansi teknik pencarian, terdapat empat kriteria yang dapat digunakan, yaitu :
Completeness: Apakah teknik tersebut menjamin penemuan solusi jika solusinya memang ada?
Time complexity : Berapa lama waktu yang diperlukan?
Space complexity : Berapa banyak ruang memori yang diperlukan?
Optimality: Apakah teknik tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda?
Bagaimana metoda GPS menemukan Solusi ?
Teknik Pencarian dan Jenisnya
Simpul
Level/Cabang
Path
Parent
Child
Root
Leave
Jumlah Ruang Simpul
Langkah solusi (Solusi)
3. TEKNIK PENCARIAN
A. BREATH FIRST SEARCH
Pencarian dilakukan pada semua simpul dalam setiap level secara berurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian akan dilakukan pada level berikutnya. Demikian seterusnya sampai ditemukan solusi.
Dengan cara ini, BFS menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukannya paling baik.
Dengan kata lain, BFS adalah komplit dan optimal.
3. TEKNIK PENCARIAN
A. BREATH FIRST SEARCH
BFS harus menyimpan semua simpul yg pernah dibangkitkan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah.
Jika b adalah faktor percabangan (jumlah simpul anak yg dimiliki oleh suatu simpul) dan d adalah kedalaman solusi, maka jumlah simpul yg harus disimpan sebanyak O(bd).
Misalkan, b = 10 dan d = 8, maka BFS harus membangkitkan dan menyimpan sebanyak 100 + 101 + 102+ 103 +104 +105 +106 +107+108 = 111.111.111 simpul.
3. TEKNIK PENCARIAN
A. BREATH FIRST SEARCH
Dari segi kecepatan, hal ini mungkin masih bisa diterima.
Dari segi memori, ini menjadi masalah karena membutuhkan ruang memori yg sangat besar.
3. TEKNIK PENCARIAN
A. BREATH FIRST SEARCH
Keuntungan :
Tidak akan menemui jalan buntu
Jika ada satu solusi, maka breath first search akan menemukannya. Jika ada lebih 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, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n-1).
3. TEKNIK PENCARIAN
- BREATH FIRST SEARCH
Contoh :
3. TEKNIK PENCARIAN
A. BREATH FIRST SEARCH
Algoritma Breath First Search mengunjungi node-node pohon secara melebar, berawal dari level dengan depth 0 ke depth maximum. Hal ini dapat dinyatakan dalam suatu antrian.
Prosedur Breath First Search:
Begin
Tempatkan node awal dalam antrian
Repeat
Hapus antrian untuk mendapatkan unsur di depannya
If unsure antrian di depannya = goal/tujuan
Return sukses dan stop
Else do
Begin
Masukkan anak turunan dari unsure di depannya jika ada di bagian belakang dari antrian
End
Until antrian kosong
End
3. TEKNIK PENCARIAN
A. BREATH FIRST SEARCH
Node_List berikut ini menggambarkan algoritma BFS di atas. Algoritma akan berakhir bila tujuan telah tercapai.
Node_list BFS dengan tujuan akhirnya adalah node 8.
3. TEKNIK PENCARIAN
A. BREATH FIRST SEARCH
TUGAS :
Buatkan program pencarian dari pohon pencarian di bawah ini menggunakan algoritma BFS.
3. TEKNIK PENCARIAN
B. DEPTH FIRST SEARCH
àPencarian dilakukan pada suatu simpul dalam setiap level dari yg paling kiri.
àJika pada level yg terdalam, solusi belum ditemukan maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yg kiri dapat dihapus dari memori.
àJika pada level yg paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.
3. TEKNIK PENCARIAN
B. DEPTH FIRST SEARCH
>> Proses pencarian akan dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi.
>> DFS membangkitkan node-node dan membandingkan mereka, tujuan sepanjang depth pohon yang terbesar kemudian bergerak naik ke “parent” (induk) dari node yang dikunjungi terakhir, hanya jika tidak ada node lebih lanjut yang dapat dibangkitkan di bawa node terakhir yang dikunjungi.
>> Setelah bergerak naik ke induk, algoritma berusaha membangkitkan turunan baru dari node induk. Hal ini dilakukan secara berulang hingga mencapai tujuan akhir.
>> Salah satu cara sederhana untuk mewujudkan algoritma DFS adalah dengan menggunakan Stack.
3. TEKNIK PENCARIAN
B. DEPTH FIRST SEARCH
Algoritma DFS sebagai berikut :
Begin
Push node awal pada stack, yang ditunjukkan dengan stack_top
While stack tidak kosong do
Begin
Pop stack untuk mendapatkan stack_top element
If stack_top_element = Tujuan
Return
Sukses dan stop
Else push turunan (cabang) stack_top element ke dalam stack
End while
End
3. TEKNIK PENCARIAN
B. DEPTH FIRST SEARCH
Contoh :
Stack berikut ini menggambarkan algoritma DFS tersebut. Proses akan diterus-kan sampai stack dalam keadaan kosong.
3. TEKNIK PENCARIAN
B. DEPTH FIRST SEARCH
à Kelebihan DFS adalah pemakaian memori yang lebih sedikit.
à DFS hanya menyimpan sekitar bd, di mana b adalah faktor percabangan dan d adalah kedalaman solusi.
à Jika b = 10 dan d = 3 maka jumlah simpul yg disimpan di memori adalah 1+10+10+10 = 31.
à Hal ini berbeda jauh dgn BFS yg harus menyimpan semua simpul yg pernah dibangkitkan. Pada kasus ini, jika gunakan BFS maka simpul yg tersimpan sebanyak 1+10+100+1000 =1111 simpul.
à Kelebihan DFS yg lain, jika solusi yg dicari berada pada level yg dalam dan paling kiri, maka DFS akan menemukannya dengan cepat.
3. TEKNIK PENCARIAN
B. DEPTH FIRST SEARCH
à Kelemahan DFS adalah jika pohon yg dibangkitkan mempunyai level yg sangat dalam (tak terhingga), maka tidak ada jaminan menemukan solusi. Artinya DFS tidak complete.
à Kelemahan lainnya adalah jika terdapat lebih dari satu solusi yg sama tetapi berada pada level yg berbeda, maka DFS tidak menjamin untuk menemukan solusi yg paling baik. Artinya, DFS tidak optimal.
Perbandingan BFS dan DFS
(Sama-sama non heuristik search)
Kualitasnya dibedakan berdasarkan :
Jumlah ruang simpul
Solusi (Jumlah langkah mencapai Solusi)
3. TEKNIK PENCARIAN
C. DEPTH LIMITED SEARCH (DLS)
à Metode ini berusaha mengatasi kelemahan DFS dengan membatasi kedalaman maksimum dari suatu jalur solusi.
à Sebelum gunakan DLS, harus tahu dulu brapa level maksimum dari suatu solusi.
à Kelmahannya : Jika batasan kedalaman terlalu kecil, DLS tidak dapat juga menemukan solusi yg ada. Artinya DLS bisa menjadi tidak complete jika batasan kedalamannya lebih kecil dibandingkan dgn level solusinya.
3. TEKNIK PENCARIAN
D. UNIFORM COST SEARCH (UCS)
à Konsepnya hampir sama dgn BFS, bedanya adalah bahwa BFS menggunakan urutan level dari yg paling rendah sampai yg paling tinggi. Sedangkan UCS berusaha menemukan solusi dgn total biaya terendah yg dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan.
à Biaya dari simpul asal ke suatu simpul n dilambangkan sebagai g(n).
3. TEKNIK PENCARIAN
B. UNIFORM COST SEARCH (UCS)
Perhatikan contoh pencarian rute berikut ini :
àKarena mengikuti konsep BFS, maka UCS menjamin ditemukannya solusi dan solusi yg ditemukannya selalu yg terbaik. Dgn kata lain, UCS adalah complete dan optimal.
à Syarat yg harus dipenuhi oleh pohon UCS adalah g(successor(n) >= g(n) untuk setiap simpul n. Jika syarat ini tidak dipenuhi maka UCS menjadi tidak complete dan tidak optimal.
3. TEKNIK PENCARIAN
E. ITERATIVE-DEEPENING SEARCH (IDS)
à IDS merupakan metode yg menggabungkan kelebihan BFS (complete dan optimal) dgn kelebihan DFS (Space complexity rendah atau membutuhkan sedikit memori).
à Konsekuensinya adalah time complexitynya menjadi tinggi.
à IDS melakukan pencarian secara iteratif menggunakan penelusuran DFS dimulai dari batasan level 0. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 untuk level 1. Demikian seterusnya sampai ditemukan solusi.
à Untuk mempercepat proses, bisa menggunakan teknik parallel processing (menggunakan lebih dari satu processor).
3. TEKNIK PENCARIAN
F. Bi-DIRECTIONAL SEARCH (BDS)
à Dengan metode, pencarian dilakukan dari dua arah, yakni pencarian maju (dari start ke tujuan) dan pencarian mundur (dari tujuan ke start).
à Ketika dua arah pencarian telah membangkitkan simpul yg sama, maka solusi telah ditemukan, yaitu dgn cara menggabungkan kedua jalur yg bertemu.
à Jika pencarian maju dan mundur menggunakan BFS, maka jumlah langkah yg diperlukan adalah sebanyak O(2bd/2) = O(bd/2).
à Misalkan, untuk b = 10 dan d = 6, maka BFS akan membangkitkan : 1+10+102+103+104+105+106 = 1.111.111 simpul.
3. TEKNIK PENCARIAN
F. Bi-DIRECTIONAL SEARCH (BDS)
à Sebaliknya BDS, hanya membangkitkan 2 x (1+10+102+103) = 2.222 simpul.
à Hal ini juga sebanding terhadap jumlah memori yg diperlukan. Dalam hal ini BDS memerlukan memori untuk menyimpan 2.222 simpul.
à BDS punya harapan yg bagus untuk digunakan karena hemat waktu maupun memori juga dan selalu memberikan solusi yg optimal jika solusinya memang ada.
PERBANDINGAN METODE PENCARIAN BERDASARKAN EMPAT (4)
KRITERIA PERFORMANCE SISTEM KB
