تعمیق تکراری A*
| کلاس | الگوریتم جست و جو |
|---|---|
| داده ساختار | گراف |
| پیچیدگی حافظه مجانبی در بدترین حالت |
*A ژرفایش تکراری (*A تعمیق تکراری) یک الگوریتم پیمایش گراف است که می تواند کوتاه ترین مسیر بین یک گره شروع و هر عضو مجموعه ای از گره های هدف را در یک گراف وزن دار پیدا کند. این الگوریتم نسخه ای تغییر یافته از جست و جوی عمق-اول ژرفایش تکراری است که از ایده استفاده از یک تابع ابتکاری کمک می گیرد تا مرتبا هزینه باقی مانده تا رسیدن به هدف از طریق جست و جوی *A را برآورد کند. چون این الگوریتم مبتنی بر جست و جوی عمق-اول است مصرف حافظه اش از *A کمتر است, اما بر خلاف جست و جوی عمق-اول ژرفایش تکراری گره های امید بخش را بسط می دهد و در همه جای درخت جست و جو تا یک عمق مشخص جست و جو نمی کند. بر خلاف *IDA* ,A از برنامه ریزی پویا استفاده نمی کند و در نتیجه اغلب یک گره را چندین بار بسط می دهد.
در حالی که IDDFS در هر تکرار از عمق به عنوان مقدار cutoff استفاده می کند, *IDA از تابع ارزیابی خود (به عنوان یک الگوریتم جست و جوی آگاهانه) برای مشخص کردن مقدار cutoff استفاده می کند.
این الگوریتم اولین بار توسط Richard Korf در سال 1985 مطرح شد.
توصیف[ویرایش]
*IDA به صورت زیر کار می کند: در هر تکرار یک جست و جوی عمق-اول انجام می دهد و گره هایی که f(n) شان از یک مقدار آستانه بیشتر است را هرس می کند. مقدار اولیه آستانه f گره شروع است و در هر تکرار الگوریتم افزایش می یابد بدین صورت که که در هر تکرار آستانه مورد استفاده برای تکرار بعدی مینیمم f هایی است که از آستانه فعلی بیشتر اند.
همانند *A, تابع ابتکاری باید ویژگی های خاصی داشته باشد تا بهینگی الگوریتم را تضمین کند. قسمت ویژگی ها را ببینید.
شبه کد[ویرایش]
path current search path (acts like a stack) node current node (last node in current path) g the cost to reach current node f estimated cost of the cheapest path (root..node..goal) h(node) estimated cost of the cheapest path (node..goal) cost(node, succ) step cost function is_goal(node) goal test successors(node) node expanding function, expand nodes ordered by g + h(node) ida_star(root) return either NOT_FOUND or a pair with the best path and its cost procedure ida_star(root) bound := h(root) path := [root] loop t := search(path, 0, bound) if t = FOUND then return (path, bound) if t = ∞ then return NOT_FOUND bound := t end loop end procedure function search(path, g, bound) node := path.last f := g + h(node) if f > bound then return f if is_goal(node) then return FOUND min := ∞ for succ in successors(node) do if succ not in path then path.push(succ) t := search(path, g + cost(node, succ), bound) if t = FOUND then return FOUND if t < min then min := t path.pop() end if end for return min end function
ویژگی ها[ویرایش]
همانند *IDA* ,A تضمین می کند که یک کوتاه ترین مسیر بین گره شروع و هر گره هدف در گراف مسئله را پیدا کند, البته در صورتی که تابع ابتکاری قابل قبول باشد, یعنی برای هر گره n:
که در آن *h هزینه واقعی یک کوتاه ترین مسیر بین n و نزدیک ترین گره هدف است.
هنگامی که حافظه کم است *IDA مفید است. *A یک صف بزرگ از گره های اکتشاف نشده را نگه می دارد که می تواند به سرعت باعث پر شدن حافظه شود. بر خلاف آن, چون *IDA هیچ گره ای به جز آن هایی که روی مسیر فعلی قرار دارند را نگه نمی دارد, حافظه مورد نیاز آن بر حسب طول جوابی که می سازد خطی است.
کاربرد ها[ویرایش]
*IDA کاربرد هایی در حل مسائل برنامه ریزی دارد. حل مکعب روبیک مثالی از یک مسئله برنامه ریزی است که *IDA قابل حل است.
مراجع[ویرایش]
This article "تعمیق تکراری A*" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:تعمیق تکراری A*. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
