Heuristic Search



Generate and Test

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Jenis-jenis Heuristic Searching:

– Generate and Test.
– Hill Climbing.
– Best First Search.
– Means-EndAnlysis, Constraint Satisfaction, dll.

 PEMBANGKITAN dan PENGUJIAN (Generate and Test)
  • Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
  • Algoritma :
1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang  dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.
  • Contoh : “Travelling Salesman Problem (TSP)”
*) Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya  boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota  dengan jarak antara tiap-tiap kota seperti berikut ini :





PENDAKIAN BUKIT (Hill Climbing)
  • 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.
  • Algoritma:
1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
b) Evaluasi keadaan baru tersebut : – Jika keadaan baru merupakan tujuan, keluar – Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. – Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
  • Contoh: TSP dengan Simple Hill Climbing Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n!/2!(n-2)!  atau sebanyak 6 kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.



Daftar Pustaka :
http://www.metode-algoritma.com

Komentar

Posting Komentar

Postingan populer dari blog ini

Negara Belgia

Gambar
ILMU SOSIAL DASAR Nama : Rizky Noer Muhammad Kelas : 1 KA 37 NPM : 19114707 Jurusan : Sistem Informasi Mata Kuliah : ISD ( Ilmu Sosial Dasar ) Belgia Belgia (secara resmi disebut Kerajaan Belgia ) adalah sebuah negara yang terletak di bagian barat benua Eropa. Negara ini merupakan negara anggota pendiri Uni Eropa dan menjadi ibukota Uni Eropa, serta organisasi internasional lainnya termasuk NATO. Belgia meliputi wilayah seluas 30.528 km² dan memiliki populasi penduduk sekitar 10,5 juta jiwa. Terletak di antara dua perbatasan budaya antara daerah Jermanik dan Latin, Belgia adalah sebuah negara dari dua kelompok etnik, Flandria dan Perancis, yang mana sebagian besarnya adalah Walloon dan sekelompok kecil adalah pembicara bahasa Jerman. Dari tinjauan Geografis, dua area terbesar dari Belgia adalah wilayah penutur bahasa Belanda yang merupakan area dari Flandria yang ada di utara, dengan 59% dari populasi secara keseluruhan, dan wilayah penutur bahasa Perancis ter...
Baca selengkapnya

Budaya Organisasi, Tipe Kepemimpinan & Strategi Organisasi

Pengertian dan Fungsi Budaya Organisasi  Budaya organisasi adalah sebuah sistem makna bersama yang dianut oleh para anggota yang membedakan suatu organisasi dari organisasi-organisasi lainnya. Sistem makna bersama ini adalah sekumpulan karakteristik kunci yang dijunjung tinggi oleh organisasi. Budaya organisasi sebagai istilah deskriptif Budaya organisasi berkaitan dengan bagaimana karyawan memahami karakteristik budaya suatu organisasi, dan tidak terkait dengan apakah karyawan menyukai karakteristik itu atau tidak. Budaya organisasi adalah suatu sikap deskriptif, bukan seperti kepuasan kerja yang lebih bersifat evaluatif. Penelitian mengenai budaya organisasi berupaya mengukur bagaimana karyawan memandang organisasi mereka:     Apakah mendorong kerja tim?     Apakah menghargai inovasi?     Apakah menekan inisiatif? Sebaliknya, kepuasan kerja berusaha mengukur respons afektif terhadap lingkungan kerja, seperti bagaima...
Baca selengkapnya

Blind Search

Gambar
Breadth-First Search Algoritma Breadth-First Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d +1. Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul-simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungi masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang telah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih d...
Baca selengkapnya