پاورپوینت کامل هوش مصنوعی (فصل چهارم: جستجوی آگاهانه) ۹۱ اسلاید در PowerPoint

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

 پاورپوینت کامل هوش مصنوعی (فصل چهارم: جستجوی آگاهانه) ۹۱ اسلاید در PowerPoint دارای ۹۱ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

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

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

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

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

پاورپوینت کامل هوش مصنوعی (فصل چهارم: جستجوی آگاهانه) ۹۱ اسلاید در PowerPoint

اسلاید ۴: فصل چهارم: جستجوی اول بهترین۱- جستجوی اول بهترینBest -First Searchاین استراتژی به این صورت بیان می‌شود که در یک درخت، گره ها توسط تابع ارزیاب ارزیابی شده ، سپس گره‌ها مرتب می‌شوند و در نتیجه گره‌ای که بهترین ارزیابی را داشته باشد، ابتدا بسط داده می‌شودهدف: یافتن راه‌حل‌های کم‌هزینه است، این الگوریتم‌ها عموماً از تعدادی معیار تخمین برای هزینه راه‌حل‌ها استفاده می‌‌کنند و سعی بر حداقل کردن آنها دارند.۴

اسلاید ۵: نکته :گره که انتخاب می شود براساس تابع ارزیاب بهترین است اگر تابع ارزیاب درست باشد پس گره حقیقتاً بهترین است ولی اگر تابع ارزیاب درست نباشد جستجو را گمراه می کندفصل چهارم: جستجوی اول بهترین – ادامه۵

اسلاید ۶: فصل چهارم: جستجوی اول بهترین – مثالمثال: در درخت جستجوی زیر به شرطی که گره O هدف باشد براساس الگوریتم جستجوی Best First ترتیب رویت گره ها کدام است؟JMTF(B) =346535423203213343ABCDEFGHIKLNPOQRS46

اسلاید ۷: فصل چهارم: جستجوی حریصانه۱-۱- جستجوی حریصانهGreedy Searchحداقل هزینه ی تخمین زده شده برای رسیدن به هدف را انتخاب می کنددر این روش نزدیکترین گره به هدف برای بسط انتخاب می شود که این هزینه توسط تابع ارزیابی تخمین زده می شود به نام :هدف h این است که فضای جستجو را کوچک کند در حالی که تضمین می کند پاسخ در این فضای کوچک قرار دارد . Heuristics Functionhh : حسی ، ذهنی ۷

اسلاید ۸: – مسئله معمای ۸ : h1: تعداد خانه هایی که در مکان های نا درست قرار دارند h2: مجموع فاصله خانه های نادرست تا مکان های صحیح شان.- برای طی مسیر بین دو شهر ارزان ترین مسیر می تواند کوتاهترین مسیر باشد.h(n): ارزان ترین مسیر از گره n به هدف .در جستجوی حریصانه ارزیابی هر گره برابر است با :f(n) = h(n)مثال : محاسبه hفصل چهارم: جستجوی حریصانه – ادامه۸

اسلاید ۹: h هر تابعی می تواند باشد فقط لازم است h(n)=0 اگر n گره هدف باشد جستجوی حریصانه از لحاظ دنبال کردن یک مسیر ویژه در تمام طول راه به طرف هدف مثل جستجوی عمقی است .نکته :h(Goal) = 0 در بدترین حالت h ممکن است هدف در عمق d باشد اما گره ها در عمق بیشتر زودتر گسترش یابند و هرگز برای امتحان مسیر ها ممکن بر نگرددمعیارهای ارزیابی استراتژی جستجوی حریصانه: ۱) کامل بودن: فصل چهارم: جستجوی حریصانه – ادامه۹

