Searching

Sherly Christina, S.Kom, M.Kom

Metode-Metode PencarianDua kategori pencarian :1. Pencarian Buta/Tanpa Informasi (blind atau un-informed

search)2. Pencarian heuristik/dengan informasi (heuristic/informed

search)

Metode-Metode PencarianUntuk mengukur perfomansi metode pencarian: Completeness Apakah metode tersebut menjamin penemuan solusi jika solusinya

memang ada?

Time Complexity Berapa lama waktu yang diperlukan?

Space Complexity Berapa banyak memori yang diperlukan?

Optimality Apakah metode tersebut menjamin menemukan solusi yang terbaik jika

terdapat beberapa solusi berbeda?

Blind/Un-Informed Search Breadth First Search (BFS) Uniform Cost Search (UCS) Depth First Search (DFS) Depth-Limited Search (DLS) Iterative Deepening Search (IDS) Bi-directional Search (BDS)

Blind/Un-Informed Search Breadth First Search (BFS) Pencarian dilakukan pd semua simpul dlm setiap level scr

berurutan dari kiri ke kanan. Jika pada satu level blm ditemukan solusi, maka pencarian dilanjutkan pd level berikutnya. Demikian seterusnya sampai ditemukan solusi.

Depth First Search (DFS) Pencarian dilakukan pd suatu simpul dlm setiap level dari yg

paling kiri. Jika pada level yg terdalam solusi belum ditemukan, maka pencarian dilanjutkan pd simpul sebelah kanan dan simpul yg kiri dapat dihapus dari memori.

Blind/Un-Informed Search Depth Limited Search (DLS)◦ Membatasi kedalaman maksimum dari suatu jalur solusi.◦ Sblm menggunakan DLS, kita harus tahu berapa level

maksimum dari suatu solusi.◦ Jika batasan kedalaman terlalu kecil, DLS tidak dapat

menemukan solusi yg ada.

Uniform Cost Search (UCS)◦ Menggunakan urutan biaya dari yang paling kecil sampai yg

terbesar.◦ UCS berusaha menemukan solusi dengan total biaya terendah

yg dihitung berdasarkan biaya dari simpul asal menuju kesimpul tujuan.

Blind/Un-Informed Search Iterative Deepening Search (IDS) Gabungan dari BFS & DFS Time complexity tinggi

Bi-Directional Search (BDS) Pencarian dilakukan 2 arah : pencarian maju (dari start ke goal)

dan pencarian mundur (goal ke start). Ketika 2 arah pencarian membangkitkan simpul yang sama,

maka solusi telah ditemukan, yaitu dgn cara menggabungkan kedua jalur yg bertemu.

Heuristic Heuristik diartikan sebagai suatu “proses yang mungkin

dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan”.

Teknik pencarian heuristik : Generate and Test Hill Climbing (Simple Hill Climbing dan Steepest – Ascent Hill

Climbing) Simulated Annealing Best First Search (Greedy Best First Search)

HeuristicGenerate n’ Test Paling sederhana Algoritma GT menggunakan prosedur Depth First Search

(DFS), suatu solusi hrs dbangkitkan secara lengkapsebelum dilakukan Test.

Sistematis Memiliki 2 prosedur penting : ◦ Pembangkit/Generate : membangkitkan sebuah solusi◦ Tes/Test : menguji solusi yang dibangkitkan tersebut

HeuristicGenerate n’ TestAlgoritma :1. Bangkitkan sebuah solusi yg mungkin. Solusi bisa berupa suatu keadaan (State)

2. Tes apakah solusi yg dibangkitkan trsebut adl. sebuah solusi yg bs diterima sesuai dgn kriteria yg diberikan.

3. Jika solusi telah ditemukan, keluar. Jika belum, kembali ke langkah 1.

HeuristicHill Climbing HC sering digunakan jika trdapat suatu fungsi heuristik yg

baik utk mengevaluasi state. Dua jenis HC Simple Hill Climbing (HC Sederhana) Steepest-Ascent HC (HC dengan memilih kemiringan yg paling

tajam)

HeuristicHill Climbing -Simple Hill Climbing

