Langsung ke konten utama

Pencarian Heuristic (Heuristic Search)

Nama : Erlin Novianty
Kelas : 3KA33
NPM : 1C114791
Tugas : Softskill Peng. Teknologi Sistem Cerdas
Dosen : Dewi Andriyani


Pencarian Heuristic (Heuristic Search)

Pencarian Heuristik adalah pencarian yang membutuhkan informasi. Biasanya digunakan untuk pencarian jarak terpendek. 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.

Pembangkitan dan Pengujian (Generate & Test)

Definisi Generate & Test

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

Algoritma Generate & Test:

  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

Pada gambar di bawah ini, terdapat 12 kota A, B, C, D, E, F, G, H, I, J, K,Z.
Pak pos ingin mengirimkan barang dari kotaA ke kota Z.
Problem : lintasan dengan jarak terpendek?

penyelesaian :



Pendakian Bukit (Hill Climbing)

Definisi 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 lainnya yang mungkin.

Algoritma Hill Climbing:
  • Buat sebuah antrian, inisialisasi node pertama dengan root dari tree.
  • Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan yang paling kecil jaraknya.
  • Bila node pertama = GOAL, selesai.

Keuntungan Hill Climbing :
  • Membutuhkan memori yang relative kecil. Karena hanya node-node pada lintasan yang aktif saja yang disimpan.
  • Menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan Hill Climbing :
  • Algoritma akan berhenti kalau mencapai nilai lokal optimum.
  • Perlu menentukan aturan yang tepat.

Contoh

Penyelesaian :



Referensi

Komentar

Posting Komentar

Postingan populer dari blog ini

Logika Fuzzy (Fuzzy Logic)

Nama : Erlin Novianty Kelas : 3 KA33 NPM : 1C114791 Tugas : Softskill Peng. Teknologi Sistem Cerdas Dosen : Dewi Andriyani Logika Fuzzy ( Fuzzy Logic ) PENGERTIAN LOGIKA FUZZY ( FUZZY LOGIC ) Dalam bahasa inggris, fuzzy mempunyai arti kabur atau tidak jelas. Jadi, logika fuzzy adalah logika yang kabur, atau mengandung unsur ketidakpastian. Pada logika biasa, yaitu logika tegas, kita hanya mengenal dua nilai, salah atau benar, 0 atau 1. Sedangkan logika fuzzy mengenal nilai antara benar dan salah. Kebenaran dalam logika fuzzy dapat dinyatakan dalam derajar kebenaran yang nilainya antara 0 sampai 1. Logika fuzzy adalah suatu cara yang tepat untuk memetakan suatu ruang input kedalam suatu ruang output. Titik awal dari konsep modern mengenai ketidakpastian adalah paper yang dibuat oleh Lotfi A Zadeh ( 1965 ), dimana Zadeh memperkenalkan teori yang memiliki obyek-obyek dari himpunan fuzzy yang memiliki batasan yang tidak presisi dan kea...
Posting Komentar
Baca selengkapnya

3rd Assignment (Embedded Question, Conditional Sentences, Comparisons)

Nama : Erlin Novianty             Kelas : 4KA33             NPM : 1C114791 Mata Kuliah : Softskill Bahasa Inggris Bisnis 2 3rd Assignment (Embedded Question, Conditional Sentences, Comparisons) After my 1st and 2nd assignment about Tenses, so now, i will make 3rd assigment about what is Embedded Question, Conditional Sentences, Comparisons, how we can use them and also give examples about it. A.   Embedded Question Sometimes we want to use a question as part of another question or a statement, so this is called an embedded question. We can use embedded questions as part of other questions. This is sometimes called an indirect question and is often used to be polite. We can also use embedded questions as part of statements. The embedded question is a noun clause and can be used in a similar way to a noun. For example, we can use it as the subj...
Posting Komentar
Baca selengkapnya

ANIMASI

Nama               : Erlin Novianty Kelas               : 3KA33 NPM               : 1C114791 Tugas               : Softskill Peng. Animasi dan Desain Grafis Dosen              : Imam Ahmad                                                                         ANIMASI    A. Pengertian Animasi   ...
Posting Komentar
Baca selengkapnya