موضوع پروژه:رفع مشکل فضای الگوریتم A*
تاریخ ارائه پروژه: 24/3/93
فهرست:
جستجویA* با حافظه محدود
چند راه حل برای مساله حافظه در A*
جستجوی عمیق کننده تکراری A* (IDA*)
روش جستجوی اول بهترین بازگشتی (RBFS)
خواص جستجوی RBFS
جستجوی A* با حافظه محدودشده (SMA*)
جستجویA* با حافظه محدود
زمان محاسبه، نقطه ضعف اصلیA* نیست.از آنجا که این الگوریتم، تمامی گره های تولید شده را در حافظه نگهداری می کند معمولاً بسیار
بیشترازآنکه وقت کم بیاورد، حافظه کم می آورد.در مورد بسیاری از مسائل بزرگ، عملی نیست.
چند راه حل برای مساله حافظه در A*
1) جستجوی عمیق کننده تکراری A* (IDA*) Iterative Depth A*
2) جستجوی اول-بهترین بازگشتی(RBFS) Recursive Best First Search
3) جستجوی A* با حافظه محدودشده (SMA*) Simplified Memory A*
جستجوی عمیق کننده تکراری A* (IDA*)
ساده ترین راه برای رفع مشکل پیچیدگی فضایی جستجوی A* استفاده از ایده موجود درجستجوی عمقی تکرار شونده (IDS) است.
تفاوت روش IDA* باروش IDS در این است که این الگوریتم بجای محدودیت روی عمق )برش عمقی(،روی هزینه f(n) محدودیت
می گذارد. مقداراولیه Flimit مقدار F ریشه است. در هر تکرار گره هایی که هزینه آنها کمتر از Flimit آن نود باشد( ( f(n)≤Flimit
گسترش می یابند. اگر در این تکرار هدف پیدا شد کار تمام می شود در غیر این صورت، الگوریتم دوباره با این مقدار Flimit جدید از
اول تکرار می شود. این تکرارها تا جایی ادامه می یابد که مقدار Flimit به گونه ای باشد که گره هدف برای گسترش انتخاب شود.
روش IDA*کامل و بهینه است. اما مشکل این روش دوباره کاری آن است.پیچیدگی زمانی این روش به تعداد مقادیر مختلفی که تابع
اکتشافی می پذیرد، بستگی دارد. ازآنجاییکه IDA* عمقی است و در هر مرحله فقط گره هایی که f(n) آنها کمتر از f-limit است
درحافظه نگهداری می شود به همین دلیل از نظر پیچیدگی حافظه مثل جستجوی عمقی O(bd)است. در شکل زیر چگونگی عملکرد
استراتژی – IDA* با اعمال هزینه های flimit مختلف درچندین contour نشان داده شده است:
شکل1.1: اعمال استراتژی IDA* با اعمال هزینه های flimit مختلف در چندین contour
function IDA*(problem) returns a solution sequence
Inputs: problem, a problem
Local variables:f-limit, the current f-COST limit
root, a node
root MAKE-NODE(INITIAL-STATE[problem])
f-limit f-COST(root)
loop do
solution, f-limit DFS_CONTOUR(root, f-limit)
if solution is non-null then return solution
if f-limit = ∞ then return failure; end
function DFS_CONTOUR(node, f-limit) returns a solution sequence and a new f-COST limit
inputs: node, a node
f-limit, the current f-COST limit
Local variables: next-f,the f-COST limit for the next contour, initially ∞
If f-COSTt[node]> f-limit then return null, f-COSTt[node]
If GOAL-TEST[problem](STATE[node]) then return node, f-limit
for each node s in SUCCESSORS(s, f-limit) do
solution,new-f DFS_CONTOUR(s, f-limit)
if solution is non-null then return solution,f-limit
next-f MIN(next-f,new-f); end
return null, next-f
مثال: معمای 8-puzzle را با روش IDA* جستجو کنید با فرض اینکه وضعیت آغازین و هدف به صورت زیرباشند :
پاسخ: براساس آنچه در مورد این روش توضیح داده شد، در هر مرحله، هزینه ای را به عنوان flimit
درنظر گرفته و در هر تکرار، وضعیت هایی که هزینه آن ها از flimit کمتر باشد، بسط داده می
شوند. در مرحله بعد وضعیتی با کمترین هزینه ای که هنوز بسط داده نشده به عنوان flimit مرحله
دوم انتخاب می شود و این تکرارها آنقدر ادامه می یابد تا flimit ای انتخاب شود که بااستفاده از
آن هدف انتخاب شود. در اولین تکرار flimit همان هزینه وضعیت اولیه است.
روش جستجوی اول بهترین بازگشتی (RBFS)
این روش یک الگوریتم بازگشتی ساده است که ساختار آن شبیه جستجوی عمقی بازگشتی است اما بجای اینکه دائماً مسیر فعلی
را به سمت پایین ادامه دهد مقدار F بهترین مسیر جانشین ازطریق اجداد گره فعلی را در حافظه نگه می دارد.اگر F گره فعلی
از این حد )مقدار F حافظه(تجاوز کند، الگوریتم به عقب باز می گردد تا مسیر جانشین را انتخاب کند. در برگشت به عقب،مقدار
F هر گره موجود در مسیر را با کمترین مقدار F فرزندانش جایگزین می کند. به این ترتیب مقدار F مربوطه به بهترین برگ را
در زیر درخت فراموش شده را به یاد می آورد و می تواند تصمیم بگیرد که این زیر درخت در ادامه انتخاب شود یا خیر.
روش RBFS نسبت به روش IDA* کاملتراست اما این روش گره های اضافی تولید می کند. دو روش RBFS و IDA* اگر
حافظه زیادی محیا باشد این الگوریتم ها راهی برای استفاده از آن ندارد. بهتر است الگوریتم از کل حافظه مورد نیازاستفاده کند
که روش SMA* از کل حافظه داده شده استفاده می کند. روش IDA* و روش RBFS از حافظه اندکی استفاده می کند .
اما ممکن است روی مسئله خاصی از حافظه داده شده به آنها حداکثر استفاده را نکنند. یعنی مقداری از حافظه را بلا استفاده بگذارند .
در این صورت برای حل این مشکل از روش SMA* استفاده می کنیم.
در مثال زیر، نقشه رومانی و فاصله شهرها تا بخارست مشخص شده است. هزینه تخمینی هر مرحله نیز برحسب کیلومتر در جدول
زیر نشان داده شده است:
در ادامه مراحل رسیدن از شهر آراد به بخارست بااستفاده از جستجوی RBFS نشان داده شده است:
مثال: کارایی روش های A* و RBFS را برای مجموعه ای از مسائل TSP و پازل های 8 تایی که به طور تصادفی تولید شده اند،
مقایسه کنید. در مورد نتایج خود توضیح دهید. اگر یک مقدار تصادفی کوچک به مقدار اکتشافی افزوده شود چه تاثیری برروی کارایی
RBFSخواهد داشت؟
پاسخ: در مساله پازل 8 تایی، روش RBFS تعداد گره های بیشتری را بسط می دهد)به خاطر عدم تشخیص حالت های تکراری(
ولی به ازای هر گره هزینه کمتری دربردارد. زیرا در این روش نیازی به نگهداری یک صف نداریم. البته در روش RBFS تعداد
گره هایی که مجدداً بسط می یابند،خیلی زیاد نیستند زیرا مسیر بهینه به ندرت تغییر می کند ولی زمانیکه مقدار اکتشافی کمی مناسب
نباشد، این مزیت از بین رفته و کارایی RBFS به شدت کاهش می یابد. در مساله TSP ،فضای حالت به شکل درخت است پس
حالت های تکراری نداریم یا به بیانی دیگر مقادیر اکتشافی حقیقی بوده و به مقادیر حدسی نیازی نیست. بنابراین RBFS محکوم به
بسط مجدد گره هایی است که قبلاً بسط یافته اند.
خواص جستجوی RBFS
RBFSکمی کارآ تر ازIDA* می باشد
– هنوز گسترش اضافی گره ها وجود دارد( تغییر عقیده)
پیچیدگی زمانی؟
– بیان پیچیدگی زمانی آن نسبتاً مشکل است: هم به دقت تابع هیوریستیک بستگی دارد و هم به این که در حین گسترش گره ها،
بهترین مسیر هر چند وقت یکبار تغییر می کند.
– مانند IDA* در معرض افزایش نمایی پیچیدگی زمانی قرار دارد
پیچیدگی حافظه؟
– O(bd)
بهینه؟
– همانند A* ، الگوریتم RBFS نیز یک الگوریتم بهینه است اگر تابع هیوریستیک h قابل قبول باشد.
• RBFS ممکن و IDA* هر دو است در معرض افزایش نمایی بالقوه در پیچیدگی همراه با جستجو در گرافها قرار بگیرند.
• آنها نمی توانند حالتهای تکراری، به جز آنهایی را که بر روی مسیر فعلی قرار دارند بررسی کنند. در نتیجه، ممکن است یک
حالت را چندین بار اکتشاف کنند.
• از میزان بسیار کم حافظه رنج می برند.
• IDA* فقط یک عدد را نگهداری می کند (محدودیت مقدار فعلی f)
• RBFS اطلاعات بیشتری را در حافظه نگهداری می کند، ولی فقط از O(bd) حافظه استفاده می کند.
• حتی اگر حافظه بیشتری در دسترس باشد نمی توانند از آن استفاده کنند.
جستجوی A* با حافظه محدودشده (SMA*)
پیچیدگی فضایی روش جستجوی IDA* خطی و حداکثر برابر O(bd) می باشد اما این روش مجبوربه تکرار محاسبات می باشد،
تغییر عقیده های مختلف RBFS نیز به منزله تولید گره های اضافی است بنابراین این دو روش در معرض پیچیدگی زمانی نمایی
قرار دارند، از طرف دیگر دو روش جستجوی IDA* و RBFS درصورتی که حافظه زیادی در دسترس داشته باشد، نمی توانند
از کل حافظه به طور کامل استفاده کنند بنابراین قسمتی از حافظه بلااستفاده باقی خواهند ماند،درحالیکه تلاش براین است تا روش های
جستجو تا حد امکان از کل حافظه استفاده نمایند،SMA*این مشکل را با در اختیار قرار دادن یک حافظه محدود از ابتدا، حل می کند
این روش مانند A* بهترین برگ را گسترش می دهد تا حافظه پر شود با پر شدن حافظه بدون از بین بردن گره های قبلی، نمی توان
گره جدیدی اضافه نمود. روش SMA* نیز همیشه بدترین گره قبلی )گره ای که بالاترین هزینه را دارد( را حذف می کند. گره هایی
که حذف می شوند، گره های فراموش شده نامیده می شوند، سپس SMA* مانند RBFS ارزش گره های فراموش شده را به گره پدر
انتساب می دهد. به این ترتیب اجداد زیر درخت فراموش شده از کیفیت مسیر مناسب تر در زیردرخت خود مطلع می شوند. SMA*
در صورتی زیر درخت فراموش شده را بیاد می آورد که تمام مسیرهای دیگر، هزینه ای بیشتر از مسیر فراموش شده داشته باشند.
SMA* کامل است درصورتیکه حافظه کافی برای ذخیره کم عمق ترین مسیر وجود داشته باشد، همچنین این روش بهینه است در
صورتیکه حافظه کافی برای ذخیره بهترین مسیر موجود باشد.این روش از تکرار محاسبات تاجاییکه حافظه اجازه دهد، جلوگیری می کند.
function SMA*(problem) returns a solution sequence Inputs: problem, a problem
Local variables:Queue, a queue of nodes ordered be f-cost Queue MAKE_QUEUE({MAKE_NODE(INITIAL_STATE[problem])}) loop do if Queue is empty then return failure n deepest least f-cost node in Queue if GOAL_TEST(n) then return success s NEXT_SUCCESSOR(n) If s is not a goal and is at maximum depth then f(s) ∞ else f(s) MAX(f(n),g(s)+h(s)) if all of n`s successors have been generated then update n`s f-cost and those of its ancestors if necessary if SUCCESSOR(n) all in memory then remove n from Queue if memory is full then delete shallowest, highest-f-cost node in Queue remove it from its parent`s successor list insert its parent on Queue if necessary insert s on Queue end
نکات مهم در مورد این روش:
نکته 1: بهترین نسل فراموش شده هر گره داخل پرانتز قرار می گیرد.
نکته 2: اگر گره غیر هدفی در عمق حداکثر باز شود و هدف نباشد )بهینه نباشد(، f(n) آن به سمت بینهایت می رود.
نکته 3: هربار مقدار f(n) کمتر، توسط گره پدر به ارث برده می شود.
نکته 4: گره هدفی که کمترین f(n) را دارد بعنوان هدف بهینه انتخاب می شود
مثال: درخت زیر را با روش SMA* و با 3 خانه حافظه پیمایش کرده و مسیر بهینه برای رسیدن به هدف را مشخص کنید؟