Sederhana, langsung memilih new state yang memiliki jalur yg lebih baik (“curam”) daripada jalur-jalur sblm nya tanpa memperhitungkan jalur-jalur lain.

HeuristicHill Climbing -Simple Hill ClimbingAlgoritma :

1. Evaluasi initial state. Jika state ini adalah goal state, maka kembalikan state inisebagai solusi dan keluar dari program. Jika state ini bukan goal state, lanjutkanproses dengan initial state sebagai current state.

2. Ulangi sampai solusi ditemukan/sampai tidak ada operator baru yg dptdiaplikasikan thd current state :

a) Pilih sebuah operator yg belum diaplikasikan thdp current state danaplikasikan operator tersebut sehingga menghasilkan new state.

b) Evaluasi new state : Jk state ini adl. goal state, mk kembalikan state ini sbg solusi & keluar dr program.

Jk state ini bukan goal state tetapi lebih baik daripada current state, mk jadikan state ini sbgcurrent state.

Jk state ini tidak lebih baik daripd current state, kembali ke langkah 2.a

HeuristicHill Climbing-Steepest Ascent HC Mengevaluasi semua state yg berada dibawah current

state dan memilih state dengan jalur paling “curam”.

HeuristicHill Climbing-Steepest Ascent HCAlgoritma :

1. Evaluasi intial state. Jika state ini adl goal state, maka kembalikan state ini sbgsolusi & keluar dr fungsi. Jika state ini bukan goal state, lanjutkan proses dgninitial state sbg current state.

2. Ulangi sampai solusi ditemukan/sampai tidak ada perubahan thd current state:a) Misalkan SUK adl state suksesor dr current state.b) Utk stp operator yg bs dilakukan thd current state, kerjakan :

• Aplikasi operator tsb & bangkitkan new state.

• Utk stp operator yg bs dilakukan thd current state, kerjakan:i. Aplikasikan operator tersebut & bangkitkan new stateii. Evaluasi new state

Jika SUK lebih baik dr current state maka ganti current state dgn SUK.

HeuristicBest First Search BFS (Pencarian terbaik lebih dulu) Membangkitkan simpul berikutnya dr sebuah simpul

terbaik diantara semua leaf nodes yg pernah dibangkitkan. Penentuan simpul terbaik : Menggunakan informasi berupa “biaya perkiraan” dari suatu

simpul menuju ke goal, atau Gabungan antara biaya sebenarnya & biaya perkiraan tersebut.

HeuristicBest First Search

1. Open berisi initial state, Closed masih kosong

2. Ulangi sampai goal ditemukan/sampai tidak ada nodes di dlm Open:a. Ambil simpul terbaik yg ada di dlm Open

b. Jk simpul trsbt sama dgn goal, mk sukses

c. Jk tidak, masukkan simpul trsbt ke dlm Closed

d. Bangkitkan smua suksesor dr simpul trsebut

e. Utk stiap suksesor kerjakan:

i. Jk suksesor trsbut blm pernah dibangkitkan, evaluasi suksesor tambahkan ke Open, dan catat parent atau orang tuanya.

ii. Jk suksesor trsbt sdh pernah dibangkitkan, ubah parent-nya jk jalurnya mll parent ini lebih baik drpd mll parent yg sbelumnya. Selanjutnya perbarui biaya untuk suksesor trsebut & node lain yg berada lvl bawahnya.

HeuristicBest First Search Open adl senarai (list) utk menyimpan simpul2 yg pernah

dibangkitkan & nilai heuristiknya tlh dihitung ttp blm trpilih sbg simpul terbaik (Best Node)

Open berisi simpul2 yg msh memiliki peluang (peluangnya msh terbuka)

Closed adl senarai untuk menyimpan simpul-simpul yg sdh pernah dibangkitkan & sdh prnh trpilih sbg simpul terbaik.

Closed berisi simpul-simpul yg tidak mgkn trpilih sbg simpul trbaik (peluang untuk terpilih sdh trtutup).

HeuristicFungsi Heuristik Memainkan peranan yg penting. Suatu fungsi diterima sbg. Fungsi heuristik jk biaya

perkiraan yg dihasilkan tidak melebihi biaya sebenarnya. Jk melebihi => overestimate/ tidak optimal