Pencarian Depth-limited search dalam Kecerdasan Buatan

Kelemahan fatal dalam DFS (depth-first search) dalam di state spaces (ruang keadaan) yang tak terbatas dapat dikurangi dengan cara memberikan DFS suatu batas kedalaman yang telah ditentukan misalnya l (limit). Artinya, node pada kedalaman l dianggap seolah-olah tidak lagi memiliki node penerus (successors). Pendekatan ini disebut depth-limited search. Dengan adanya batas kedalaman maka akan memecahkan masalah penelusuran jalur yang tak terbatas. Sayangnya, itu juga memiliki kompensasi lain yaitu adanya potensi incompleteness jika kita memilih l < d, yang artinya, goal yang paling dangkal berada di luar batas kedalaman. Depth-limited search juga tidak akan optimal jika kita memilih l > d. Kompleksitas waktunya (execution time) adalah O(b^l) dan kompleksitas ruangnya (memori) adalah O(bl). DFS dapat dilihat sebagai kasus khusus dari depth-limited search dengan l = ∞.

Terkadang, batasan kedalaman dapat didasarkan pada pengetahuan tentang masalah tersebut. Misalnya, di peta Rumania ada 20 kota. Oleh karena itu, kita tahu bahwa jika ada solusi, itu pasti memiliki maksimum 19 untuk yang paling dalam, jadi l = 19 adalah pilihan yang memungkinkan. Tetapi kenyataannya jika kita mempelajari peta dengan teliti, kita akan menemukan bahwa kota apa pun dapat dicapai dari kota lain mana pun dengan maksimal 9 langkah. Angka ini, disebut sebagai diameter dari ruang keadaan, dan memberi kita batas kedalaman yang lebih baik, yang mengarah ke depth-limited search yang lebih efisien. Namun, untuk sebagian besar masalah, kita tidak bisa mengetahui batas kedalaman yang baik sampai kita menyelesaikan masalah tersebut.

Depth-limited search dapat diimplementasikan sebagai modifikasi sederhana pada algoritma pencarian berbasis graph atau tree secara umum. Alternatif lainnya, depth-limited search dapat diimplementasikan sebagai algoritma rekursif sederhana seperti yang ditunjukkan pada gambar di bawah ini. Perhatikan bahwa pencarian dengan kedalaman terbatas dapat diakhiri dengan dua jenis kegagalan: 1) kegagalan standar yaitu menunjukkan tidak ada solusi; 2) nilai batas kedalaman menunjukkan tidak ada solusi dalam batas kedalaman tersebut.

Implementasi rekursif dari depth limited search