Metode Pencarian Dan Pelacakan 2

5.1 Best-First Search

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.

5.2 Problem Reduction

Problem reduction atau yang biasa dikenal dengan constraint, intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat penting dalam penyelesaian constraint satisfactionproblem yang sangat berat sehingga semua aplikasi komersial penyelesaian constraint satisfactionproblem menggunakan teknik konsistensi ini sebagai langkah dasar. Sejarah konsistensi constraint dapat ditlusuri dari peningkatan efisiensi program pengenalan gambar oleh peneliti di intelejensi semu. Pegenalan gambar melibatkan pemberian label kepada semua garis pada gambar dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang konsisten pada tahap awal. Dengan demikian memperpendek pencarian untuk pembeian nilai yang konsisten.Untuk mengilustrasikan teknik konsistensi ini akan diberikan sebuah contoh constraint satisfaction problem yang sangat sederhana.

 Anggap A < B adalah constraint antara variabel A dengan domainD_A = { 3..7} dan variabel B dengan domain D_B = { 1..5}. dengan jelas tampak bahwa bahwa untuk sebagian nilai pada D_A tidak ada nilai yang konsisten di D_B yang memenuhi constraint A < B dan sebaliknya. Niai yang demikian dapat dibuang dari domain yang berkaitan tanpa kehilangan solusi apapun. Reduksi itu aman. Didapatkan domain yang tereduksi D_A = {3,4} dan D_B = {4,5}.

Perhatikan bahwa reduksi ini tidak membuang semua pasangan yang tidak konsisten. Sebagai contoh kumpulan label (<A, 4>, <B, 4>) masihh dapat dihasilkan dari domain, tetapi untuk setiap nilai A dari D_A adalah mungkin untuk mencari nilai B yang konsisten dan sebaliknya.

Walaupun teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi, teknik konsistensi ini membantu menyelesaikan constraint satisfactionproblem dalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian maupun pada saat pencarian.

Constraint sering direpresentasikan dengan gambar graf (gambar 1) di mana setiap verteks mewakili variabel dan busur antar verteks mewakili constraint binari yang mengikat variabel-variabel yan dihubungkan dengan busur tersebut. Constraint unari diwakilkan dengan busur melingkar.

Kebanyakan solusi menggunakan pohonOR,dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang. Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.

Graf AND-OR

Pada dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND. Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi.

 Untukmendeskripsikanalgoritma Graph AND-OR kitamenggunakannilai F_UTILITY, yaitubiayasolusi.

Algoritma:

      1.    Inisialisasi graph ke node awal.

      2.    Kerjakanlangkah-langkah di bawahinihingga node awal SOLVED atausampaibiayanyalebihtinggidari F_UTILITY:

          (a.) Telusuri graph, mualaidari node awaldanikutijalurterbaik. Akumulasikankumpulan node yang adapadalintasantersebutdanbelumpernahdiekspansiataudiberi label SOLVED.

           (b.) Ambilsatu node danekspansi node tersebut. Jikatidakada successor, maka set F_UTILITY sebagainilaidari node tersebut. Bilatidakdemikian, tambahkan successor-successor dari node tersebutke graph danhitungnilaisetiap f’ (hanyagunakan h’ danabaikan g).Jika f’ = 0, tandai node tersebutdengan SOLVED.

           (c.)  Ubah f’ harapandari node baru yang diekspansi. Kirimkanperubahaninisecara backward sepanjang graph.Jika node berisisuatu arc suatu successor yang semua descendant-nyaberlabel SOLVED makatandai node itudengan SOLVED.

