Heuristik

Sering kali, anda mendapati bahawa pendekatan heuristik, yang bergantung pada penemuan diri dan menghasilkan hasil yang cukup berguna (tidak semestinya optimum, tetapi cukup baik) adalah kaedah yang sebenarnya anda perlukan untuk menyelesaikan masalah. Mendapatkan algoritma untuk melaksanakan beberapa kerja yang diperlukan untuk anda menjimatkan masa dan usaha kerana anda boleh membuat algoritma yang melihat pola yang lebih baik daripada manusia.

Oleh itu, penemuan diri adalah proses membenarkan algoritma menunjukkan kepada anda jalan yang berpotensi berguna untuk penyelesaian (tetapi anda masih harus bergantung pada intuisi dan pemahaman manusia untuk mengetahui sama ada penyelesaiannya adalah yang betul). Bahagian berikut menerangkan teknik yang anda boleh gunakan untuk mengira kos algoritma yang menggunakan heuristik sebagai kaedah untuk mencari kegunaan sebenar dari sebarang penyelesaian yang diberikan.

Mewakili masalah sebagai ruang

A ruang masalah adalah persekitaran yang mencari penyelesaian untuk dilakukan. Satu set negeri dan operator yang digunakan untuk menukar negeri-negeri tersebut mewakili ruang masalah. Sebagai contoh, pertimbangkan permainan jubin yang mempunyai lapan jubin dalam bingkai 3-x-3. Setiap jubin memperlihatkan satu bahagian gambar, dan jubin bermula dalam beberapa susunan rawak supaya gambar itu tergelincir. Matlamatnya adalah untuk memindahkan satu jubin pada satu masa untuk meletakkan semua jubin dalam susunan yang betul dan mendedahkan gambar.

Gabungan keadaan permulaan, jubin rawak, dan keadaan matlamat - jubin dalam susunan tertentu - ialah masalah masalah. Anda boleh mewakili teka-teki secara grafik menggunakan graf ruang masalah. Setiap nod dari graf ruang masalah membentangkan keadaan (lapan jubin dalam kedudukan tertentu). Tepi-tayar mewakili operasi, seperti untuk memindahkan jubin nombor lapan ke atas. Apabila anda memindahkan jubin lapan ke atas, gambar berubah - ia bergerak ke keadaan lain.

Memenangi permainan dengan bergerak dari keadaan permulaan kepada keadaan matlamat bukan satu-satunya pertimbangan. Untuk menyelesaikan permainan dengan cekap, anda perlu melakukan tugas ini dalam jumlah paling sedikit mungkin, yang bermaksud menggunakan bilangan pengendali terkecil. Bilangan langkah minimum yang digunakan untuk menyelesaikan teka-teki adalah kedalaman masalah.

Anda harus mempertimbangkan beberapa faktor ketika mewakili masalah sebagai ruang. Sebagai contoh, anda mesti mempertimbangkan bilangan maksimum nod yang akan sesuai dengan ingatan, yang mewakili kerumitan ruang. Apabila anda tidak dapat menyesuaikan semua nod dalam memori pada satu masa, komputer mesti menyimpan beberapa nod di lokasi lain, seperti cakera keras, yang boleh melambatkan algoritma dengan ketara.Untuk menentukan sama ada nod akan sesuai dengan ingatan, anda mesti mempertimbangkan kekukuhan masa, yang merupakan bilangan maksimum nod yang dibuat untuk menyelesaikan masalah tersebut. Di samping itu, penting untuk mempertimbangkan faktor cawangan, yang merupakan bilangan purata nod yang dicipta dalam graf ruang masalah untuk menyelesaikan masalah.

Melangkah secara rawak dan diberkati oleh nasib

Memecahkan masalah carian dengan teknik brute-force mungkin. Kelebihan pendekatan ini ialah anda tidak memerlukan pengetahuan khusus domain untuk menggunakan salah satu daripada algoritma ini. Algoritma kekerasan cenderung menggunakan pendekatan yang paling mudah untuk menyelesaikan masalah. Kelemahannya ialah pendekatan kekerasan berfungsi dengan baik hanya untuk sejumlah kecil nod. Berikut adalah beberapa algoritma carian kekerasan yang biasa:

