نمایش مبدأ برای پیش‌نویس:تعمیق تکراری A*

{| class="infobox"
|+ class="infobox-title" id="4" |'''*A ژرفایش تکراری'''
! class="infobox-label" scope="row" |کلاس
| class="infobox-data" |الگوریتم جست و جو
|-
! class="infobox-label" scope="row" |داده ساختار
| class="infobox-data" |گراف
|-
! class="infobox-label" scope="row" |پیچیدگی حافظه مجانبی در بدترین حالت
| class="infobox-data" |<math>O(d)</math>
|}
'''*A ژرفایش تکراری (*A تعمیق تکراری) یک الگوریتم پیمایش گراف است که می تواند کوتاه ترین مسیر بین یک گره شروع و هر عضو مجموعه ای از گره های هدف را در یک گراف وزن دار پیدا کند.  این الگوریتم نسخه ای تغییر یافته از جست و جوی عمق-اول ژرفایش تکراری است که از ایده استفاده از یک تابع ابتکاری کمک می گیرد تا مرتبا هزینه باقی مانده تا رسیدن به هدف از طریق جست و جوی *A را برآورد کند. چون این الگوریتم مبتنی بر جست و جوی عمق-اول است مصرف حافظه اش از *A کمتر است, اما بر خلاف جست و جوی عمق-اول ژرفایش تکراری گره های امید بخش را بسط می دهد و در همه جای درخت جست و جو تا یک عمق مشخص جست و جو نمی کند. بر خلاف *IDA* ,A از برنامه ریزی پویا استفاده نمی کند و در نتیجه اغلب یک گره را چندین بار بسط می دهد.'''

در حالی که IDDFS در هر تکرار از عمق به عنوان مقدار cutoff استفاده می کند, *IDA از تابع ارزیابی خود (به عنوان یک الگوریتم جست و جوی آگاهانه) برای مشخص کردن مقدار cutoff استفاده می کند.

این الگوریتم اولین بار توسط Richard Korf در سال 1985 مطرح شد.

== توصیف ==
<nowiki>*</nowiki>IDA به صورت زیر کار می کند: در هر تکرار یک جست و جوی عمق-اول انجام می دهد و گره هایی که f(n) شان از یک مقدار آستانه بیشتر است را هرس می کند. مقدار اولیه آستانه f گره شروع است و در هر تکرار الگوریتم افزایش می یابد بدین صورت که که در هر تکرار آستانه مورد استفاده برای تکرار بعدی مینیمم f هایی است که از آستانه فعلی بیشتر اند.

همانند *A, تابع ابتکاری باید ویژگی های خاصی داشته باشد تا بهینگی الگوریتم را تضمین کند. قسمت ویژگی ها را ببینید.

