Pencarian Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan(completeness).
Fungsi heuristic digunakan untuk mengevaluasi keadaan-keadaan problem individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
· Jenis-jenisHeuristic Searching:
–Generate and Test.
–Hill Climbing.
–Best First Search.
–Alpha Beta Prunning,Means-End-Anlysis,ConstraintSatisfaction, Simulated Annealing, dll
Permasalahan pencariaan adalah merupakan yang sering dijumpai oleh peneliti di bidang kecerdasan buatan. Permasalahan ini merupakan hal penting dalam menentukan keberhasilan system kecerdasan buatan.
Terdapat beberapa metode pencarian, pertama adalah metode yang hanya berusaha mencari kemungkinan penyelesaian. Metode yang termasuk pada bagian ini adalah dept-first search, hill climbing, breadth first search, beam search dan best first search. Kedua adalah metode yang lebih kompleks yang akan mencari jarak terpendek. Metode yang termasuk pada bagian ini adalah british museum procedure, branch and bound, dynamic programming dan A*. yang ketiga adalah beberapa procedure atau metode yang diterapkan saat berhadapan dengan musuh. Metode pada bagian ini adalah minimax search, alpha beta pruning. Diatas adalah beberapa contoh metode yang digunakan untuk menyelesaikan permasalahan pencarian. Pada makalah ini akan dijelaskan metode Best First Search.
Metode pencarian dikatakan penting untuk menyelesaikan permasalahan karena setiap state (keadaan) menggambarkan langkah-langkah untuk menyelesaikan permasalahan.
Metode pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, dimana setiap state menggambarkan kemungkinan posisi pada suatu saat.
Metode pencarian adalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif.
v Best-First Search
Sesuai dengan namanya, Best-First Search membangkitkan simpul berikutnya dari sebuah simpul (yang sejauh ini terbaik diantara semua leaf nodes yang pernah dibangkitkan. Penentuan simpul teraik dapat dilakukan dengan menggunakan informasi berupa biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut. Biaya perkiraan tersebut dapat diperoleh dengan menggunakan suatu fungsi yang disebut fungsi heuristic.
Terdapat dua jenis algoritma Best-First Search, yaitu:
1) Greedy Best_-First Search yang hanya memperhitungkan biaya perkiraan saja; dan
2) algoritma A* yang memperhitungkan gabuangan dua biaya, biaya sebenarnya dan biaya perkiraan.
Secara umum berikut adalah pseudocode algoritma Best-First Search :
ü OPEN berisi initial state dan CLOSED masih kosong.
ü Ulang sampai goal ditemukan atau sampai tidak ada nodes 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 suksesor dari simpul tersebut
e. Untuk setiap suksesor kerjakan :
i. Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat parent atau orang tuanya.
ii. Jika suksesor tersebut sudah pernah dibangkitkan, ubah parentnya jika jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya, perbarui biaya untuk suksesor tersebut dan nodes lain yang berada di level bawahnya.
Pada algoritma tersebut diatas, OPEN adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah dibangkitkan dan nilai heuristiknya telah dihitung tapi belum terpilih sebagai simpul terbaik (best node). Dengan kata lain, OPEN berisi simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka) untuk terpilih sebagai simpul terbaik. Sedangkan CLOSED adalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik. Artinya, CLOSED berisi simpul-simpul tidak mungkin terpilih sebagi simpul terbaik (peluang untuk terpilih sudah tertutup).
1. Greedy Best_First Search
Greedy Best First Search hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni:
f(n) = h(n)
· di mana h(n)= perkiraan biaya dari simpul n ke goal.
· Biaya yang sebenarnya (actual cost) tidak diperhitungkan.
· Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya maka algoritma ini menjadi 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.
2. A* Search
· Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greedy Best First Search.
· Algoritma ini memperhitungkan biaya dari biaya sebenarnya ditambah dengan biaya perkiraan.
· Dalam notasi matematika dituliskan sebagai:
f(n) = g(n) + h(n)
· g(n) = biaya sebenarnya untuk mencapai simpul n
· h(n) = perkiraan biaya dari simpul n ke goal.
· f(n) = perkiraan total biaya jalur yang melalui simpul n ke goal.
Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.