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

*A ژرفایش تکراری

کلاس	الگوریتم جست و جو
داده ساختار	گراف
پیچیدگی حافظه مجانبی در بدترین حالت	$O(d)$

*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)\leq h^{*}(n)$

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

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

کاربرد ها

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