Pencarian Heuristik dan A*

Pencarian heuristik menggunakan estimasi spesifik masalah dari biaya yang tersisa menuju tujuan untuk memandu status mana yang akan dieksplorasi terlebih dahulu; A* adalah algoritma kanoniknya, memperluas status berdasarkan urutan jumlah biaya-sejauh-ini dan estimasi biaya-yang-akan-datang.

Definition

Pencarian heuristik adalah pencarian terinformasi yang mengurutkan batas menggunakan fungsi evaluasi yang menggabungkan biaya yang diketahui dari awal dengan estimasi heuristik dari biaya yang tersisa; A* menggunakan f(n) = g(n) + h(n) dan optimal ketika h dapat diterima.

Scope

Topik ini mencakup strategi pencarian terinformasi (heuristik), yang berpusat pada pencarian terbaik-pertama dan algoritma A*, termasuk desain dan properti fungsi heuristik (keterterimaan, konsistensi/monotonisitas), jaminan optimalitas dan efisiensi yang diberikan oleh properti ini, serta varian terbatas memori seperti A* pendalaman-iteratif (IDA*). Ini membahas bagaimana heuristik dibangun (masalah yang direlaksasi, basis data pola) dan bagaimana heuristik menukar akurasi dengan komputasi. Pembelajaran heuristik dari data termasuk dalam subbidang pembelajaran mesin.

Core questions

• Apa yang membuat heuristik dapat diterima, dan mengapa keterterimaan menjamin optimalitas A*?
• Bagaimana konsistensi (monotonisitas) memperkuat jaminan dan mencegah perluasan ulang node?
• Bagaimana heuristik yang baik dirancang, misalnya dari versi masalah yang direlaksasi?
• Bagaimana varian terbatas memori seperti IDA* mempertahankan optimalitas dengan ruang terbatas?

Key concepts

• fungsi evaluasi f = g + h
• heuristik yang dapat diterima
• heuristik konsisten (monoton)
• pencarian terbaik-pertama serakah
• pencarian A*
• A* pendalaman-iteratif (IDA*)
• dominasi heuristik
• masalah yang direlaksasi dan basis data pola

Key theories

Optimalitas A* di bawah heuristik yang dapat diterima

Ketika heuristik h tidak pernah melebih-lebihkan biaya sebenarnya yang tersisa, A* memperluas node dengan meningkatkan f = g + h dan dijamin mengembalikan jalur dengan biaya terendah; di antara algoritma yang menggunakan informasi heuristik yang sama, A* adalah yang paling efisien secara optimal.

Desain heuristik melalui relaksasi

Heuristik yang dapat diterima dapat diturunkan secara sistematis dengan memecahkan versi masalah yang direlaksasi (satu dengan batasan tindakan yang lebih sedikit), karena biaya pasti dari masalah yang lebih mudah adalah batas bawah pada masalah asli; heuristik yang mendominasi (lebih terinformasi) memperluas lebih sedikit node.

Pencarian heuristik terbatas memori

A* pendalaman-iteratif melakukan pencarian mendalam-pertama berturut-turut yang dibatasi oleh ambang batas biaya-f yang meningkat, mencapai optimalitas seperti A* dengan memori linier dalam kedalaman solusi.

Clinical relevance

Pencarian heuristik menggerakkan penemuan rute dalam peta dan permainan, perencanaan gerak dalam robotika, dan mesin pencari di dalam perencana otomatis dan pemecah teka-teki; seni praktis desain heuristik secara langsung menentukan apakah masalah besar dapat diselesaikan dalam waktu yang dapat diterima.

History

Algoritma A* diperkenalkan oleh Hart, Nilsson, dan Raphael (1968), memberikan dasar optimalitas formal pada pencarian heuristik. Monograf Pearl tahun 1984, Heuristics, memberikan perlakuan teoretis definitif, dan IDA* Korf tahun 1985 mengatasi biaya memori A*. Hasil-hasil ini tetap menjadi materi inti dalam pendidikan AI.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

Apa itu heuristik yang dapat diterima?

Heuristik dapat diterima jika tidak pernah melebih-lebihkan biaya sebenarnya untuk mencapai tujuan dari status apa pun. Keterterimaan adalah kondisi di mana A* dijamin menemukan solusi optimal (biaya terendah).

Apa perbedaan antara pencarian terbaik-pertama serakah dan A*?

Pencarian terbaik-pertama serakah memperluas status yang tampak paling dekat dengan tujuan berdasarkan heuristik saja (h), yang cepat tetapi bisa jauh dari optimal. A* menambahkan biaya aktual yang dikeluarkan sejauh ini (g), memperluas dengan f = g + h, yang mempertahankan optimalitas ketika heuristik dapat diterima.