Pencarian Berbentuk /heuristik search dan Eksplorasi

3.1.) Strategi pencarian berbentuk / heuristic search strategy :

         Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).

• greedy best first search 

          Algoritma ini Merupakan jenis Best First Search yang hanya mempertimbangkan harga perkiraan (estimated cost) yaitu f(n) = h(n). Sedangkan harga sesungguhnya tidak digunakan. Sehingga solusi yang dihasilkan tidak optimal. Algoritma greedy ini membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

• A search

          Bentuk dari Best First Search yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).

f(n) = g(n) + h(n)

3.2.) Fungsi heuristik

      Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

3.3 ) Algoritma pencarian lokal dan masalah optimisasi : 

• hill climbing search

          Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.

• simulated annealing search 

           Simulated annealing (SA) adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu.Simulated Annealing berjalan berdasarkan analogi dengan proses annealing yang telah dijelaskan di atas. Pada awal proses SA, dipilih suatu solusi awal, yang merepresentasikan kondisi materi sebelum proses dimulai.

• local beem search

          Beam Search adalah algoritma pencarian heuristik yangmerupakan optimasi dari pencarian best-first search yang mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah solusiparsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.

Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :

a. Masalah yang akan di selesaikan
    Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.

b. Kumpulan aturan-aturan heuristik untuk pemangkasan
    Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.

c. Memori dengan kapasitas yang terbatas
    Adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi tidak akan melebihi memori yang tersedia.

     Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini jauh lebih sedikit daripada metode yang mendasari mtode pencarian ini. Kelemahan utama Beam Search adalah metode pencarian ini mungkin tidak dapat mencapai tujuan/hasil yang optimaldan bahkan mungkin tidak mencapai tujuan sama sekali.

• Genetic Algoritma

        Genetic Algorithm(atau GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

3.4 ) Agen pencarian online dan lingkungan yang tidak diketahui

Sumber : 

https://blogaqu.wordpress.com/2009/11/09/penerapan-greedy-best-first-search-dalam-implementasi-pencarian-lintasan-terpendek-dan-efisien-berdasarkan-jalur-dan-tarif-relatif-angkutan-kota-angkot-dari-pancoran-ke-manggarai/

http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/

https://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html

https://id.wikipedia.org/wiki/Simulated_annealing

http://principessaprincipe.blogspot.co.id/2011/05/beam-search.html