اسلاید ۱۰: یعنی h نزدیک به هدف از hهای Nodeهای دیگر بیشتر شود و هرگز انتخاب نشودپس کامل نیست، ۲) بهینه بودن: بهینه نیست زیرا توجهی به g(n) ندارد.۳) پیچیدگی زمانی: ۴) پیچیدگی مکانی: O(bm)O(bm)در بدترین حالت در بدترین حالت میزان کاهش پیچیدگی، به مسئله و کیفیت تابع h بستگی دارد.فصل چهارم: جستجوی حریصانه – ادامه۱۰

اسلاید ۱۱: ABCDEFGHIKMLNOg=3PQJWVXYZRSTU112133232323111232111323h(B)=13510132312211212جستجوی حریصانهمثالفصل چهارم: جستجوی حریصانه – مثال۱۱

اسلاید ۱۲: ABCDEFGHIKMLNOg=3PQJWVXYZRSTU112133232323111232111323h(B)=13510132312211212جستجوی حریصانهمثالفصل چهارم: جستجوی حریصانه – مثال۱۲

اسلاید ۱۳: ABCDEFGHIKMLNOg=3PQJWVXYZRSTU112133232323111232111323h(B)=13510132312211212جستجوی حریصانهمثالهزینه مسیر پاسخ = ۷ ولی هزینه پاسخ بهینه = ۴فصل چهارم: جستجوی حریصانه – مثال۱۳

اسلاید ۱۴: فصل چهارم: جستجوی A*حداقل‌سازی مجموع هزینه مسیر جستجوی حریصانه: h(n) را به سمت هدف حداقل می کندf(n) = h(n) جستجو با هزینه یکنواخت: g(n) یا هزینه مسیر را حداقل می کندf(n) = g(n)نه بهینه بود و نه کاملهم بهینه است و هم کاملالگوریتم A*f(n) = g(n) + h(n)الگوریتم گره ای را بسط می دهد که کمترین f را داراست ۱-۲- جستجوی A*14

اسلاید ۱۵: هنگام تولید گراف فاصله طی شده از مبداء محور رشد گراف است ولی به تدریج فاصله مانده تا هدف تاثیر بیشتری در تولید گراف خواهد داشت.: از سمت یک به سمت صفر کاهش پیدا می کند در شروع تولید فضای پاسخ مساوی یک است و سپس به تدریج کاهش پیدا می کندf(n) = g(n) + (1-) h(n) : 1 0تابع ارزیاب دیگر:فصل چهارم: جستجوی A* – ادامه۱۵

اسلاید ۱۶: S4B1G10D1G20E6A2C3215411558712921جستجوی A*مثالفصل چهارم: جستجوی A* – مثال اولفضای حالت۱۶

اسلاید ۱۷: درخت جستجوی با استفاده از جستجوی A*S4B1E6A2C3D1G10G202581412f=2+2f=5+310+63+17+04+1f* = f =6+0=6فصل چهارم: جستجوی A* – مثال اولG105C3S5124+35+56+j>

اسلاید ۱۸: Goal Stateh = تعداد چهارخانه‌هایی که در مکان‌های نادرست هستند. مثال:معمای ۸۲۸۳۱۶۴۷۵Start State1238 4765فصل چهارم: جستجوی A* – مثال دوم۱۸

اسلاید ۱۹: ۲۸۳۱۶۴۷۵۰+۴۲۸۳۱۶۴ ۷۵۲۸۳۱ ۴۷۶۵۲۸۳۱۶۴۷۵ ۱+۵۱+۳۱+۵۲۸۳ ۱۴۷۶۵۲ ۳۱۸۴۷۶۵۲۸۳۱۴۷۶۵۲+۳goal !2+4 832147653+32+3283714 653+4 231847653+2123 847654+11238 47655+0123784 655+2231847653+4جستجوی A*مثالh = تعداد چهارخانه‌هایی که در مکان‌های نادرست هستند. معمای ۸فصل چهارم: جستجوی A* – مثال دوم۱۹

