پاورپوینت کامل الگوریتم های جستجوی آگاهانه ۸۷ اسلاید در PowerPoint

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل الگوریتم های جستجوی آگاهانه ۸۷ اسلاید در PowerPoint دارای ۸۷ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

شما با استفاده ازاین پاورپوینت میتوانید یک ارائه بسیارعالی و با شکوهی داشته باشید و همه حاضرین با اشتیاق به مطالب شما گوش خواهند داد.

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل الگوریتم های جستجوی آگاهانه ۸۷ اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل الگوریتم های جستجوی آگاهانه ۸۷ اسلاید در PowerPoint

اسلاید ۴: جستجوی اول – بهتریننمونه ای از الگوریتم عمومی tree-search یا graph-search است که در ان یک گره بر اساس یک تابع ارزیابی f(n) برای گسترش انتخاب می شود.تابع ارزیابی evaluation function تخمین ”میزان مطلوب بودن“ گره هربار مطلوب ترین گره گسترش نیافته را بسط می دهد.پیاده سازی:گره ها در fringe به ترتیب نزولی میزان مطلوبیت مرتب می شوند. یک صف اولویتحالت های خاص جستجوی حریصانه Greedy searchجستجوی A*دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۴

اسلاید ۵: جستجوی اول -بهترین حریصانهتابع هیوریستیک h(n) هزینه تخمینی مسیر از گره n تا نزدیکترین گره هدفبرای مثال، در نقشه رومانی می توان هزینه مسیر از هر شهری به بخارست را از طریق مسافت یک خط مستقیم از آن شهر به بخارست تخمین زد.hSLD(n) فاصله مستقیم از n تا بخارستجستجوی اول -بهترین حریصانهجستجوی حریصانه گره ای را گسترش می دهد که به نظر می رسد نزدیکترین گره به هدف ( بخارست) باشد.تابع ارزیابی f(n)= h(n)دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۵

اسلاید ۶: نقشه رومانی به همراه هزینه مراحل برحسب kmدانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۶

اسلاید ۷: جستجوی اول -بهترین حریصانه

اسلاید ۸: جستجوی اول -بهترین حریصانه

اسلاید ۹: جستجوی اول -بهترین حریصانه

اسلاید ۱۰: جستجوی اول -بهترین حریصانه

اسلاید ۱۱: خواص جستجوی اول -بهترین حریصانهدانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۱۱کامل؟–خیر (ممکن است در حلقه بینهایت گیر کند)پیچیدگی زمانی؟O(bm) – اما با یک هیوریستیک خوب می تواند به شدت بهبود یابدپیچیدگی حافظه؟– O(bm) تمام گره ها را در حافظه نگه می دارد.بهینه؟– خیر (مثلا در مثال قبل مسیر بهینه ای وجود دارد که از دید جستجوی حریصانه مخفی می ماند).

اسلاید ۱۲: حلقه بینهایت در جستجوی حریصانهدانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۱۲پایانشروعIasi Neamt Iasi Neamt

اسلاید ۱۳: جستجوی A*ایده: از گسترش مسیرهایی که تاکنون مشخص شده پرهزینه می باشند، اجتناب کن. تابع ارزیابیf(n) = g(n) + h(n)دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۱۳هزینه رسیدن به گره n هزینه تخمینی ارزانترین مسیر از گره n به هدفهزینه ارزانترین مسیر گذرنده از گره n به هدف

اسلاید ۱۴: مثال جستجوی A*

اسلاید ۱۵: مثال جستجوی A*

اسلاید ۱۶: مثال جستجوی A*

اسلاید ۱۷: مثال جستجوی A*

اسلاید ۱۸: مثال جستجوی A*

اسلاید ۱۹: مثال جستجوی A*

