Hauristic Search


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.

1). 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 :


Alur pencarian dengan Generate and Test



2) 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.

 Sumber : 

http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html?m=1

Komentar

Posting Komentar

Postingan populer dari blog ini

Fuzzy logic

Gambar
Fuzzy logic merupakan peningkatan dari logika Boolean yang berhadapan dengan konsep kebenaran sebagian. Saat logika klasik menyatakan bahwa segala hal dapat diekspresikan dalam istilah biner (0 atau 1, hitam atau putih, ya atau tidak), logika fuzzy menggantikan kebenaran boolean dengan tingkat kebenaran. Logika Fuzzy memungkinkan nilai keanggotaan antara 0 dan 1, tingkat keabuan dan juga hitam dan putih, dan dalam bentuk linguistik, konsep tidak pasti seperti "sedikit", "lumayan", dan "sangat". Logika ini berhubungan dengan set fuzzy dan teori kemungkinan. Logika fuzzy diperkenalkan oleh Dr. Lotfi Zadeh dari Universitas California, Berkeley pada 1965. Logika fuzzy adalah suatu cara yang tepat untuk memetakan suatu ruang input ke dalam suatu ruang output. Skema logika fuzzy adalah sebagai berikut: Pada gambar dapat diketahui bahwa antara input dan output terdapat sebuah kotak hitam yang sesuai. Contoh persoalan : -        Sebua...
Baca selengkapnya

BUSINESS RELATIONSHIP MANAGEMENT

Gambar
Business relationship management   (BRM) adalah pendekatan formal untuk pemahaman, mendefinisikan, dan mendukung kegiatan antar-usaha yang terkait dengan jaringan bisnis. Manajemen hubungan bisnis terdiri dari pengetahuan, keterampilan, dan perilaku (atau kompetensi) yang membina hubungan yang produktif antara organisasi jasa ( Sumber Daya Manusia, teknologi informasi, departemen keuangan, atau penyedia eksternal) dan mitra bisnis mereka. BRM berbeda dari manajemen hubungan perusahaan dan manajemen hubungan pelanggan meskipun hal itu berkaitan. Ini adalah ruang lingkup yang lebih besar dari penghubung yang sejalan kepentingan bisnis dengan TI Penyerahan. 1. Ruang Lingkup      Manajemen hubungan bisnis terdiri dari pengetahuan, keterampilan, dan perilaku (atau kompetensi) yang membina hubungan yang produktif antara organisasi jasa (misalnya Sumber Daya Manusia , teknologi informasi , departemen keuangan, atau penyedia eksternal) dan mitra bisnis mereka. BRM...
Baca selengkapnya

Pengantar Inkscape

Pengertian Inkscape Inkscape adalah sebuah perangkat lunak editor gambar vektor yang bersifat bebas terbuka dibawah lisensi GNU GPL. Tujuan utama dari Inkscape adalah membuat perangkat grafik mutakhir yang memenuhi standar XML, SVG, dan CSS. Fungsi Inkscape Inkscape dapat digunakan untuk membuat gambar vektor untuk berbagai kebutuhan, misalnya untuk membuat gambar ilustrasi pada web, ikon untuk smartphone, gambar kartun atau animasi, membuat garis sederhana, kaligrafi, logo, brosur, dan masih banyak lagi. Format gambar yang dibuat menggunakan Inkscape sangat handal dan dapat disebarkan melalui internet dengan mudah karena ukurannya lebih kecil dibandingkan dengan format yang dibuat menggunakan aplikasi lain yang sejenis. Dukungan untuk berbagai format telah ditambahkan termasuk untuk berbagai browser dan smartphone masa kini. Bagian-bagian dari inkscape : 1.         Menu Bar Menu Bar atau dalam bahasa Indonesi sering disebut baris menu, berisi da...
Baca selengkapnya