Kamis, 11 April 2013

METODE PENCARIAN (ARTIFICIAL INTELEJENCE) Depth-limited saerch (DLS)


Depth-limited saerch (DLS)


Metode ini berusaha mengatasi kelemahan DFS (tidak complete) dengan membatasi kelemahan maksimum dari suatu jalur solusi
adalah suatu algoritma untuk mengeksplorasi simpul dari grafik. Ini merupakan modifikasi dari depth-first search dan digunakan misalnya dalam algoritma iteratif memperdalam kedalaman-pertama pencarian.

umum

Seperti pencarian depth-first normal, kedalaman terbatas pencarian sebuah pencarian uninformed. Ia bekerja persis seperti depth-first search, tapi menghindari kekurangan mengenai kelengkapan dengan memberlakukan batas maksimum pada kedalaman pencarian. Bahkan jika pencarian masih bisa memperluas simpul melampaui kedalaman itu, itu tidak akan melakukannya dan dengan demikian tidak akan mengikuti jalan jauh dalam atau terjebak dalam siklus. Oleh karena itu kedalaman terbatas pencari akan mencari solusi jika dalam batas kedalaman, yang menjamin setidaknya kelengkapan pada semua grafik.

Algoritma (informal)

General

1. Menentukan titik mana harus memulai pencarian dan menetapkan kedalaman maksimum pencarian

2. Periksa apakah titik saat ini adalah negara tujuan

• Jika tidak: Melakukan apa-apa

• Jika ya: kembali

3. Periksa apakah titik saat berada dalam kedalaman maksimum pencarian

• Jika tidak: Melakukan apa-apa

• Jika ya:

1. Memperluas titik dan menyimpan semua penerusnya dalam tumpukan

2. Hubungi DLS rekursif untuk semua simpul dari stack dan kembali ke Langkah 2



ruang kompleksitas

Karena kedalaman terbatas pencarian internal menggunakan depth-first search, kompleksitas ruang adalah setara dengan normal kedalaman-pertama pencarian.



waktu kompleksitas

Karena kedalaman terbatas pencarian internal menggunakan depth-first-search, kompleksitas waktu adalah setara dengan normal kedalaman-pertama pencarian, dan O () di mana singkatan jumlah simpul dan jumlah tepi dalam grafik dieksplorasi. Perhatikan bahwa kedalaman terbatas pencarian tidak mengeksplorasi seluruh grafik, tetapi hanya bagian yang terletak dalam terikat ditentukan.



kelengkapan

Meskipun kedalaman terbatas pencarian tidak bisa mengikuti jalan panjang tak terhingga, juga tidak dapat terjebak dalam siklus, secara umum algoritma ini tidak lengkap karena tidak menemukan solusi yang terletak di luar kedalaman pencarian tertentu. Tetapi jika kedalaman pencarian maksimum dipilih untuk menjadi lebih besar dari kedalaman solusi algoritma menjadi lengkap.



optimalitas

Kedalaman terbatas pencarian tidak optimal. Ia masih memiliki masalah depth-first pencarian yang pertama kali mengeksplorasi salah satu jalan sampai akhir, sehingga mungkin menemukan solusi yang lebih mahal daripada beberapa solusi di jalan lain.

Tidak ada komentar:

Poskan Komentar