اسلاید ۲۰: هیوریستیک قابل قبولیک هیوریستیک h(n) قابل قبول است اگر برای هر گره n داشته باشیم : h(n) h*(n) که h*(n) هزینه واقعی برای رسیدن به هدف از گره n می باشد.یک هیوریستیک قابل قبول هرگز هزینه رسیدن به هدف را بیش از حد تخمین نمی زند، یعنی خوش بینانه است.مثال: هیوریستیکhSLD(n) هیچگاه فاصله را بیش از حد واقعی تخمین نمی زند.قضیه: اگر h(n) قابل قبول باشد، A* با استفاده از TREE-SEARCH بهینه استدانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۰

اسلاید ۲۱: اثبات بهینگی A*فرض کنید یک جواب زیر بهینه مانند G2 ایجاد شده و در fringe قرار دارد. همچنین فرض کنید n یک گره گسترش نیافته روی کوتاهترین مسیر به هدف بهینه G باشد.دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۱f(G2) = g(G2)since h(G2) = 0 g(G2) > g(G) since G2 is suboptimal f(G) = g(G)since h(G) = 0 f(G2) > f(G)from above

اسلاید ۲۲: اثبات بهینگی A*فرض کنید یک جواب زیر بهینه مانند G2 ایجاد شده و در fringe قرار دارد. همچنین فرض کنید n یک گره گسترش نیافته روی کوتاهترین مسیر به هدف بهینه G باشد.دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۲f(G2)> f(G) from above h(n) h*(n)since h is admissibleg(n) + h(n) g(n) + h*(n) f(n) f(G)چون f(G2) > f(n) است A* هیچگاه G2 را برای گسترش انتخاب نمی کند

اسلاید ۲۳: بهینگی A*اگر به جایTREE–SEARCH از GRAPH–SEARCH استفاده کنیم، آنگاه قضیه قبل دیگر صدق نمی کند.ممکن است راه حلهای نیمه بهینه برگردانده شوند، زیرا GRAPH–SEARCH می تواند میسر بهینه به یک حالت تکراری را کنار بگذارد، اگر اولین گره تولیدی نباشد.دو راهکار برای حل این مشکل:اولین راه حل، این است که GRAPH–SEARCH را به نحوی توسعه بدهیم که از بین مسیری که به یک گره می رسد آن مسیری که پرهزینه تر است را کنار بگذارد. این روش فضای زیادی اشغال می کند، اما بهینگی را تضمین می کند.راه حل دوم، اطمینان از این موضوع است که مسیر بهینه به هر حالت تکراری، همیشه اولین مسیری است که دنبال می شود. شرط سازگاری (یا یکنواختی)دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۳

اسلاید ۲۴: هیوریستیک های سازگاریک هیوریستیک سازگار consistent است اگر h(n) c(n,a,n) + h(n)شکلی از قانون کلی نامساوی مثلث است که تصریح می کند هیچ ضلعی از یک مثلث نمی تواند بلندتر از مجموع دو ضلع دیگر باشد.هر هیوریستیک سازگار، قابل قبول نیز هست.قضیه: اگر h(n) سازگار باشد، A* با استفاده از GRAPH–SEARCH بهینه استدانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۴

اسلاید ۲۵: هیوریستیک های سازگاراگر h(n) سازگار باشد آنگاه f(n) در طول هر مسیری، غیرنزولی است. f(n) = g(n) + h(n) = g(n) + c(n,a,n) + h(n) g(n) + h(n) = f(n)می توان نتیجه گرفت که رشته ای از گره ها که توسطA* با استفاده از GRAPH–SEARCH گسترش یافته اند به ترتیب غیرنزولی f(n) می باشد. در نتیجه، اولین گره هدفی که برای گسترش انتخاب می شود باید یک راه حل بهینه باشد، زیرا تمامی گره های بعدی حداقل به همان اندازه هزینه خواهند داشت.دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۵

اسلاید ۲۶: بهینگی A*A* به تدریج f-contour ها را اضافه می کند. دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۶