== شبه کد ==
 <span style="color:Green;">path</span>              ''current search path (acts like a stack)''
 <span style="color:Green;">node</span>              ''current node'' ''(last node in current path)''
 <span style="color:Green;">g</span>                 ''the cost to reach current node''
 <span style="color:Green;">f</span>                 ''estimated cost of the cheapest path (root..node..goal)''
 <span style="color:OrangeRed;">'''h'''</span>(<span style="color:Green;">node</span>)           ''estimated cost of the cheapest path (node..goal)''
 <span style="color:OrangeRed;">'''cost'''</span>(<span style="color:Green;">node</span>, <span style="color:Green;">succ</span>)  ''step cost function''
 <span style="color:OrangeRed;">'''is_goal'''</span>(<span style="color:Green;">node</span>)     ''goal test''
 <span style="color:OrangeRed;">'''successors'''</span>(<span style="color:Green;">node</span>)  ''node expanding function, expand nodes ordered by g + h(node)''
 <span style="color:OrangeRed;">'''ida_star'''</span>(<span style="color:Green;">root</span>)    ''return either NOT_FOUND or a pair with the best path and its cost''
  
 '''procedure''' <span style="color:OrangeRed;">'''ida_star'''</span>(<span style="color:Green;">root</span>)
     <span style="color:Green;">bound</span> := <span style="color:OrangeRed;">'''h'''</span>(<span style="color:Green;">root</span>)
     <span style="color:Green;">path</span> := [<span style="color:Green;">root</span>]
     '''loop'''
         <span style="color:Green;">t</span> := <span style="color:OrangeRed;">'''search'''</span>(<span style="color:Green;">path</span>, 0, <span style="color:Green;">bound</span>)
         '''if''' <span style="color:Green;">t</span> = FOUND '''then return''' <span style="color:Green;">(path, bound)</span>
         '''if''' <span style="color:Green;">t</span> = ∞ '''then return''' NOT_FOUND
         <span style="color:Green;">bound</span> := <span style="color:Green;">t</span>
     '''end loop'''
 '''end procedure'''
 
 '''function''' <span style="color:OrangeRed;">'''search'''</span>(<span style="color:Green;">path</span>, <span style="color:Green;">g</span>, <span style="color:Green;">bound</span>)
     <span style="color:Green;">node</span> := <span style="color:Green;">path</span>.last
     <span style="color:Green;">f</span> := <span style="color:Green;">g</span> + <span style="color:OrangeRed;">'''h'''</span>(<span style="color:Green;">node</span>)
     '''if''' <span style="color:Green;">f</span> > <span style="color:Green;">bound</span> '''then return''' <span style="color:Green;">f</span>
     '''if''' <span style="color:OrangeRed;">'''is_goal'''</span>(<span style="color:Green;">node</span>) '''then return''' FOUND
     <span style="color:Green;">min</span> := ∞
     '''for''' <span style="color:Green;">succ</span> '''in''' <span style="color:OrangeRed;">'''successors'''</span>(<span style="color:Green;">node</span>) '''do'''
         '''if''' <span style="color:Green;">succ</span> '''not''' '''in''' <span style="color:Green;">path</span> '''then'''
             <span style="color:Green;">path</span>.push(<span style="color:Green;">succ</span>)
             <span style="color:Green;">t</span> := <span style="color:OrangeRed;">'''search'''</span>(<span style="color:Green;">path</span>, <span style="color:Green;">g</span> + <span style="color:OrangeRed;">'''cost'''</span>(<span style="color:Green;">node</span>, <span style="color:Green;">succ</span>), <span style="color:Green;">bound</span>)
             '''if''' <span style="color:Green;">t</span> = FOUND '''then return''' FOUND
             '''if''' <span style="color:Green;">t</span> < <span style="color:Green;">min</span> '''then''' <span style="color:Green;">min</span> := <span style="color:Green;">t</span>
             <span style="color:Green;">path</span>.pop()
         '''end''' '''if'''
     '''end for'''
     '''return''' <span style="color:Green;">min</span>
 '''end function'''

== ویژگی ها ==
همانند *IDA* ,A تضمین می کند که یک کوتاه ترین مسیر بین گره شروع و هر گره هدف در گراف مسئله را پیدا کند, البته در صورتی که تابع ابتکاری قابل قبول باشد, یعنی برای هر گره n:

: <math>h(n) \le h^*(n)</math>

که در آن *h هزینه واقعی یک کوتاه ترین مسیر بین n و نزدیک ترین گره هدف است.

هنگامی که حافظه کم است *IDA مفید است. *A یک صف بزرگ از گره های اکتشاف نشده را نگه می دارد که می تواند به سرعت باعث پر شدن حافظه شود. بر خلاف آن, چون *IDA هیچ گره ای به جز آن هایی که روی مسیر فعلی قرار دارند را نگه نمی دارد, حافظه مورد نیاز آن بر حسب طول جوابی که می سازد خطی است.

== کاربرد ها ==
<nowiki>*</nowiki>IDA کاربرد هایی در حل مسائل برنامه ریزی دارد. حل مکعب روبیک مثالی از یک مسئله برنامه ریزی است که *IDA قابل حل است.

== مراجع ==



[[رده:بازی هوش مصنوعی]]
[[رده:الگوریتم‌های جستجو]]
[[رده:الگوریتم‌های مسیریابی]]
[[رده:الگوریتم‌های گراف]]