Metode Pencarian dan Pelacakan 2 (Heuristik)(M5)

Heuristic search merupakan metode pencarian yang memperhatikan nilai heuristic (nilai perkiraan). Teknik pencarian heuristic merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu. Heuristic adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan.

Best First Search

Best first search merupakan kombinasi dari algoritma depth first search dengan algoritma breadth first search dengan mengambil kelebihan dari kedua algoritma tersebut. Apabila pada pencarian dengan algoritma hill climbing tidak diperbolehkan untuk kembali ke node pada level pada yang lebih rendah meskipun memiliki nilai heuristic yang lebih baik, lain halnya pada algoritma best first search pencarian diperbolehkan mengunjungi node yang ada dilevel lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristic yang buruk. 

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.
                         

                         

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.
               

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. 

Strategi Means-Ends Analysis

Metode Means-Ends Analysis merupakan strategi pemecahan masalah yang dalam hal ini membagi masalah ke dalam masalah yang lebih sederhana, atau dari masalah yang khusus ke masalah yang lebih umum. Sehingga dengan begitu akan mendapatkan kesimpulan atau tujuan pembelajaran yang lebih dipahami dan dimengerti.

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. Jadi, Means-Ends Analysis adalah strategi belajar mengajar yang menganalisa suatu masalah dengan bermacam cara sehingga mendapatkan hasil atau tujuan akhir. 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.

 

Sumber :

 

http://blognyacomel.blogspot.co.id/2013/11/best-first-search.html

http://nailil-hidayah.blogspot.co.id/2013/11/kecerdasan-buatan.html

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

https://www.academia.edu/4698026/MAKALAH_MEANS-END_ANALYSIS_oleh_ROSTINTYA_DARMAYA_PERTIWI_10120098_B?auto=download