Carian rentas pertama: Teknik ini bermula pada nod akar, meneroka setiap node anak pertama, dan hanya kemudian bergerak ke tahap seterusnya. Ia berkembang tahap demi tahap sehingga ia mendapat penyelesaian. Kelemahan algoritma ini adalah bahawa ia mesti menyimpan setiap nod dalam ingatan, yang bermaksud ia menggunakan sejumlah besar memori untuk sebilangan besar nod. Teknik ini dapat memeriksa nod duplikat, yang menjimatkan masa, dan selalu muncul dengan penyelesaian.
Carian mendalam pertama: Teknik ini bermula pada nod akar dan meneroka satu set node anak yang disambungkan sehingga ia mencapai nod daun. Ia berkembang cawangan mengikut cawangan sehingga ia mendapat penyelesaian. Kelemahan algoritma ini adalah bahawa ia tidak dapat memeriksa nod pendua, yang bermaksud bahawa ia mungkin melintasi laluan nod yang sama lebih daripada satu kali. Malah, algoritma ini tidak dapat mencari penyelesaian sama sekali, yang bermaksud bahawa anda mesti menentukan titik cutoff untuk menjaga algoritma dari mencari tanpa batas. Satu kelebihan pendekatan ini ialah memori itu berkesan.
Carian silih ganti: Teknik ini mencari secara serentak dari nod akar dan nod gol sehingga kedua-dua laluan carian bertemu di tengah. Satu kelebihan pendekatan ini adalah bahawa ia adalah masa yang cekap kerana ia mendapati penyelesaiannya lebih cepat daripada banyak penyelesaian kuasa kasar lain. Di samping itu, ia menggunakan memori lebih cekap daripada pendekatan lain dan sentiasa mencari penyelesaian. Kelemahan utama adalah kerumitan pelaksanaan, diterjemahkan ke dalam kitaran pembangunan yang lebih panjang.

Menggunakan fungsi heuristik dan fungsi

Bagi sesetengah orang, perkataan heuristik hanya berbunyi rumit. Ia akan menjadi mudah untuk mengatakan bahawa algoritma itu membuat tekaan berpelajaran dan kemudian cuba lagi apabila gagal. Tidak seperti kaedah kekerasan kasar, algoritma heuristik belajar. Mereka juga menggunakan fungsi kos untuk membuat pilihan yang lebih baik. Akibatnya, algoritma heuristik lebih rumit, tetapi mereka mempunyai kelebihan tersendiri dalam menyelesaikan masalah yang rumit. Seperti algoritma kuasa kasar, terdapat banyak algoritma heuristik dan masing-masing dilengkapi dengan kelebihan, kelemahan, dan keperluan khusus. Senarai berikut menerangkan beberapa algoritma heuristik yang paling biasa:

Pencarian heuristik tulen: Algoritma memperluaskan nod mengikut kos mereka.Ia mengekalkan dua senarai. Senarai tertutup mengandungi nod yang telah dieksplorasi; senarai terbuka mengandungi nod yang masih belum dijelajahi. Dalam setiap lelaran, algoritma memperluaskan nod dengan kos yang paling rendah. Semua nod kanak-kanak diletakkan dalam senarai tertutup dan kos nod kanak-kanak individu dikira. Algoritma ini menghantar nod kanak-kanak dengan kos rendah kembali ke senarai terbuka dan memadam nod kanak-kanak dengan kos yang tinggi. Akibatnya, algoritma itu melakukan carian pintar, berdasarkan kos untuk penyelesaiannya.
A * search: Algoritma menjejaki kos nod ketika ia meneroka mereka dengan menggunakan persamaan: f (n) = g (n) + h (n), di mana
- n adalah pengenal simpul.
- g (n) adalah kos untuk mencapai nod setakat ini.
- h (n) ialah anggaran kos untuk mencapai matlamat dari nod.
- f (n) ialah anggaran kos laluan dari n ke matlamat.

Idea ini adalah untuk mencari jalan yang paling menjanjikan terlebih dahulu dan elakkan jalan yang mahal.