Metode Pencarian dan Pelacakan 2

08.47 |

Pengertian Best-first Search

Best-First Search merupakan sebuah metode yang membangkitkan simpul dari simpul sebelumnya. Best-first search memilih simpul baru yang memiliki biaya terkecil diantara semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n).

fungsi evaluasi best-first search dapat berupa biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut.

Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi heuristic merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan sepanjang jalur yang memiliki kemungkinan sukses paling besar.

Ada beberapa istilah yang sering digunakan pada metode best-first search, yaitu:

1 Start node adalah sebuah terminology untuk posisi awal sebuah pencarian

2 Curret node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek

3 Suksesor adalah simpul-simpul yang yang akan diperiksa setelah current node

4 Simpul (node) merupakan representasi dari area pencarian

5 Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan

6 Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan

7 Goal node yaitu simpul tujuan

8 Parent adalah curret node dari suksesor.

Algoritma best-first search

Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi algoritma best-first search dapat dilihat pada gambar 3.4 dibawah ini.

Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah senarai, yaitu: OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node-node yang pernah dibangkitkan dan sudah dievaluasi. Algoritma selengkapnya adalah sebagai berikut.

1) OPEN berisi initial state dan CLOSED masih kosong.

2) Ulangi sampai goal ditemukan atau sampai tidak ada di dalam OPEN.

a. Ambil simpul terbaik yang ada di OPEN.

b. Jika simpul tersebut sama dengan goal, maka sukses

c. Jika tidak, masukkan simpul tersebut ke dalam CLOSED

d. Bangkitkan semua aksesor dari simpul tersebut

e. Untuk setiap suksesor kerjakan:

i. Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat parent.

ii. Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nyajika jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya perbarui biaya untuk suksesor tersebut dn nodes lain yang berada di level bawahnya.

Algoritma yang menggunakan metode best-first search, yaitu:

a. Greedy Best-First

Greedy Best-First adalah algoritma best-first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni f(n) = h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal.

b. A*

A* adalah algoritma best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.

PROBLEM REDUCTION

Problem reduction adalah dasar teknik pemecahan masalah AI dimana dilakukan dengan cara mengurangi masalah dalam satu set sub masalah yang lebih mudah pemecahannya. Intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Ide utama teknik problem reduction adalah mendekomposisi masalah ke dalam skala yang lebih kecil.

Problem Reduction dibagi dalam dua metode yaitu :

1. Graf AND OR Graf AND OR atau tree merupakan graf yang digunakan untuk

memperlihatkan solusi dari permasalahan yang dapat diselesaikan dengan cara mendekomposisikan masalah tersebut menjadi sekumpulan masalah yang lebih kecil, dimana semuanya harus dapat diselesaikan. Pereduksian ini membangkitkan arc(busur) AND. Satu busur AND akan menghasilkan beberapa nomor dari simpul setelahnya dimana semua simpul harus diselesaikan supaya pancaran menghasilkan solusi. Hanya saja pada graf OR banyak pancaran akan muncul dari beberapa node, mengindikasikan beberapa jalan yang dapat menyelesaikan masalah.

Untuk menemukan solusi dari sebuah graf AND OR kita memerlukan sebuah algoritma yang serupa dengan algoritma BFS(Best First Search) tetapi dengan kemampuan untuk menangani pancaran AND dengan tepat. Algoritma ini harus menemukan bagian dari simpul awal dari graf untuk menghimpun simpul-simpul yang menggambarkan state solusi. Perlu diketahui bahwa hal ini mungkin diperlukan untuk mendapatkan lebih dari solusi dalam setiap pancaran AND. Untuk mendeskripsikan algoritma Graph AND-OR kita menggunakan nilai F_UTILITY, yaitu biaya solusi. Algoritma :

9 Inisialisasi graph ke node awal.  

10 Kerjakan langkah-langkah di bawah ini hingga node awal SOLVED  

atau sampai biayanya lebih tinggi dari F_UTILITY:

(a.) Telusuri graph, mualai dari node awal dan ikuti jalur terbaik. Akumulasikan kumpulan node yang ada pada lintasan tersebut dan belum pernah diekspansi atau diberi label SOLVED.