PadaGambar 2.33, pada langkah-1 semulahanyaadasatu node yaitu A. Node A diekspansihasilnyaadalah node B, C, dan D.Node D memilikibiaya yang lebihrendah (6) jikadibandingkandengan B dan C (9).Pada langkah-2 node D terpilihuntukdiekspansi, menjadi E dan F denganbiayaestimasisebesar 10.Sehinggakitaharusmemperbaikinilai f’ dari D menjadi 10.Kembalike level sebelumnya, node B dan C memilikibiaya yang lebihrendahdaripada D (9 < 10).Pada langkah-3, kitamenelusuri arc dari node A, ke B dan C bersama-sama. Jika B dieksploreterlebihdahulu, makaakanmenurunkan node G dan H. Kita perbaikinilai f’ dari B menjadi 6 (nilai G=6 lebihbaikdaripada H=8), sehinggabiaya AND-arc B-C menjadi 12 (6+4+2). Dengandemikiannilai node D kembalimenjadilebihbaik (10 < 12).Sehinggaekspansidilakukankembaliterhadap D. Demikianseterusnya.

2.3.2  Algoritma AO*

Algoritma AO* menggunakanstruktur Graph.Tiap-tiap node pada graph tersebutakanmemilikinilai h’ yang merupakanbiayaestimasijalurdari node itusendirisampaisuatusolusi.

Algoritma

            1.    Diketahui GRAPH yang hanyaberisi  nodeawal (sebutsaja node INIT). Hitungh’(INIT).

      2. Kerjakanlangkah-langkah di bawahinihingga INI bertanda SOLVED atausamoainilaih’(INIT) menjadilebihbesardaripada FUTILITY:

        (a)  Ekspand INIT danambilsalahsatu node yang belumpernahdiekspand (sebut NODE).

      (b)   Bangkitkan successor-successor NODE. Jikatidamemiliki successor maka set FUTULITY dengannilaih’(NODE). Jikaada successor, makauntuksetiap successor (sebutsebagai SUCC) yang bukanmerupakan ancestor dari NODE, kerjakan:

                            i  Tambahkan SUCC ke graph.

                            ii   Jika SUCC adalah terminal node, tandaidengan SOLVED dan set nilai h’-nyasamadengan 0.

                            iii   Jika SUCC bukan terminal node, hitungnilai h’.

        (c) Kirimkaninformasibarutersebutke graph, dengancara: tetapkan S adalah node yang ditandaidengan SOLVED atau node yang nilai h’-nyabarusajadiperbaiki, dansampaikannilaiinike parent-nya. Inisialisasi S = NODE. Kerjakanlangkah-langkahberikutinihingga S kosong:

                                     i .Jikamungkin, seleksidari S suatu node yang tidakmemiliki descendant dalam GRAPH yang      terjadipada S. Jikatidakada, seleksisebarang node dari S (sebut: CURRENT) danhapusdari S.

                                     ii .Hitungbiayatiap-tiap arc yang munculdari CURRENT. Biayatiap-tiap arc inisamadenganjumlah h’ untuktiap-tiap node padaakhir arc ditambahdenganbiaya arc itusendiri. Set h’(CURRENT) denganbiaya minimum yang barusajadihitungdaristiap arc yang muncultadi.

                          iii.Tandaijalurterbaik yang keluardari CURRENT denganmenandai arc yang memilikibiaya minimum.

                                     iv.Tandai CURRENT dengan SOLVED jikasemua node yang dihubungkandengannyahingga arc yang barusajaditandaitaditelahditandaidengan SOLVED.

                                     v .Jika CURRENT telahditandaidengan SOLVED ataujikabiaya CURRENT telahberubah, maka status baruiniharusdisampaikanke GRAPH. Kemudiantambahkansemua ancestor dari CURRENT ke S.

Sebagaicontoh, padaGambar 2.34 Jelasbahwajalurmelalui C selalulebihbaikdaripadamelalui B. Tetapijikabiaya node E muncul, danpengaruhperubahan yang diberikanke node B tidaksebesarpengaruhnyaterhadap node C, makajalurmelalui B bisajadilebihbaik. Sebagaicontoh, hasil expand node E, misalkan 10, makabiaya node C menjadi 11 (10+1), dengandemikianbiaya node Aapabilamemilihjalurlewat C adalah 12 (11+1). Tentusajaakanlebihbaikmemilihjalurmelalui node B (11). Tapitidakdemikianhalnyaapabilakemudian node D diekspan.Bisajadijalurdenganmelalui node B

