People Innovation Excellence
 

Pencarian Depth-limited search dalam Artificial Intelligence

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 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(bl) 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

Published at :
Written By
Albert Verasius Dian Sano,S.T., M.Kom.
Subject Content Specialist
Leave Your Footprint

    Periksa Browser Anda

    Check Your Browser

    Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

    Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

    Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

    Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

    We're Moving Forward.

    This Site Is No Longer Supporting Out-of Date Browser.

    If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

    Best viewed with one of these browser instead. It is totally free.

    1. Google Chrome
    2. Mozilla Firefox
    3. Opera
    4. Internet Explorer 9
    Close