(b.) Ambil satu node dan ekspansi node tersebut. Jika tidak ada successor, maka set F_UTILITY sebagai nilai dari node tersebut. Bila tidak demikian, tambahkan successor-successor dari node tersebut ke graph dan hitung nilai setiap f’ (hanya gunakan h’ dan abaikan g). Jika f’ = 0, tandai node tersebut dengan SOLVED.

(c.) Ubah f’ harapan dari node baru yang diekspansi. Kirimkan perubahan ini secara backward sepanjang graph. Jika node berisi suatu arc suatu successor yang semua descendant-nya berlabel SOLVED maka tandai node itu dengan SOLVED.

Pada Gambar di atas, pada langkah-1 semula hanya ada satu node yaitu A. Node A diekspansi hasilnya adalah node B, C, dan D. Node D memiliki biaya yang lebih rendah (6) jika dibandingkan dengan B dan C (9). Pada langkah-2 node D terpilih untuk diekspansi, menjadi E dan F dengan biaya estimasi sebesar 10. Sehingga kita harus memperbaiki nilai

f’ dari D menjadi 10. Kembali ke level sebelumnya, node B dan C memiliki biaya yang lebih rendah daripada D (9 < 10). Pada langkah-3, kita menelusuri arc dari node A, ke B dan C bersama-sama. Jika B dieksplore terlebih dahulu, maka akan menurunkan node G dan H. Kita perbaiki nilai f’ dari B menjadi 6 (nilai G=6 lebih baik daripada H=8), sehingga biaya AND-arc B-C menjadi 12 (6+4+2). Dengan demikian nilai node D kembali menjadi lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D. Demikian seterusnya.

2. Graf AO*(Algorithm Optimized) Algoritma AO* menggunakan struktur Graph dimana tiap-tiap node

pada graph tersebut akan memiliki nilai h’ yang merupakan biaya estimasi jalur dari node itu sendiri sampai suatu solusi. Algoritma 1. Diketahui GRAPH yang hanya berisi node awal (sebut saja node INIT). Hitung h’(INIT).

2. Kerjakan langkah-langkah di bawah ini hingga INI bertanda SOLVED atau samoai nilai h’(INIT) menjadi lebih besar daripada F_UTILITY:

. (a) Ekspand INIT dan ambil salah satu node yang belum pernah diekspand (sebut NODE).  

. (b) Bangkitkan successor-successor NODE. Jika tida memiliki successor maka set FUTULITY dengan nilai h’(NODE). Jika ada successor, maka untuk setiap successor (sebut sebagai SUCC) yang bukan merupakan ancestor dari NODE, kerjakan:  1. Tambahkan SUCC ke graf. 2. Jika SUCC adalah terminal node, tandai dengan  SOLVED dan set nilai h’-nya sama dengan 0. 3. Jika SUCC bukan terminal node, hitung nilai h’.  

. (c) Kirimkan informasi baru tersebut ke graph, dengan cara: tetapkan S adalah node yang ditandai dengan SOLVED atau node yang nilai h’-nya baru saja diperbaiki, dan sampaikan  

nilai ini ke parent-nya. Inisialisasi S = NODE. Kerjakan langkah-langkah berikut ini hingga S kosong.

1. Jika mungkin, seleksi dari S suatu node yang tidak memiliki descendant dalam GRAPH yang terjadi pada S. Jika tidak ada, seleksi sebarang node dari S (sebut: CURRENT) dan hapus dari S.

2. Hitung biaya tiap-tiap arc yang muncul dari CURRENT. Biaya tiap-tiap arc ini sama dengan jumlah h’ untuk tiap- tiap node pada akhir arc ditambah dengan biaya arc itu sendiri. Set h’(CURRENT) dengan biaya minimum yang baru saja dihitung dari stiap arc yang muncul tadi.

3. Tandai jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya minimum.

4. Tandai CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc yang baru saja ditandai tadi telah ditandai dengan SOLVED.  

