الگوریتم جست وجو با عمق محدود depth- limited search
الگوریتم جست وجو با عمق محدود depth- limited search
شکست های الگوریتم جست وجوی عمقی در فضاهای حالت نامتناهی، میتواند با ارائه یک الگوریتم جستوجوی عمقی با عمق محدود مثل Ɩ که از قبل تعیین میشود، کمتر شود. یعنی با گره های واقع در عمق Ɩ طوری رفتار میشود که گویی فاقد پسین ها هستند. این روش، جستوجو با عمق محدود نام دارد.
الگوریتم جست وجو با عمق محدود depth- limited search :
عمق محدود، مسئله ی "مسیر نامحدود" را حل میکند. اگر d>l انتخاب شود (عمیق ترین هدف فراتر از این عمق محدود باشد) این روش جست وجو کامل نخواهد بود. این وضعیت ممکن است وقتی پیش بیاید که d معلوم نباشد. اگر Ɩ> d انتخاب شود، جستوجو با عمق محدود ، بهینه نخواهد بود. پیچیدگی زمانی این روش برابر با O(b^Ɩ) و پیچیدگی فضای آن O(bƖ) است. جستوجوی عمقی حالت خاصی از جستوجو با عمق محدود است که در آن Ɩ بی نهایت انتخاب شده است.
گاهی محدودیت هایی که برای عمق تعیین میشود، ممکن است به دانشی که درباره مسئله داریم، بستگی داشته باشد.
جستوجو با عمق محدود میتواند بصورت یک الگوریتم ساده بازگشتی پیاده سازی شود که شبه کد آنرا در زیر مشاهده میکنید. جستوجو با عمق محدود میتواند با دو نوع شکست خاتمه یابد: مقدار failure استاندارد که نشان میدهد جوابی وجود ندارد. و مقدار cutoff که نشان میدهد جوابی در عمق محدود وجود ندارد.
شبه کد الگوریتم جست وجو با عمق محدود:
function DEPTH-LIMITED-SEARCH (problem, limit) returns a solution, or failure/cutoff
return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE),problem,limit )
function RECURSIVE-DLS (node,problem, limit) returns a solution, or failure/cutoff
if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
else if limit=0 then return cutoff
.gif)