اسلاید ۲۰: ۲۰فصل چهارم: جستجوی A* – ادامهدر صورتی که h یکی از آن استثناها باشد که یکنوا نیست، می توان با ایجاد یک اصلاح جزئی آن را یکنوا می‌کنیمخاصیت یکنوایی (monotonicity)تقریباً تمام کشف‌کنندگی‌های مجاز دارای این ویژگی هستند که در طول هر مسیری از ریشه، هزینه f هرگز کاهش پیدا نمی‌کند.این خاصیت برای کشف‌کنندگی، خاصیت یکنوایی (monotonicity) گفته می‌شود.نگاهی گذرا به اثبات کامل A*:

اسلاید ۲۱: f(n’) = max( f(n) , g(n’)+h(n’) )هزینه گره فرزند هزینه گره والداز این طریق، مقادیر گمراه کننده ای که ممکن است با یک هیورستیک یکنوا پدیدار شوند حذف می کنیم. به این معادل سازی معادله pathmax نامیده می شودهر گره جدیدی که تولید می‌شود، باید کنترل کنیم که آیا هزینه f این گره از هزینه f پدرش کمتر است یا خیر. اگر کمتر باشد، هزینه f پدر به جای فرزند می‌نشیند.اگر n’ فرزند n باشد فصل چهارم: جستجوی A* – ادامه۲۱

اسلاید ۲۲: با شرطی بر روی تابع هیورستیک h(n) بهینه نیز خواهد بود:این شرط عبارت است از اینکه تابع h(n) قابل قبول (admissibles) باشددر مثال مسیر یابی بین دو شهر h(n) می تواند خط مستقیم بین دو شهر باشد؟ بله قابل قبول است چون خط مستقیم کوهتاهترین مسیر بین دو شهر است۰ h(n) h*(n) for all nSh*(n) : هزینه واقعی رسیدن از n به هدف باشد آنگاه:بهینه بودن A*: یعنی برای هر گره مثل n ، بیشتر از هزینه واقعی مسیر تا هدف نباشد. یعنی تابع h(n) تخمین اضافی نزند.فصل چهارم: جستجوی A* – ادامه۲۲

اسلاید ۲۳: با توجه به جستجوی با هزینه یکنواخت که وابسته به g(n) است و با شرط اینکه هزینه یک مسیر با ادامه مسیر، کاهش پیدا نخواهد کرد، کامل است آنگاه:فصل چهارم: جستجوی A* – ادامه۲۳f(n’) = g(n’) + h(n’) = g(n) + c + h(n’) f(n) = g(n) + h(n) f(n’) f(n)g(n) + c + h(n’) g(n) + h(n) c + h(n’) h(n)نا برابری مثلثی

اسلاید ۲۴: ۲۷۳۱۱XYh=100h=1h=0h=0g(X)+h(X) = 102g(Y)+h(Y) = 74Optimal path is not found!در صورتی A* جواب بهینه را می دهد که h قابل قبول باشد در مثال فوق h قابل قبول نیستمثالفصل چهارم: جستجوی A* – ادامه۲۴

اسلاید ۲۵: اگر f* هزینه هزینه مسیر راه حل (هزینه واقعی مسیر بهینه از شروع تا هدف) تعریف شود می توان گفت: A* تمام گره ها با f(n) < f* را بسط خواهد دادفصل چهارم: جستجوی A* – ادامهf*25

اسلاید ۲۶: اگر f* هزینه هزینه مسیر راه حل (هزینه واقعی مسیر بهینه از شروع تا هدف) تعریف شود می توان گفت: A* تمام گره ها با f(n) < f* را بسط خواهد داد A*ممکن است تعداد از گره هایی که f(n)=f* است قبل از اینکه گره هدف انتخاب شود بسط دهد A* تمام گره ها با f(n)>f* را بسط نخواهد داد. یعنی الگوریتم A* قادر است گره های بدل را بدون امتحان حذف یا هرس کند.فصل چهارم: جستجوی A* – ادامه

