جستجوی عمق اول عمیق‌کننده تکراری

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

جستجوی عمق اول عمیق‌کننده تکراری (به انگلیسی: Iterative deepening depth-first search)، (به اختصار IDDFS) یک استراتژی جستجوی فضای حالت است که در آن یک جستجوی عمق محدود، بارها و بارها اجرا می‌شود که با هر تکرار حد عمق را افزایش می‌دهد، تا زمانی که به مقدار ِD -عمق کم عمق ترین حالت نهایی- برسد. IDDFS، مشابه جستجوی اول سطح است با این تفاوت که حافظه ی کمتری را اشغال می کند؛ در هر تکرار، گره‌هایی را که در درخت جستجو در همان سطح از جستجوی عمق اول هستند را می‌بیند، اما مرتبهٔ تجمعی برای هر گره که اولین بار دیده می‌شود، -بدون هرس در نظر بگیرید-، اول سطح است.

مشخصات[ویرایش]

الگوریتم جستجوی عمیق کننده ی تکراری کارایی الگوریتم جستجوی اول عمق در فضا را با کامل بودن الگوریتم جستجوی اول سطح (وقتی ضریب انشعاب متناهی است)، ترکیب می کند.این روش وقتی بهینه است که یک تابع هزینه ی مسیر بک تابع غیرنزولی از عمق گره باشد.

پیچیدگی فضا در این روش از O(bd) است، که در آن b ضریب انشعاب و d عمق گره ی هدف با کمترین عمق است. از آنجایی که الگوریتم جستجوی عمیق کننده ی تکراری حالت ها را چندین بار ملاقات می کند به نظر زمان را هدر می دهد. ولی در حقیقت جندان هزینه بر نیست، زیرا اکثر گره های یک درخت تولید شده، در پایین ترین سطح قرار دارند، بنابراین اهمیت چندانی ندارد که گره های بالایی چندین بار ملاقات شوند.

مهم ترین خصوصیت IDDFS در جستجوی درخت بازی این است که روش های پیشین جستجو سعی می کردند با استفاده از توابع شهودی و ابتکار جستجو را انجام دهند، مانند killer heuristic یا alpha-beta pruning، به طوری که تخمین بهتر از گره ها در آخرین جستجوی عمیق می توانست اتفاق بیفتد، و جستجو از آن جایی که در زمان کمتری انجام می شود سریع تر پیش خواهد رفت.

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

پیچیدگی زمانی IDDFS یک درخت بسیار متعادل از O(b^d) است.

در یک جستجوی عمق اول عمیق کننده ی تکراری، گره های سطح زیرین یک بار گسترش میابند، آن هایی که در سطح بعدی قرار دارند دو بار گسترش میابند، و تا جایی که تا ریشه ی درخت، d+1 بار گسترش خواهد یافت. پس تعداد گسترش ها در یک جستجوی عمیق کننده ی تکراری چنین خواهد بود:

(d+1)1+(d)b+(d-1)b^2+...+3b^{d-2}+2b^{d-1}+b^2

\sum_{i=0}^d (d+1-i)b^i

در هر حال، یک جستجوی عمیق کننده ی تکراری از عمق صفر تا عمق d فقط 11% گره بیش تر از یک جستجوی اول سطح یا یک جستجوی اول عمق با عمق d وقتی b=10 است گسترش میابد.هر چه ضریب انشعاب بزرگ تر باشد، در نهایت جمع کلی هزینه روی حالت های در حال گسترش کم تر می شود، ولی حتی وقتی که ضریب انشعاب 2 است، جستجوی عمیق کننده ی تکراری تنها دو برابر یک جستجوی اول سطح زمان می گیرد. این بدان معنی است که پیچیدگی زمانی یک الگوریتم عمیق کننده ی تکراری هنوز همان O(bd) است، و پیچیدگی فضا همان O(bd) است. به صورت کلی جستجوی عمیق کننده ی تکراری نسبت به روش های دیگر جستجو وقتی یک فضای بزرگ برای جستجو داریم و عمق نیز نامعلوم است ارجحیت دارد.

الگوریتم[ویرایش]

شبه برنامه زیر نشان می دهد IDDFS را با استفاده از DFS عمق محدود بازگشتی(DLS) اجرا شده است.

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}

جستجوی عمق محدود می تواند به صورت بازگشتی انجام شود. توجه کنید تنها لازم است گره هدف برای depth==0 چک شود، چون وقتی depth>0 باشد، DLS گره هایی را که در تکرار قبلی IDDFS دیده شده اند را گسترش می دهد.

DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth> 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return no-solution
}

جستارهای وابسته[ویرایش]

منابع[ویرایش]

پیوند به بیرون[ویرایش]