Metode Iterative Deepening A* Iterative-Deepening A* (IDA*) search algorithm adalah pengembangan dari A*search algorithm yang dikombinasikan dengan iterative deepening search. IDA* search algorithm merupakan best-first searches yang optimal dalam hal solution cost, time, dan space. Prinsip algoritma iterative deepening search adalah melakukan depth-limited search secara bertahap dengan nilai l yang incremental . Contoh cara kerja iterative deepening search dapat dilihat pada gambar:
Pada metode IDA* search algorithm digunakan fungsi evaluasi yang sama seperti metode A* yaitu sebagai berikut:
f(n) = g(n) + h(n) (6)
Dimana: f(n) = estimasi total cost suatu path dari node awal ke node tujuan melalui node n g(n) = cost dari suatu path untuk mencapai node n dari node awal h(n) = estimasi cost suatu path
Dimana: f(n) = estimasi total cost suatu path dari node awal ke node tujuan melalui node n g(n) = cost dari suatu path untuk mencapai node n dari node awal h(n) = estimasi cost suatu path
Iteratif memperdalam kedalaman-pertama pencarian (IDS) adalah pencarian ruang strategi di mana pencarian mendalam-terbatas dijalankan berulang kali, meningkatkan batas kedalaman dengan setiap iterasi sampai mencapai, kedalaman negara tujuan dangkal. IDS setara dengan luas-pertama pencarian, tetapi menggunakan memori lebih sedikit, pada setiap iterasi, ia mengunjungi node dalam pohon pencarian dalam urutan yang sama seperti depth-first search, tapi urutan kumulatif di mana node pertama kali mengunjungi secara efektif luasnya -pertama.
IDS menggabungkan depth-first pencari ruang-efisiensi dan kelengkapan luas-pertama pencarian ini (ketika faktor percabangan terbatas). Ini adalah optimal ketika biaya jalan adalah fungsi non-penurunan kedalaman node.
Kompleksitas ruang IDS adalah, di mana merupakan faktor percabangan dan kedalaman dangkal gawang. Karena berulang memperdalam kunjungan menyatakan beberapa kali, hal itu mungkin tampak sia-sia, tapi ternyata menjadi tidak begitu mahal, karena di pohon sebagian besar node berada di tingkat bawah, sehingga tidak terlalu menjadi masalah jika tingkat atas yang dikunjungi beberapa kali.
Keuntungan utama dari IDS dalam mencari permainan pohon adalah bahwa pencarian sebelumnya cenderung meningkatkan heuristik yang biasa digunakan, seperti heuristik pembunuh dan pemangkasan alpha-beta, sehingga perkiraan yang lebih akurat dari skor berbagai node pada pencarian kedalaman akhir dapat terjadi, dan pencarian selesai lebih cepat karena dilakukan dalam urutan yang lebih baik. Misalnya, alpha-beta pemangkasan yang paling efisien jika ia mencari langkah terbaik pertama.
IDS menggabungkan depth-first pencari ruang-efisiensi dan kelengkapan luas-pertama pencarian ini (ketika faktor percabangan terbatas). Ini adalah optimal ketika biaya jalan adalah fungsi non-penurunan kedalaman node.
Kompleksitas ruang IDS adalah, di mana merupakan faktor percabangan dan kedalaman dangkal gawang. Karena berulang memperdalam kunjungan menyatakan beberapa kali, hal itu mungkin tampak sia-sia, tapi ternyata menjadi tidak begitu mahal, karena di pohon sebagian besar node berada di tingkat bawah, sehingga tidak terlalu menjadi masalah jika tingkat atas yang dikunjungi beberapa kali.
Keuntungan utama dari IDS dalam mencari permainan pohon adalah bahwa pencarian sebelumnya cenderung meningkatkan heuristik yang biasa digunakan, seperti heuristik pembunuh dan pemangkasan alpha-beta, sehingga perkiraan yang lebih akurat dari skor berbagai node pada pencarian kedalaman akhir dapat terjadi, dan pencarian selesai lebih cepat karena dilakukan dalam urutan yang lebih baik. Misalnya, alpha-beta pemangkasan yang paling efisien jika ia mencari langkah terbaik pertama.
Tidak ada komentar:
Posting Komentar