IDDFS
menggabungkan ruang-efisiensi depth-first search dan kelengkapan breadth-first
pencari (ketika faktor percabangan terbatas). Hal ini optimal ketika biaya
jalan adalah fungsi non-penurunan kedalaman node.
Iterative
Deepening A* (IDA*) adalah varian dari iterative deepening pencarian depth-first
search yang meminjam ide untuk menggunakan fungsi heuristik untuk mengevaluasi
biaya yang tersisa untuk sampai ke tujuan dari algoritma pencarian A*. Karena perdasarkan iterative deepening
depeth-first search, penggunaan memori lebih rendah daripada di A*, tapi tidak
seperti biasa iterative deepening depth-first search, berkonsentrasi pada
eksplorasi node yang paling menjanjikan dan dengan demikian tidak pergi ke
kedalaman yang sama mana-mana di pohon pencarian. Tidak seperti A *, IDA *
tidak menggunakan pemrograman dinamis dan oleh karena itu sering berakhir
menjelajahi node yang sama berkali-kali.
Sejauh ini, tidak ada metode yang
dibahas telah ideal; satu-satunya yang menjamin bahwa jalan akan ditemukan
memerlukan ruang eksponensial. Salah satu cara untuk menggabungkan efisiensi
ruang pencarian mendalam-pertama dengan optimalitas metode luas-pertama adalah
dengan menggunakan pendalaman berulang. Idenya adalah untuk menghitung ulang
elemen perbatasan daripada menyimpannya. Setiap recomputation bisa menjadi
pencarian mendalam-pertama, yang dengan demikian menggunakan ruang kurang.
Pertimbangkan membuat pencarian
luas-pertama ke pencarian pendalaman berulang. Hal ini dilakukan dengan
memiliki pencari depth-first, yang hanya mencari dengan kedalaman terbatas. Hal
pertama dapat melakukan pencarian mendalam-pertama yang mendalam 1 dengan
membangun jalur panjang 1 dengan cara depth-first. Kemudian dapat membangun
jalan ke kedalaman 2, maka kedalaman 3, dan seterusnya. Hal ini dapat membuang
semua perhitungan sebelumnya setiap kali dan mulai lagi. Akhirnya akan
menemukan solusi jika ada, dan, seperti yang pencacahan jalan dalam rangka,
jalan dengan busur paling sedikit akan selalu ditemukan pertama.
Ketika menerapkan pencarian
memperdalam berulang, Anda harus membedakan antara kegagalan karena kedalaman
terikat dicapai dan kegagalan yang tidak melibatkan mencapai kedalaman terikat.
Dalam kasus pertama, pencarian
harus dicoba dengan yang lebih besar kedalaman terikat. Dalam kasus kedua, itu
adalah buang-buang waktu untuk mencoba lagi dengan lebih mendalam terikat,
karena tidak ada jalan ada tidak peduli apa kedalaman. Kami mengatakan bahwa
kegagalan karena mencapai kedalaman terikat gagal wajar, dan kegagalan tanpa
mencapai kedalaman terikat gagal secara alami.
Sementara pencarian
mendalam-pertama pendalaman berulang standar menggunakan kedalaman pencari
sebagai cutoff untuk setiap iterasi, IDA * menggunakan f lebih informatif (n) =
g (n) + h (n) di mana g (n) adalah biaya untuk perjalanan dari akar ke simpul n
dan h (n) adalah perkiraan heuristik dari biaya untuk perjalanan dari n untuk
solusi.
Kode Pemograman:
Perbandingan dengan algoritma lain:
Pencarian A * salah satu yang
terbaik untuk tujuan umum algoritma pencarian graph ketika ada cara untuk memperkirakan
jarak ke tujuan. IDA* sedikit lebih lambat dibandingkan A* (ini mengeksplorasi
sama node beberapa kali karena tidak ingat kerja sebelumnya) tetapi bermanfaat
bila masalahnya adalah memori dibatasi. Pencarian A* membuat antrian besar node
yang belum dijelajahi yang dapat dengan cepat mengisi memori. Karena IDA *
tidak ingat semua simpul kecuali orang-orang di jalan saat ini memiliki profil
memori sangat kecil.
Masalah
yang jelas dengan iterative deepening adalah perhitungan terbuang yang terjadi
pada setiap langkah. Bagaimanapun, mungkin tidak seburuk yang satu mungkin
berpikir, terutama jika faktor percabangan tinggi. Pertimbangan waktu berjalan
dari algoritma.
Source:
Tidak ada komentar:
Posting Komentar