Algoritma Depth Limited Search (DLS) Dalam Artificial Intelligent

Metode searching pada kecerdasan buatan digunakan untuk pencarian solusi atau searching problem space bukan searching data dalam sebuah struktur data. Dengan proses searching ini akan ditemukan sebuah penyelesaian dan akan terbentuk sebuah solution space. Terdapat 2 metode pencarian yaitu:

• blind/ un-informed search: digunakan saat tidak ada data atau informasi awal dalam proses pencarian. Contohnya yaitu Dept Limited Search, Dept First Search, dsb.
• Heuristic search : pencarian dengan menggunakan infromasi atau pencarian berbasis heuristic. Contoh dari heuristic searh ini adalah Best First Seacrh dan A*.

Yang akan dibahas kali ini adalah salah satu metode blind/ un-informed search yaitu Dept Limited Search

Apa Itu Dept Limited Search

Depth Limited Search merupakan salah satu algoritma pencarian dalam menemukan solusi adalah pencarian yang berusaha mengatasi kelemahan DFS dengan membatasi kedalaman maksimum.

Algortima ini dijalankan dengan membangkitkan pohon pencarian secara dinamis. Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree.

Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisialisasikan batas depth pada level tertentu semenjak awal pencarian.

Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor. Sebelum menggunakan DLS, terlebih dahulu harus diketahui berapa level maksimum dari suatu solusi.

Kelebihan dan Kelemahan DLS:

Kelebihan DLS ini adalah lebih baik daripada DFS, dimana dalam DLS mwngatasi kelemahan dari DFS dan untuk kelemahanya, jika batasan kedalaman terlalu kecil, DLS tidak dapat juga menemukan solusi yang ada.

Artinya DLS bisa menjadi tidak complete jika batasan kedalamannya lebih kecil dibandingkan dengan level solusinya.

Langkah-langkah dalam Dept Limited Search adalah sebagi berikut:

1. Pertama yaitu tentukan kedalaman simpul yang akan dicari
2. Kunjungi simpul a atau simpul awal.
3. lalu kunjungi simpul b yang bertetangga dengan simpul a, yang berada di kedalaman pohon <= batas.
4. Ulangi Dept Limited Search mulai dari simpul b ke simpul yang bertetangga. (Mencari simpul dari atas kebawah lalu ke tetangga dari b dst.)
5. Ketika mencapai simpul kedalaman s sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir.
6. Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi dalam kedalaman ponon <= batas.

Contoh dept limited search dan penjelasannya

Bila simpul awal adalah 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 4, 8, 5, 3, 6,.7

penjelasan secara singkat adalah jika kedalaman 3 adalah 5,6,7 maka untuk sampai pada kedalaman 3 simpul-simpul mana saja yang akan dilalui untuk pertama yaitu 1,2,5 lalu simpul kedua yaitu 1,3,6 dan ketiga adalah 1,4,7 dan hasil akir ditulis satu kali saja tidak perlu mengulang angka. Maka hasilnya adalah 1,2,3,4,5,6,7.