5. Jika CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah, maka status baru ini harus disampaikan ke GRAPH. Kemudian tambahkan semua ancestor dari CURRENT ke S.  

Sebagai contoh, pada Gambar di atas, jelas bahwa jalur melalui C selalu lebih baik daripada melalui B. Tetapi jika biaya node E muncul, dan pengaruh perubahan yang diberikan ke node B tidak sebesar pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1), dengan demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1). Tentu saja akan lebih baik memilih jalur melalui node B (11). Tapi tidak demikian halnya apabila kemudian node D diekspan. Bisa jadi jalur dengan melalui node B akan lebih buruk lagi ketimbang jalur dengan melalui node C.

Pengertian Metode Constrain Satisfaction

Contrains Satisfaction Problem atau yang lebih dikenal dengan CSP merupakan sebuah pendekatan untuk menyelesaikan suatu masalah dengan tujuan menemukan keadaan atau objek yang memenuhi sejumlah persyaratan atau kriteria. Sebuah constrain diartikan sebagai sebuah batasan dari solusi yang memungkinkan dalam sebuah problem optimasi.

Berikut ini beberapa definisi formal dari hal-hal yang berhubungan dengan constrain satisfaction :

a. Domain

Domain berisikan nilai yang dapat diambil oleh sebuah variabel. Sebuah domain itu bersifat khusus untuk sebuah variabel. Jadi masing-masing variabel itu memiliki domainnya masing-masing. Kesepakatan umum memberi huruf kapital D untuk menyebut domain. Domain dalam caonstrain satisfaction seringnya memiliki anggota bilangan bulat. Anggota sebuah domain boleh saja bukan numerik. Hal yang dapat menjadi anggota sebuah domain adalah simbol. Contoh anggota domain yang bukan numerik adalah singkatan dari nama sebuah kota di negara Australia. Anggota domainnya adalah SA yaitu dari South Australia, NT yaitu Northern Territory, Q yaitu Queensland, V yaitu Victoria, T yaitu Tasmania, NSW yaitu New South Wales, WA yaitu Western Australia.

b. State

State didefinisikan sebagai sejumlah variable X_i yang nialainya dari domain.

c. Goal Test

Goal test pada constrain satisfaction adalah himpunan constrain atau syarat yang harus dipenuhi berupa kombinasi nilai dari subset variabel.

d. Solusi

Solusi pada constrain satisfaction adalah penetapan nilai (assigment) terhadap semua variabel sehingga semua syarat dipenuhi.

Prosedur pembatasan (Constrain Satisfaction) adalah sebagai berikut :

1. Pilihlah sebuah simpul yang belum dikembangkan dalam graph pencarian (search)

2. Terapkan aturan-aturan inferensi pembatas untuk simpul yang dipilih untuk menghasilkan semua pembatasan baru yang dimungkinkan.

3. Jika himpunan pembatas berisi sebuah kontradiksi, maka laporkanlah adanya kesuksesan.

4. Jika tidak ditemukan adanya kontradiksi atau solusi lengkap, maka solusi-solusi parsial baru yang konsisten dengan himpunan pembatas saat ini. sisipkan solusi-solusi parsial ke dalam graph pencarian.

2.3 Aplikasi Metode Constrain Satisfaction

Metode constrain satisfaction dapat diaplikasikan pada beberapa aplikasi permainan (game), penjadwalan pekerjaan, pewarnaan peta, dan sebagainya. Sebagai contoh adalah pewarnaan pada peta. Perhatikan gambar benua Australia berikut:

Misalkan WA := Western Australia

NT := Northern Territory

SA := South Australia

NSW : = New South Wales

V := Victoria

T := Tasmania

Pada gambar di atas, setiap daerah pada benua Australia merupakan variable CSP.

· Variabel = WA, NT, Q, NSW, T, V

· Domain D_i = {red(R),green(G).blue(B)}

· Constrain = daerah yang bertetangga dekat harus memiliki warna yang berbeda.