5.3 Constraint satisfaction

Dalam kecerdasan buatan dan riset operasi, constraint satisfaction adalah proses menemukan solusi untuk satu set kendala yang memaksakan kondisi bahwa variabel harus memuaskan. Solusi Oleh karena itu vektor dari variabel yang memenuhi semua kendala.

Teknik yang digunakan dalam constraint satisfaction tergantung pada jenis kendala yang dipertimbangkan. Sering digunakan adalah kendala pada domain yang terbatas, ke titik yang kendala masalah kepuasan biasanya diidentifikasi dengan masalah berdasarkan kendala pada domain yang terbatas.
Masalah seperti ini biasanya dipecahkan melalui pencarian, khususnya bentuk kemunduran atau pencarian lokal. Kendala propagasi metode lain digunakanpada masalah tersebut, kebanyakan dari mereka tidak lengkap pada umumnya, yaitu, mereka dapat memecahkan masalah atau membuktikannya unsatisfiable, tetapi tidak selalu. Kendala metode propagasi juga digunakan dalam hubungannya dengan pencarian untuk membuat soal yang diberikan sederhana untuk memecahkan.
Jenis lain dianggap kendala berada pada bilangan real atau rasional; pemecahan masalah pada kendala-kendala dilakukan melalui eliminasi variabel atau algoritma simpleks

permasalahan pada Constraint satisfaction
Sebagai awalnya didefinisikan dalam kecerdasan buatan, kendala menghitung nilai yang mungkin satu set variabel dapat mengambil. Informal, domain terbatas adalah himpunan berhingga elemen sewenang-wenang. Sebuah kepuasan kendala masalah pada domain seperti berisi satu set variabel yang nilainya hanya dapat diambil dari domain, dan satu set kendala, kendala masing-masing menetapkan nilai diperbolehkan untuk sekelompok variabel. Sebuah solusi untuk masalah ini adalah evaluasi dari variabel-variabel yang memenuhi semua kendala. Dengan kata lain, solusi adalah cara untuk menetapkan nilai untuk setiap variabel sedemikian rupa sehingga semua kendala dipenuhi oleh nilai-nilai ini.

Dalam praktek, kendala yang sering diekspresikan dalam bentuk yang kompak, daripada enumerasi semua nilai dari variabel yang akan memuaskan kendala. Salah satu kendala yang paling sering digunakan adalah salah satu menetapkan bahwa nilai-nilai dari variabel-variabel yang terkena harus semua berbeda.

Masalah yang dapat dinyatakan sebagai masalah kepuasan kendala adalah teka-teki ratu Delapan, pemecahan masalah Sudoku, masalah satisfiability Boolean, masalah penjadwalan dan berbagai masalah pada grafik seperti masalah pewarnaan graf.

Meskipun biasanya tidak termasuk dalam definisi di atas dari masalah kepuasan kendala, aritmatika persamaan dan ketidaksetaraan terikat nilai-nilai dari  variabel yang dikandungnya dan karenanya dapat dianggap sebagai bentuk kendala. Domain mereka adalah himpunan nomor (baik bilangan bulat, rasional, atau nyata),yang tak terbatas: oleh karena itu, hubungan ini kendala mungkin tak terbatas serta, misalnya, X = Y 1 memiliki jumlah tak terbatas pasangan nilai memuaskan .
Aritmatika persamaan dan ketidaksamaan sering tidak dianggap dalam definisi "masalah kepuasan kendala", yang terbatas pada domain yang terbatas. Namun mereka sering digunakan dalam pemrograman kendala..

5.4 Means Ends Analysis

Pengertian Means-Ends Analysis

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.

Beberapa pengertian Means-Ends Analysis menurut para tokoh antara lain:

