نمایش مبدأ برای جستجوی عمق اول ژرفایش تکراری

{{ویکی‌سازی}}
{{Infobox Algorithm
|class=[[الگوریتم جستجو]]
|image=
|caption=
|data=[[درخت (ساختار داده)]]، [[گراف (ساختار داده)]]
|time=<math>O(b^d)</math>, where <math>b</math> is the branching factor and <math>d</math> is the depth of the shallowest solution
|space=<math>O(d)</math>{{rp|5}}
|optimal=yes (for unweighted graphs)
|complete=yes
}}
{{الگوریتم پیمایش درخت}}
'''جستجوی عمق اول ژرفایش تکراری''' {{انگلیسی|''Iterative deepening depth-first search''}}، {{به اختصار| IDDFS}} یا '''جستجوی عمق-اول با ژرفایش تکراری'''<ref>{{cite journal|last=Korf|first=Richard|year=1985|title=Depth-first Iterative-Deepening: An Optimal Admissible Tree Search|journal=Artificial Intelligence|volume=27|pages=97–109|doi=10.1016/0004-3702(85)90084-0}}</ref> یا '''جستجوی عمق-اول تعمیق تکراری''' یک استراتژی [[جستجوی فضای حالت]] است که در آن یک [[الگوریتم جستجوی عمق اول|جستجوی عمق محدود]]، بارها و بارها اجرا می‌شود که با هر تکرار حد عمق را افزایش می‌دهد، تا زمانی که به مقدارِ D -عمق کم عمق‌ترین حالت-نهایی برسد. آی‌دی‌دی‌اف‌اس، مشابه [[الگوریتم جستجوی اول سطح|جستجوی اول سطح]] است با این تفاوت که حافظهٔ کمتری را اشغال می‌کند؛ در هر تکرار، گره‌هایی را که در [[جستجوی درختی|درخت جستجو]] در همان سطح از [[جستجوی عمق اول]] هستند را می‌بیند، اما مرتبهٔ تجمعی برای هر گره که اولین بار دیده می‌شود، بدون هرس در نظر بگیرید-، اول سطح است.<ref name="re1985">{{Cite journal|last=KORF|first=Richard E.|year=1985|title=Depth-first iterative deepening|url=https://cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf|language=en|publication-date=1985}}</ref>

== الگوریتم برای گراف‌های جهت‌دار ==
شبه‌کد زیر آی‌دی‌دی‌اف‌اس را نشان می‌دهد که براساس یک دی‌اف‌اس محدودعمق بازگشتی (به نام DLS) برای [[گراف جهت‌دار|نمودارهای جهت‌دار]] پیاده‌سازی شده‌است. این پیاده‌سازی آی‌دی‌دی‌اف‌اس برای گره‌هایی که قبلاً بازدید شده‌اند حساب نمی‌کند و بنابراین برای [[گراف (ریاضی)|گراف‌های بدون‌جهت]] کارنمی‌کند.

  {{چپ‌چین}}

 '''function''' IDDFS(root) '''is'''
     '''for''' depth '''from''' 0 '''to''' ∞ '''do'''
         found, remaining ← DLS(root, depth)
         '''if''' found ≠ '''null''' '''then'''
             '''return''' found
         '''else if''' not remaining '''then'''
             '''return''' '''null'''
 
 '''function''' DLS(node, depth) '''is'''
     '''if''' depth = 0 '''then'''
         '''if''' node is a goal '''then'''
             '''return''' (node, '''true''')
         '''else'''
             '''return''' ('''null''', '''true''')    ''(Not found, but may have children)''
 
     '''else if''' depth > 0 '''then'''
         any_remaining ← '''false'''
         '''foreach''' child '''of''' node '''do'''
             found, remaining ← DLS(child, depth−1)
             '''if''' found ≠ null '''then'''
                 '''return''' (found, '''true''')   
             '''if''' remaining '''then'''
                 any_remaining ← true    ''(At least one node found at depth, let IDDFS deepen)''
         '''return''' ('''null''', any_remaining)

{{پایان چپ‌چین}}

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

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

== مشخصات ==
جستجوی عمق اول ژرفایش تکراری کارایی-فضایی الگوریتم جستجوی عمق-اول و [[الگوریتم جستجوی سطح اول]] (وقتی [[ضریب انشعاب]] متناهی است)، را ترکیب می‌کند. این روش وقتی بهینه است که یک تابع هزینهٔ مسیر بک تابع غیرنزولی از عمق گره باشد.{{نیازمند اسناد|date=نوامبر ۲۰۲۲}} اگر راه حلی وجود داشته باشد، مسیر راه حلی با کمترین کمان را پیدا می‌کند.<ref>{{cite web|author1=David Poole|author2=Alan Mackworth|title=3.5.3 Iterative Deepening‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition|url=https://artint.info/2e/html/ArtInt2e.Ch3.S5.SS3.html|website=artint.info|access-date=29 November 2018}}</ref>

پیچیدگی فضا در این روش از <math>O(bd)</math> است، که در آن b [[ضریب انشعاب]] و d عمق گرهٔ هدف با کمترین عمق است. از آنجایی که الگوریتم جستجوی ژرفایش تکراری حالت‌ها را چندین بار ملاقات می‌کند به نظر زمان را هدر می‌دهد. ولی در حقیقت جندان هزینه بر نیست، زیرا اکثر گره‌های یک درخت تولید شده، در پایین‌ترین سطح قرار دارند، بنابراین اهمیت چندانی ندارد که گره‌های بالایی چندین بار ملاقات شوند.<ref name="rn3">{{Russell Norvig 2003}}</ref>

مهم‌ترین خصوصیت آی‌دی‌دی‌اف‌اس در جستجوی [[درخت بازی]] این است که روش‌های پیشین جستجو سعی می‌کردند با استفاده از توابع شهودی و ابتکار جستجو را انجام دهند، مانند چابک‌یابی قاتل ([//en.wikipedia.org/w/index.php?title=Killer_heuristic&oldid=380816104 killer heuristic]) یا [[هرس آلفا بتا|هرس آلفا-بتا]]، به‌طوری‌که تخمین بهتر از گره‌ها در آخرین جستجوی عمیق می‌توانست اتفاق بیفتد، و جستجو از آن جایی که در زمان کمتری انجام می‌شود سریع تر پیش خواهد رفت.

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

== تحلیل مجانبی ==
=== پیچیدگی زمانی ===
[[زمان اجرای الگوریتم|پیچیدگی زمانی]] آی‌دی‌دی‌اف‌اس یک درخت بسیار متعادل از <math>O(b^d)</math> است، که در آن b عامل انشعاب و d عمق هدف است.

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

<math>{\displaystyle b^{d}+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^{2}+db+(d+1)=\sum _{i=0}^{d}(d+1-i)b^{i}}</math>

که در آن <math>{\displaystyle b^{d}}</math> تعداد انبساط‌ها در عمق d, <math>{\displaystyle 2b^{d-1}}</math> تعداد انبساط‌ها در عمق d-1 و غیره است. فاکتورگیری <math>{\displaystyle b^{d}}</math> نتیجه پاین را می‌دهد

<math>{\displaystyle b^{d}(1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+db^{1-d}+(d+1)b^{-d})}</math>

<math>{\displaystyle x={\frac {1}{b}}=b^{-1}}</math>

<math>{\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})}</math>

<math>{\displaystyle b^{d}(1+2x+3x^{2}+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)}</math>

<math>{\displaystyle b^{d}(1-x)^{-2}=b^{d}{\frac {1}{(1-x)^{2}}}}, for {\displaystyle abs(x)<1}{\displaystyle abs(x)<1}</math>

<math>{\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})\leq b^{d}(1-x)^{-2}}, for {\displaystyle abs(x)<1}{\displaystyle abs(x)<1}</math>

از اینرو زمان اجرای جستجوی عمقی تکراری اول عمق <math>O(b^d)</math> است.

=== پیچیدگی فضا ===
پیچیدگی فضای آی‌دی‌دی‌اف‌اس، <math> {\displaystyle O(d)}</math>  است که d عمق هدف است.

==== اثبات ====
از آنجایی که آی‌دی‌دی‌اف‌اس، در هر نقطه‌ای، درگیر یک جستجوی عمقی است، فقط باید پشته‌ای از گره‌ها را ذخیره کند که نشان‌دهنده شاخه درختی است که در حال گسترش است. از آنجایی که راه حلی با طول بهینه پیدا می‌کند، حداکثر عمق این پشته d است و بنابراین حداکثر مقدار فضا <math> {\displaystyle O(d)}</math> است.

به‌طور کلی، زمانی که فضای جستجوی زیادی وجود دارد و عمق راه حل مشخص نیست، عمیق کردن تکراری روش جستجوی ترجیحی است.<ref name="re1985"/>

در هر حال، یک جستجوی ژرفایش تکراری از عمق صفر تا عمق d فقط ۱۱٪ گره بیشتر از یک جستجوی اول سطح یا یک جستجوی اول عمق با عمق d وقتی b=۱۰ است گسترش می‌یابد. هر چه ضریب انشعاب بزرگ‌تر باشد، در نهایت جمع کلی هزینه روی حالت‌های در حال گسترش کم‌تر می‌شود، ولی حتی وقتی که ضریب انشعاب ۲ است، جستجوی ژرفایش تکراری تنها دو برابر یک جستجوی اول سطح زمان می‌گیرد. این بدان معنی است که [[پیچیدگی زمانی]] یک الگوریتم ژرفایش تکراری هنوز همان <math>O(bd)</math> است به صورت کلی جستجوی ژرفایش تکراری نسبت به روش‌های دیگر جستجو وقتی یک فضای بزرگ برای جستجو داریم و عمق نیز نامعلوم است ارجحیت دارد.<ref name="rn32">{{Russell Norvig 2003}}</ref>

== الگوریتم ==
شبه برنامه زیر نشان می‌دهد آی‌دی‌دی‌اف‌اس را با استفاده از دی‌اف‌اس عمق محدود بازگشتی(DLS) اجرا شده‌است.
{{چپ‌چین}}
 '''IDDFS'''(root, goal)
 {
  depth = 0
  repeat
  {
  result = '''DLS'''(root, goal, depth)
  if (result is a solution)
  return result
  depth = depth + 1
  }
 }
{{پایان چپ‌چین}}

جستجوی عمق محدود می‌تواند به صورت بازگشتی انجام شود. توجه کنید تنها لازم است گره هدف برای depth==۰ چک شود، چون وقتی depth>0 باشد، DLS گره‌هایی را که در تکرار قبلی آی‌دی‌دی‌اف‌اس دیده شده‌اند را گسترش می‌دهد.
{{چپ‌چین}}
 '''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
 }
{{پایان چپ‌چین}}

== جستارهای وابسته ==
* [[الگوریتم جستجوی عمق اول]]
* [[الگوریتم ناآگاهانه]]

== منابع ==
{{پانویس|چپ‌چین=بله|۲}}

== پیوند به بیرون ==
[[رده:الگوریتم‌های جستجو]]
[[رده:الگوریتم‌های گراف]]