Akan didefinisikan seperti pada constrain bahwa untuk setiap wilayah yang berbatasan harus diberi pewarnaan yang berbeda. Dengan demikian, pewarnaan WA ≠ NT ≠ SA, NT ≠ Q ≠ SA, Q ≠ NSW ≠ SA, SA ≠ Q ≠ NSW ≠ V, NSW ≠ V, dan V ≠ T. Jadi (WA,NT) = {(WA,SA) = ... = (V,T) anggota dari {(red, green), (red, blue), (green, red), (green, blue),…..}.

Solusi pewarnaan D_i pada setiap variabel dapat dinyatakan sebagai berikut :

· WA = red

· NT = green

· Q = red

· NSW = green

· V = red

· SA = blue

· T = green

Dan dinyatakan seperti berikut :

Pengertian Metode Means Ends Analysis (MEA)

Means-Ends Analysis terdiri dari tiga unsur kata yakni; Mean, End dan Analysis. Mean menurut bahasa yakni berarti, banyaknya cara. Sedangkan End adalah akhir atau tujuan, dan Analysis berarti analisa atau penyelidikan secara sistematis.

Means-Ends Analysis pertama kali diperkenalkan oleh Newell dan Simon (wikipedia, 2007) dalam General Problem Solving (GPS), yang menyatakan bahwa Means-Ends Analysis adalah suatu teknik pemecahan masalah di mana pernyataan sekarang dibandingkan dengan tujuan, dan perbedaan di antaranya dibagi ke dalam sub-subtujuan untuk memperoleh tujuan dengan menggunakan operator yang sesuai.

Sedangkan menurut Kamran Zaheer (2006): “Means-Ends Analysis merupakan salah satu yang penting dalam mencari algoritma matematika dan digunakan pada semua aplikasi yang dibutuhkan seluruh pencarian untuk mendapatkan hasil. Dan MEA juga digunakan untuk keefektifan dalam pencarian distribusi dari sebuah pemikiran. Eeden (2003) suatu pemecahan masalah mempunyai beberapa situasi dengan menentukan hasil, mengidentifikasi perbedaan diantara masalah tersebut dan menentukan tindakan untuk menemukan kesamaan dari perbedaan tersebut”.

Dari uraian di atas jelas bahwa metode Means-Ends Analysis merupakan suatu model pembelajaran bervariasi antara metode pemecahan masalah dengan sintaks dalam penyajian materinya menggunakan pendekatan pemecahan masalah berbasis heuristik, yaitu memecahkan suatu masalah ke dalam dua atau lebih subtujuan. Di mana MEA mengelaborasi menjadi sub-sub masalah yang lebih sederhana, mengidentifikasi perbedaan, dan menyusun sub-sub masalahnya sehingga terjadi koneksivitas.

1.2 Teknik Means End Analysis

Teknik MEA adalah strategi untuk mengontrol pencarian dalam memecahkan masalah. Mengingat keadaan saat ini dan tujuan, suatu tindakan yang dipilih akan mengurangi perbedaan antara keduanya. Tindakan ini dilakukan pada keadaan saat ini untuk menghasilkan tujuan baru, dan proses ini secara rekursif diterapkan untuk tujuan baru dan tujuan semula.

Perhatikan bahwa, agar MEA menjadi efektif, tujuan-sistem mencari harus memiliki sarana bergaul untuk setiap jenis perbedaan terdeteksi tindakan-tindakan yang relevan untuk mengurangi perbedaan itu. Hal ini juga harus memiliki cara untuk mendeteksi kemajuan itu adalah keputusan (perubahan perbedaan antara ktual dan negara yang diinginkan), karena beberapa urutan mencoba tindakan mungkin gagal dan, karenanya, beberapa urutan alternatif mungkin dicoba.

1.3 Algoritma Means End Analysis

Model Means-Ends Analysis adalah variasi dari pembelajaran dengan pemecahan masalah dengan sintaks:

1. sajikan materi dengan pendekatan pemecahan masalah berbasis heuristic,

2. elaborasi menjadi sub-sub masalah yang lebih sederhana,

3. identifikasi perbedaan,

4. susun sub-sub masalah sehingga terjadi koneksivitas,

5. pilih strategi solusi.