Yang mengandung pengertian bahwa MEA (Means-Ends Analysis) merupakan metode pemikiran sistem dalam penerapannya merencanakan tujuan keseluruhan, dimana tujuan tersebut dijadikan kedalam beberapa tujuan yang pada akhirnya menjadi beberapa langkah atau tindakan berdasarkan konsep yang berlaku. Dan pada setiap akhir tujuan akan berakhir pada tujuan yang lebih umum. 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”.

Selanjutnya Erman Suherman (2007) menyatakan Means-Ends Analysis merupakan model pembelajaran variasi antara metode pemecahan masalah dengan sintaks yang menyajikan materinya pada pendekatan pemecahan masalah berbasis heuristik, mengelaborasi menjadi sub-sub masalah yang lebih sederhana, mengidentifikasi perbedaan, menyususun sub-sub masalahnya sehingga terjadi koneksivitas. Kemudian Jacob (2005) menyatakan bahwa Means-Ends Analysis merupakan suatu proses untuk memecahkan suatu masalah ke dalam dua atau lebih subtujuan.

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.

Adapun dalam menerapkan langkah-langkah dalam strategi Means-Ends Analysis Glass & Holyoak (Jacob C, 2005), menyatakan bahwa komponen utama dari Means-Ends Analysis memuat dua langkah yang digunakan berulang-ulang. Yang dalam hal ini mengidentifikasi perbedaan diantara pernyataan sekarang dan tujuan yang ditentukan. Kemudian menggunakan suatu tindakan untuk mengurangi satu dari perbedaan

Kemudian Herbert Simon (Eeden, 2003)9 menyatakan bahwa langkah-langkah yang dimiliki oleh metode Means-Ends Analysis hampir memiliki persamaan dengan model pemecahan masalah (Problem Solving) karakteristik permasalahannya yakni: pertama, Problem Space (all possible configuration), dimana masalah dibagi ke dalam suatu konfigurasi beberapa kemungkinan-kemungkinan, yang kedua yakni, Problem State (the particular configuration) dimana inti dari suatu masalah tersebut di buat ke dalam beberapa bagian konfigurasi particular masalah, kemudian yang ketiga yakni, Key to solving is a problem is to choose the right operators (processes applied to change the configuration), dimana kunci untuk suatu pemecahan adalah suatu masalah yang harus dipilih dalam proses perubahan dari masalah tersebut, dan yang keempat yakni, Problem solving is a search process: Each action takes us front one part of the problem space to another, dimana suatu pemecahan masalah adalah proses pemilihan satu tindakan dari beberapa masalah yang ada.

Sedangkan Kamran (2006), menyatakan bahwa langkah-langkah dalam mempergunakan metode Means-Ends Analysis adalah sebagai berikut:

1. Mentransfer inti masalah ke dalam beberapa bagian dari masalah tersebut

2. Bagian tersebut diolah

3. Bagian masalah tersebut dikirimkan untuk mencari kesamaan dari beberapa perbedaan.

Jacob (2005) menambahkan, apabila kita mempergunakan metode Means-Ends Analysis agar dapat menyelesaikan masalah dengan cepat dan mudah, kita dapat memulainya dengan cara:

1. Mendahulukan petunjuk/arahan, dari pernyataan awal sampai pernyataan tujuan, atau,

2. Terbalik mulai dari pernyataan tujuan sampai kepada pernyataan awal.

Metode Means-Ends Analysis berdasarkan konsep di atas jelas bahwa setiap tujuan yang dicapai ada dalam cara/langkah itu sendiri untuk mendapatkan tujuan yang lebih umum dan rinci. Metode Means-Ends Analysis juga dapat mengembangkan berpikir reflektif, kritis, logis, sistematis dan kreatif.

sumber : 

http://deisyamalia.blogspot.co.id/2012/03/best-first-search.html

http://ichaajja212.blogspot.co.id/2012/10/heuristic-search-techniques-problem.html 

http://saefulnugroho.blogspot.co.id/2011/10/constraint-satisfaction.html 

http://lukman-pribadi.blogspot.co.id/p/means-ends-analysis.html