METODE PENCARIAN (ARTIFICIAL INTELEJENCE) Iterative-deepening search (IDS)

==> IDS merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori)

==> Tetapi konsekwensinya adalah time complexitynya menjadi tinggi.


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.

Keuntungan kedua adalah respon dari algoritma. Karena iterasi awal menggunakan nilai kecil untuk, mereka mengeksekusi sangat cepat. Hal ini memungkinkan algoritma untuk memasok indikasi awal hasilnya segera, diikuti oleh perbaikan dengan meningkatnya. Ketika digunakan dalam pengaturan interaktif, seperti dalam program bermain catur, fasilitas ini memungkinkan program untuk bermain setiap saat dengan langkah terbaik saat ini ditemukan dalam pencarian telah selesai sejauh ini. Hal ini tidak mungkin dengan pencarian mendalam-pertama tradisional.

Kompleksitas waktu IDS di seimbang pohon berhasil menjadi sama seperti pencarian Depth-first:.

Dalam iteratif deepening, pencarian node pada tingkat bawah diperluas sekali, orang-orang di samping tingkat bawah diperluas dua kali, dan seterusnya, sampai ke akar pohon pencarian, yang diperluas kali [2]. Jadi jumlah ekspansi dalam pencarian berulang memperdalam adalah





Untuk dan jumlah ini

6 + 50 + 400 + 3.000 + 20.000 + 100.000 = 123.456

Semua bersama-sama, berulang-ulang pencarian pendalaman dari kedalaman 1 sampai kedalaman memperluas node hanya sekitar 11% lebih dari pencarian luas-pertama atau kedalaman terbatas tunggal untuk kedalaman, saat. Faktor semakin tinggi percabangan, semakin rendah biaya overhead negara berulang kali diperluas, tapi bahkan ketika faktor percabangan adalah 2, berulang memperdalam pencarian hanya membutuhkan waktu sekitar dua kali lebih lama sebagai pencarian luas-pertama lengkap. Ini berarti bahwa kompleksitas waktu berulang memperdalam masih, dan kompleksitas ruang adalah seperti pencarian depth-first reguler. Secara umum, berulang memperdalam adalah metode pencarian disukai ketika ada ruang pencarian yang besar dan kedalaman solusi tidak diketahui. [2]



Contoh



pencarian depth-first mulai A, dengan asumsi bahwa tepi kiri dalam grafik yang ditunjukkan dipilih sebelum bagian samping kanan, dan dengan asumsi pencarian mengingat node sebelumnya dikunjungi dan tidak akan mengulangi mereka (karena ini adalah grafik kecil), akan mengunjungi node dalam urutan sebagai berikut: A, B, D, F, E, C, G. tepi dilalui dalam bentuk pencarian pohon Trémaux, struktur dengan aplikasi penting dalam teori graf.

Melakukan pencarian yang sama tanpa mengingat sebelumnya mengunjungi hasil node pada kelenjar mengunjungi di urutan A, B, D, F, E, A, B, D, F, E, dll selamanya, terperangkap dalam A, B, D, F , E siklus dan tidak pernah mencapai C atau G.

Iteratif memperdalam mencegah loop ini dan akan mencapai node berikut pada kedalaman berikut, dengan asumsi itu melanjutkan kiri-ke-kanan seperti di atas:

0: A

1: A (diulang), B, C, E

(Perhatikan bahwa berulang memperdalam kini melihat C, ketika pencarian depth-first konvensional tidak.)

2: A, B, D, F, C, G, E, F

(Perhatikan bahwa masih melihat C, tetapi itu datang kemudian. Juga mencatat bahwa ia melihat E melalui jalan yang berbeda, dan loop kembali ke F dua kali.)

3: A, B, D, F, E, C, G, E, F, B

Untuk grafik ini, karena lebih mendalam ditambahkan, dua siklus "ABFE" dan "AEFB" hanya akan mendapatkan lagi sebelum algoritma menyerah dan mencoba cabang lain.