Daftar Isi:
Video: BEKONANG #1 - BELAJAR KOMPUTASIONAL 2024
Seringkali, Anda menemukan pendekatan heuristik, yang berisi pada penemuan diri dan menghasilkan hasil yang cukup berguna (belum tentu optimal, tapi cukup bagus) adalah metode yang benar-benar Anda butuhkan untuk memecahkan masalah. Mendapatkan algoritma untuk melakukan beberapa pekerjaan yang dibutuhkan untuk Anda menghemat waktu dan tenaga karena Anda dapat membuat algoritme yang melihat pola lebih baik daripada manusia. Konsekuensinya, penemuan diri adalah proses yang memungkinkan algoritme untuk menunjukkan jalan yang berpotensi berguna ke solusi (namun Anda tetap harus mengandalkan intuisi dan pemahaman manusia untuk mengetahui apakah solusinya benar). Bagian berikut menjelaskan teknik yang dapat Anda gunakan untuk menghitung biaya algoritma yang menggunakan heuristik sebagai metode untuk menemukan kegunaan sebenarnya dari solusi yang diberikan.
A
ruang masalah adalah lingkungan di mana pencarian solusi terjadi. Satu set negara bagian dan operator yang digunakan untuk mengubah keadaan tersebut mewakili ruang masalah. Misalnya, perhatikan permainan ubin yang memiliki delapan ubin dalam bingkai 3-x-3. Setiap ubin menunjukkan satu bagian gambar, dan ubin mulai dalam urutan acak sehingga gambarnya acak-acakan. Tujuannya adalah untuk memindahkan satu genteng sekaligus untuk menempatkan semua ubin dengan urutan yang benar dan mengungkapkan gambarnya. .
Anda bisa mewakili teka-teki grafis dengan menggunakan grafik ruang masalah. Setiap simpul dari grafik ruang masalah menyajikan sebuah keadaan (delapan ubin pada posisi tertentu). Tepi mewakili operasi, seperti memindahkan ubin nomor delapan ke atas. Saat Anda memindahkan ubin ke atas, gambar berubah - bergerak ke keadaan lain.
Anda harus mempertimbangkan beberapa faktor saat merepresentasikan masalah sebagai sebuah ruang. Misalnya, Anda harus mempertimbangkan jumlah node maksimum yang sesuai dengan memori, yang mewakili kompleksitas ruang.
Bila Anda tidak dapat memasukkan semua node dalam memori pada satu waktu, komputer harus menyimpan beberapa node di lokasi lain, seperti hard drive, yang dapat memperlambat algoritma dengan cukup.Untuk menentukan apakah node akan muat di memori, Anda harus mempertimbangkan kompleksitas waktu, yang merupakan jumlah maksimum node yang dibuat untuk memecahkan masalah. Selain itu, penting untuk mempertimbangkan faktor keterkaitan, yang merupakan jumlah rata-rata nodus yang tercipta dalam grafik ruang masalah untuk memecahkan masalah. Pergi secara acak dan diberkati oleh keberuntungan Memecahkan masalah pencarian dengan menggunakan teknik brute force. Keuntungan dari pendekatan ini adalah Anda tidak memerlukan pengetahuan khusus domain untuk menggunakan salah satu algoritma ini. Algoritma brute force cenderung menggunakan pendekatan yang paling sederhana untuk memecahkan masalah. Kelemahannya adalah bahwa pendekatan brute force bekerja dengan baik hanya untuk sejumlah kecil simpul. Berikut adalah beberapa algoritma pencarian brute force yang umum:
Breadth-first search:
Teknik ini dimulai pada node root, mengeksplorasi masing-masing node anak terlebih dahulu, dan baru kemudian bergerak ke tingkat berikutnya. Ini berkembang setingkat sampai menemukan solusinya. Kerugian dari algoritma ini adalah bahwa ia harus menyimpan setiap simpul dalam memori, yang berarti bahwa ia menggunakan memori dalam jumlah besar untuk sejumlah besar simpul. Teknik ini bisa memeriksa duplikat node, yang menghemat waktu, dan selalu muncul dengan solusi.
- Kedalaman-penelusuran pertama: Teknik ini dimulai di simpul akar dan mengeksplorasi sekumpulan simpul anak yang terhubung sampai mencapai simpul daun. Ini berkembang cabang demi cabang sampai menemukan solusinya. Kerugian dari algoritma ini adalah bahwa ia tidak dapat memeriksa node duplikat, yang berarti bahwa ia mungkin melintasi jalur nodus yang sama lebih dari satu kali. Sebenarnya, algoritme ini mungkin tidak menemukan solusi sama sekali, yang berarti Anda harus menentukan titik cutoff agar algoritme tidak mencari dengan pasti. Keuntungan dari pendekatan ini adalah efisiensi memori.
- Pencarian dua arah: Teknik ini mencari secara bersamaan dari simpul akar dan simpul tujuan sampai dua jalur pencarian bertemu di tengahnya. Keuntungan dari pendekatan ini adalah bahwa waktu itu efisien karena menemukan solusi lebih cepat daripada banyak solusi brute force lainnya. Selain itu, ia menggunakan memori lebih efisien daripada pendekatan lainnya dan selalu menemukan solusinya. Kelemahan utama adalah kompleksitas implementasi, yang diterjemahkan ke dalam siklus pengembangan yang lebih panjang.
- Menggunakan heuristik dan fungsi biaya Bagi beberapa orang, kata
heuristik
terdengar rumit. Akan sangat mudah untuk mengatakan bahwa algoritma tersebut membuat tebakan yang terdidik dan kemudian mencoba lagi saat gagal. Tidak seperti metode brute force, algoritma heuristik belajar. Mereka juga menggunakan fungsi biaya untuk membuat pilihan yang lebih baik. Akibatnya, algoritma heuristik lebih kompleks, namun memiliki keunggulan tersendiri dalam memecahkan masalah yang kompleks. Seperti algoritma brute force, ada banyak algoritma heuristik dan masing-masing dilengkapi dengan kelebihan, kekurangan, dan persyaratan khusus tersendiri. Daftar berikut ini menjelaskan beberapa algoritma heuristik yang paling umum: Pencarian heuristik murni: Algoritma memperluas node sesuai urutan biaya mereka.Ini memelihara dua daftar. Daftar tertutup berisi simpul yang telah dieksplorasi; daftar terbuka berisi simpul yang harus dijelajahi. Pada setiap iterasi, algoritma mengembang node dengan biaya serendah mungkin. Semua simpul anaknya ditempatkan dalam daftar tertutup dan biaya simpul anak individu dihitung. Algoritma mengirimkan node anak dengan biaya rendah kembali ke daftar terbuka dan menghapus node anak dengan biaya tinggi. Akibatnya, algoritma melakukan pencarian berbasis solusi yang cerdas dan berbasis biaya.
- A * search: Algoritma melacak biaya node karena mengeksplorasinya dengan menggunakan persamaan:
- f (n) = g n) + h (n), di mana n adalah pengenal simpul.
- g (
- n) adalah biaya untuk mencapai simpul sejauh ini. h (
- n) adalah perkiraan biaya untuk mencapai tujuan dari simpul. f (
- n) adalah perkiraan biaya jalur dari n ke sasaran. Idenya adalah mencari jalan yang paling menjanjikan terlebih dulu dan menghindari jalan yang mahal. Pencarian terbaik untuk pencarian terbaik:
Algoritma selalu memilih jalur yang paling dekat dengan tujuan menggunakan persamaan:
- f (n) = h