اسلاید ۲۷: خواص جستجوی A*اولین راه حل پیداشده، باید یک راه حل بهینه باشد زیرا گره های هدف در تمامی contourهای بعدی دارای هزینه f بیشتری خواهند بود و در نتیجه هزینه G بالاتری نیز دارند (زیرا تمامی گره های هدف دارای h(n)=0 هستند).جستجوی A* کامل است. همان طور که نوارهای با f در حال افزایش را اضافه می کنیم، باید بالاخره به نواری برسیم که در آنجا f مساوی هزینه مسیر تا یک حالت هدف است.دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۷

اسلاید ۲۸: خواص جستجوی A*دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۸کامل؟–بله، مگر اینکه تعدادی نامحدود گره با f f(G) وجود داشته باشد. A* –در گراف های متناهی محلی ( با فاکتور انشعاب محدود) کامل می باشدپیچیدگی زمانی؟– نمایی پیچیدگی حافظه؟– نمایی تمام گره ها را در حافظه نگه می دارد.بهینه؟– بله

اسلاید ۲۹: خواص جستجوی A*بهینه؟– بله نمی تواند fi+1 را گسترش دهد مگر آنکه fi تمام شده باشد. A* – تمام گره ها با f(n) <f* را گسترش می دهد. A* – برخی گره ها با f(n) =f* را گسترش می دهد. A* – هرگز گره ای با f(n) >f* را گسترش نمی دهد. A* دارای کارآیی بهینه optimally efficient می باشد یعنی هیچ الگوریتم بهینه دیگری تضمین نمی کند که تعداد گره هایی که گسترش می دهد از A* کمتر باشد.علت این امر آن است که هر الگوریتمی که تمامی گره ها را با f(n) <f* را گسترش ندهد خطر از دست دادن راه حل بهینه را دارد.دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۲۹

اسلاید ۳۰: جستجوی A* با حافظه محدودزمان محاسبه، نقطه ضعف اصلیA* نیست. از آنجا که این الگوریتم، تمامی گره های تولید شده را در حافظه نگهداری می کند معمولاً بسیار بیشتر از آنکه وقت کم بیاورد، حافظه کم می آورد.در مورد بسیاری از مسائل بزرگ، عملی نیست.چند راه حل برای مسأله حافظه در A*جستجوی عمیق کننده تکراری A* (IDA*)جستجوی اول-بهترین بازگشتی(RBFS) جستجوی (ساده شده) A* با حافظه محدود ((S)MBA*)دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۳۰

اسلاید ۳۱: IDA*ایده استفاده از راهکار عمیق کننده تکراری در زمینه جستجوی آگاهانهتفاوت اصلی بین IDS و IDA*در IDA* به جای محدوده عمقی از محدوده f (یعنی g+h) استفاده می شود.در هر تکرار، مقدار برش، کوچکترین هزینه f میان تمام گره هایی است که از برش تکرار قبلی بیشتر باشند.دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۳۱

اسلاید ۳۲: جستجوی اول -بهترین بازگشتی (RBFS)یک الگوریتم بازگشتی با فضای خطی که سعی می کند از جستجوی اول- بهترین استاندارد تقلید کند.ساختارRBFS مشابه جستجوی اول عمق بازگشتی است، اما به جای ادامه دادن مسیر فعلی به طور نامشخص، خود را از مقدار بهترین f مسیر جایگزین قابل دسترس از تمام اجداد گره فعلی مطلع نگه می دارد.اگر گره فعلی از این محدوده فراتر رود، تابع بازگشتی آن را به عقب برمی گرداند تا روی یک مسیر جایگزین دیگر قرار گیرد.در بازگشت به عقب مقدار f مربوط به هر گره موجود در مسیر را با بهترین مقدار f فرزندانش جایگزین می کند.بنابراین گسترش مجدد نتیجه فعلی هنوز ممکن می باشد.دانشگاه صنعتی اصفهان دانشکده برق و کامپیوتر۳۲

اسلاید ۳۳: جستجوی اول