اسلاید ۲۷: ۲۷فصل چهارم: جستجوی A* – ادامه (کارآ بهینه Optimally effecient) یعنی هیچ الگوریتم بهینه ای که جستجو را از ریشه شروع می کند، تضمین نمی کند تعداد گره های کمتری نسبت به A* ایجاد کند و در زمانی که تابع هیورستیک بکار رفته در تمام الگوریتمها یکسان باشد. یک الگوریتم ممکن است که راه حل بهینه را در صورتی که همه گره ها با f(n)<f* بسط ندهد، گم کند.A* به طور موثری برای هر تابع h قابل قبول، از نظر بهینگی کارآ می باشد.

اسلاید ۲۸: یک راه برای تشخیص کیفیت کشف‌کنندگی فاکتور انشعاب مؤثر b* استمعمولاً فاکتور انشعاب مؤثر که توسط کشف‌کنندگی نمایش داده می‌شود، مقدار ثابتی دارد.یک کشف‌کنندگی خوب طراحی شده، b* آن در حدود ۱ است.اثر صحت کشف‌کنندگی بر کارایی:فاکتور انشعاب مؤثر b* (Effective Branching Factor) تعداد گره‌های بسط داده شده توسط A* برای یک مسئله ویژه N باشد و عمق راه حل d، سپسb* فاکتور انشعابی است که یک درخت یکنواخت با عمق d خواهد داشت تا گره‌های N را نگهدارد. بنابراین: ۱+ b*+( b*)2…+( b*)d = Nفصل چهارم: جستجوی A* – کارآیی A*28

اسلاید ۲۹: مثالیعنی متوسط تعداد گره هایی که در هر سطر بسط می دهد تا به هدف برسد برابر با ۱.۹۱ است اگر هدف در عمق ۵ باشد d = 5و تعداد گره هایی A* بسط داده تا به هدف رسیده برابر ۲۵ باشد N = 25 آنگاه :b* = 1.91 تابع هیورستیکی که b* آن به یک نزدیکتر باشد بهتر طراحی شده استیعنی بین توابع h آن تابعی که b* آن به یک نزدیکتر است مناسبتر است زیرا تعداد گره کمتری بسط می دهد.فصل چهارم: جستجوی A* – کارآیی A*29

اسلاید ۳۰: معمای ۸ یکی از مسائل اولیه کشف‌کنندگی بود.h2 = مجموع فواصل چهارخانه‌ها از مکان‌های هدف صحیحشان است. فاصله‌ای که ما حساب می‌کنیم، مجموع فواصل عمودی و افقی است که بعضی وقتها city block distance و یا Manhattan distance نامیده می‌شود.اگر خواستار یافتن راه‌حل‌های کوتاه باشیم، به یک تابع کشف‌کننده نیاز داریم که هرگز در تعداد مراحل به هدف اغراق نکند. در اینجا ما دو کاندید داریم:h1 = تعداد چهارخانه‌هایی که در مکان‌های نادرست هستند. h1 یک کشف‌کننده مجاز است، زیرا واضح است که هر چهارخانه‌ای که خارج از مکان درست باشد حداقل یکبار باید جابجا شود.فصل چهارم: جستجوی A* – کارآیی A*30

اسلاید ۳۱: اگر مجموعه ای از توابع مثل {h1,h2,h3,…,hn} وجود داشته باشد و هیچ کدام بر دیگری برتری نداشته باشد بین hهای موجود hای انتخاب می شود که بیشتر از همه باشد آنگاه h(n) = max{h1,h2,h3,…,hn} در مثال معمای ۸h1 و h2 هر قابل قبول اند و جواب بهینه را می دهند وh1 < h2h2 کارآتر از h1 است زیرا تعداد گرهای کمتری را بسط می دهدفصل چهارم: جستجوی A* – کارآیی A*31

اسلاید ۳۲: هزینه جست و جوفاکتور انشعاب مؤثرمیانگین گره های بسط یافته در جستجوی عمقی تکرار شوندهIDS و A* و فاکتور انشعاب مؤثر با استفاده از h1 و h2اثر صحت کشف‌کنندگی بر کارایی:فصل چها