Pencarian Depth First dalam Kecerdasan Buatan

Pencarian depth-first selalu menurunkan node terdalam di jalur aktif saat ini dari pohon pencarian.

Pencarian depth first pada pohon biner. Areayang belum dijelajahi ditampilkan dalam warna abu-abu terang. Node-node tanpa turunan di jalur sebelumnya dihapus dari memori. Node pada kedalaman 3 tidak memiliki turunan dan M adalah satu-satunya node goal (tujuan).

Proses pencarian diilustrasikan pada gambar di atas. Pencarian berproses menuju ke level terdalam dari pohon pencarian, hingga di mana node tidak memiliki turunan lagi dan baru kembali naik ke atas dan berpindah ke jalur berikutnya. 

Kalau pencarian breadth-first menggunakan antrian FIFO (first in first out), maka pencarian depth-first ini menggunakan antrian LIFO (last in first out).

Antrian LIFO berarti bahwa node yang baru dibuat dipilih untuk diturunkan (ekspansi). Node baru ini menjadi node terdalam yang belum diturunkan (diekspansi) karena node ini adalah satu level lebih dalam dari induknya — begitu terus prosesnya berulang-ulang sampai tidak ada node turunan lagi.

Adalah praktik yang umum untuk menerapkan pencarian depth-first dengan menggunakan fungsi rekursif atau fungsi yang memanggil dirinya sendiri pada tiap-tiap node anak di dalamnya. (Algoritma depth-first rekursif yang menggabungkan depth limit ditunjukkan pada gambar di bawah ini.)

Implementasi rekursif pencarian pohon depth-limited

Pencarian pohon depth-first dapat dimodifikasi tanpa cost memori tambahan sehingga algoritma ini akan memeriksa state/node baru dan membandingkan terhadap node-node pada jalur yang sama mulai dari root hingga ke node saat ini; ini menghindari loop yang tak terbatas dalam state space yang terbatas (ruang keadaan atau semua kemungkinan node yang akan dicari) tetapi tidak menghindari adanya jalur redundan. Dalam state space (ruang keadaan) tak terbatas, algoritma ini akan gagal jika menelusuri jalur yang tidak berisi node goal (tujuan).

Pencarian depth first tidak optimal. [Lihat kriteria kinerja algoritma pencarian pada artikel Pencarian Breadth First dalam Kecerdasan Buatan  di bagian catatan akhir]. Sebagai contoh, pada gambar paling atas, pencarian depth first akan menjelajahi seluruh subtree kiri bahkan jika node C adalah node goal (tujuan). Jika node J juga merupakan node goal (tujuan), maka pencarian depth first akan memilihnya sebagai solusi, bukan C, yang akan menjadi solusi meskipun C lebih baik; karenanya, pencarian depth first tidak optimal.

Kompleksitas waktu pencarian pohon depth first, dapat menurunkan semua node O(b^m) di pohon pencarian, di mana m adalah kedalaman maksimum dari node manapun; dan ini bisa jauh lebih besar dari ukuran state space (ruang keadaan). Perhatikan bahwa m itu sendiri bisa jauh lebih besar dari d (kedalaman dari solusi yang terdangkal) dan bisa tidak terbatas kecuali jika kedalaman pohon dibatasi.

Sampai disini, pencarian depth first tampaknya tidak memiliki keuntungan yang jelas dibandingkan pencarian breadth first, jadi mengapa kita mempelajarinya? Alasannya adalah kompleksitas ruang/memori. Untuk pencarian pohon depth first perlu menyimpan hanya satu jalur dari root ke node leaf (node paling ujung yang tidak ada turunan), bersama dengan node sibling (node di sebelahnya) yang belum diturunkan (diekspansi) yang tersisa untuk setiap node yang berada dalam jalur yang sama. Setelah sebuah node telah diturunkan, node tersebut dapat dihapus dari memori segera setelah semua turunannya dikunjungi. (Lihat gambar paling atas). Untuk state space (ruang keadaan) dengan percabangan faktor b dan kedalaman maksimum m, pencarian depth first membutuhkan penyimpanan node-node O(b^m).

Menggunakan asumsi yang sama seperti pada tabel dalam artikel sebelumnya: Pencarian Breadth First dalam Kecerdasan Buatan, dan dengan asumsi node pada kedalaman yang sama dengan node goal (tujuan) yang paling ujung (tidak memiliki node turunan lagi), kita bisa menemukan bahwa pencarian depth first hanya akan membutuhkan 156 kilobyte dan bukannya 10 exabytes pada kedalaman d = 16, dan ini adalah 7 triliun kali lebih sedikit ruang/memori. Hal inilah yang menyebabkan pencarian pohon depth first sebagai dasar penarik banyak bidang lain dalam kecerdasan buatan (AI), termasuk dalam bidang constraint satisfaction, propositional satisfiability, dan logic programming.

Varian pencarian depth-first yang disebut pencarian backtracking menggunakan memori yang lebih sedikit. (Lihat Bab 6 untuk lebih jelasnya.) Dalam pencarian backtracking, hanya satu node turunan yang dihasilkan dan bukan semua node turunannya; setiap node yang diturunkan akan mengingat turunan mana yang akan dihasilkan berikutnya. Dengan cara ini, hanya O(m) memori yang diperlukan dibanding dengan O(bm).