جستجوی عمق محدود

در علوم کامپیوتر جستجوی عمق محدود الگوریتمی برای کاوش رئوس گراف است. این روش در واقع نسخه‌ای از روش جستجوی اول-عمق است و برای مثال درتعمیق تکراری الگوریتم اول عمق استفاده می‌شود.

نگاه کلی

مشابه الگوریتم اول-عمق، جستجوی عمق محدود، یک جستجوی ناآگاهانه است. این جستجو دقیقاً مشابه جستجوی اول-عمق عمل می‌کند، اما با تحمیل کردن یک محدودیت حداکثری روی عمق جستجو، از مشکلاتی که مربوط به تمامیت اول-عمق است، جلوگیری می‌کند. حتی اگر جستجو هنوز هم بتواند یک رأس فراتر از آن عمق گسترش دهد، نمی‌تواند چنین کاری را انجام دهد و در نتیجه، مسیرهای با عمق نامحدود را دنبال نمی‌کند یا به عبارتی در حلقه‌ها گیر نمی‌افتد؛ بنابراین، جستجوی با عمق محدود در صورتی جواب را پیدا خواهد نمود که این جواب در فاصله اولین سطح تا عمق محدود قرار داشته باشد، که این محدودیت حداقل تمامیت را روی تمامی گراف‌ها تضمین می‌کند.

الگوریتم (غیررسمی)

رأسی را که الگوریتم باید از آن شروع کند و همچنین حداکثر عمق جستجو را مشخص کنید.
چک کنید که آیا رأس کنونی حالت هدف است:
- اگر نیست: هیچ کاری انجام ندهید.
- اگر پاسخ مثبت است: از الگوریتم خارج شوید.
چک کنید که آیا رأس کنونی در عمق کمتر از حداکثر عمق جستجو قرار دارد:
- اگر چنین نیست: هیچ کاری انجام ندهید.
- اگر پاسخ مثبت است:
  1. رأس را بسط دهید و تمامی نودهای زیرمجموعه آن را در پشته ذخیره کنید.
  2. DLS را به‌طور بازگشتی برای تمامی رئوس موجود در پشته فراخوانی کنید و به مرحله ۲ برگردید.

شبه کد

DLS(node, goal, depth) {
 if (depth>= ۰) {
 if (node == goal)
 x=goal if (goal=depth)
 return node

 for each child in expand(node)
 DLS(child, goal, depth-1)
 }

}

خصوصیات

پیچیدگی فضایی

از آن جایی که جستجوی عمق محدود در درون خود از جستجوی اول عمق استفاده می‌کند، پیچیدگی فضایی آن معادل با پیچیدگی فضایی الگوریتم جستجوی اول عمق معمولی است.

پیچیدگی زمانی

از آنجایی که الگوریتم عمق محدود، در درون دارد از جستجوی اول عمق استفاده می‌کند، پیچیدگی زمانی آن هم معادل با پیچیدگی زمانی جستجوی اول عمق است، یعنی از مرتبه( $\vert V\vert +\vert E\vert$ )O، که $\vert V\vert$ ، به معنی تعداد رئوس و $\vert E\vert$ برای تعداد یال‌های پیمایش شده در گراف استفاده می‌شوند. توجه کنید که جستجوی عمق محدود تمام گراف را پیمایش نمی‌کند، بلکه فقط بخشی را که در مرز مشخص شده قرار دارد پیمایش می‌کند.

تمامیت

با وجود اینکه جستجوی عمق محدود نمی‌تواند قطعاً مسیرهای طولانی را دنبال کند، اما از آن طرف هم در حلقه‌ها گیر نمی‌افتد، در کل این الگوریتم در صورتی که پاسخ را قبل از رسیدن به عمق جستجوی داده شده پیدا نکند کامل، نیست. اما اگر حداکثر عمق محدود بزرگتر از عمق جواب باشد، الگوریتم کامل می‌شود.

بهینگی

جستجوی عمق محدود بهینه نیست. هنوز مشکل جستجوی اول عمق که یک مسیر را تا به انتهای آن پیمایش می‌کند، دراینجا وجود دارد، در نتیجه شاید جوابی را پیدا کند که هزینه برتر از برخی جواب‌ها در مسیری دیگر باشد.

مرور ادبیات

Russell, Stuart J. ; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2

منابع

ویکی‌پدیای انگلیسی