هوش مصنوعی (حل مسئله با جستجو)

هوش مصنوعی (حل مسئله با جستجو)

اسلاید 1: 1هوش مصنوعی نام مرجع : Artificial Intelligence نویسنده :استوارت راسل، پیتر نورویگ

اسلاید 2: 2هوش مصنوعيفصل سومحل مسئله با جستجو

اسلاید 3: 3هوش مصنوعي Artificial Intelligenceفهرستعاملهای حل مسئلهمسئلهاندازه گيری کارايي حل مسئلهجستجوی ناآگاهانهاجتناب از حالتهای تکراریجستجو با اطلاعات ناقص

اسلاید 4: 4حل مسئله با جستجوعاملهای حل مسئلهچهار گام اساسي برای حل مسائلفرموله کردن هدف: وضعيتهای مطلوب نهايي کدامند؟فرموله کردن مسئله: چه فعاليتها و وضعيتهايي برای رسيدن به هدف موجود است؟جستجو: انتخاب بهترين دنباله از فعاليتهايي که منجر به حالاتی با مقدار شناخته شده ميشود.اجرا: وقتی دنباله فعاليت مطلوب پيدا شد، فعاليتهای پيشنهادی آن ميتواند اجرا شود.

اسلاید 5: 5حل مسئله با جستجومثال: نقشه رومانی

اسلاید 6: 6حل مسئله با جستجوصورت مسأله: رفتن از آراد به بخارستفرموله کردن هدف: رسيدن به بخارستفرموله کردن مسئله: وضعيتها: شهرهای مختلففعاليتها: حرکت بين شهرهاجستجو: دنباله ای از شهرها مثل:آراد، سيبيو، فاگارس، بخارستاين جستجو با توجه به کم هزينه ترين مسير انتخاب ميشودمثال: نقشه رومانی

اسلاید 7: 7حل مسئله با جستجومسئلهحالت اوليه: حالتی که عامل از آن شروع ميکند. در مثال رومانی: شهر آراد n(Arad)تابع جانشين: توصيفي از فعاليتهای ممکن که برای عامل مهيا است. در مثال رومانی:Zerind,Sibui,Timisoara} S(Arad)={فضای حالت: مجموعه ای از حالتها که از حالت اوليه ميتوان به آنها رسيد. در مثال رومانی: کليه شهرها که با شروع از آراد ميتوان به آنها رسيدتابع جانشين + حالت اوليه = فضای حالت

اسلاید 8: 8حل مسئله با جستجوآزمون هدف: تعيين ميکند که آيا حالت خاصی، حالت هدف است يا خيرهدف صريح: در مثال رومانی، رسيدن به بخارستهدف انتزاعی: در مثال شطرنج، رسيدن به حالت کيش و ماتمسير: دنباله ای از حالتها که دنباله ای از فعاليتها را به هم متصل ميکند. در مثال رومانی: Arad, Sibiu, Fagaras يک مسير استهزينه مسير: برای هر مسير يک هزينه عددی در نظر ميگيرد. در مثال رومانی: طول مسير بين شهرها بر حسب کيلومترراه حل مسئله مسيری از حالت اوليه به حالت هدف است راه حل بهينه کمترين هزينه مسير را دارد

اسلاید 9: 9حل مسئله با جستجومثال: دنيای جارو برقيحالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.لذا 8 = 2^2* 2حالت در اين جهان وجود داردحالت اوليه: هر حالتی ميتواند به عنوان حالت اوليه طراحی شودتابع جانشين: حالتهای معتبر از سه عمليات: راست، چپ، مکشآزمون هدف: تميزی تمام مربعهاهزينه مسير: تعداد مراحل در مسير

اسلاید 10: 10حل مسئله با جستجومثال: دنيای جارو برقيحالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.لذا 8 = 2^2* 2حالت در اين جهان وجود داردحالت اوليه: هر حالتی ميتواند به عنوان حالت اوليه طراحی شودتابع جانشين: حالتهای معتبر از سه عمليات: راست، چپ، مکشآزمون هدف: تميزی تمام مربعهاهزينه مسير: تعداد مراحل در مسير

اسلاید 11: 11حل مسئله با جستجومثال: معمای8حالتها: مکان هر هشت خانه شماره دار و خانه خالی در يکي از 9 خانهحالت اوليه: هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفتتابع جانشين: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا يا پايينآزمون هدف: بررسی ميکند که حالتی که اعداد به ترتيب چيده شده اند(طبق شکل روبرو) رخ داده يا نههزينه مسير: برابر با تعداد مراحل در مسير

اسلاید 12: 12حل مسئله با جستجومثال: معمای8حالتها: مکان هر هشت خانه شماره دار و خانه خالی در يکي از 9 خانهحالت اوليه: هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفتتابع جانشين: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا يا پايينآزمون هدف: بررسی ميکند که حالتی که اعداد به ترتيب چيده شده اند(طبق شکل روبرو) رخ داده يا نههزينه مسير: برابر با تعداد مراحل در مسير

اسلاید 13: 13حل مسئله با جستجومثال: مسئله 8 وزيرفرمول بندی افزايشيحالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت استحالت اوليه: هيچ وزيری در صفحه نيستتابع جانشين: وزيری را به خانه خالی اضافه ميکندآزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرنددر اين فرمول بندی بايد 14^10*3 دنباله ممکن بررسی ميشود

اسلاید 14: 14حل مسئله با جستجومثال: مسئله 8 وزيرفرمول بندی افزايشيحالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت استحالت اوليه: هيچ وزيری در صفحه نيستتابع جانشين: وزيری را به خانه خالی اضافه ميکندآزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرنددر اين فرمول بندی بايد 14^10*3 دنباله ممکن بررسی ميشود

اسلاید 15: 15حل مسئله با جستجومثال: مسئله 8 وزيرفرمول بندی حالت کاملحالتها: چيدمان n وزير (0≤ n≤ 8) ، بطوريکه در هر ستون از n ستون سمت چپ، يک وزير قرار گيرد و هيچ دو وزيری بهم گارد نگيرندحالت اوليه: با 8 وزير در صفحه شروع ميشودتابع جانشين: وزيری را در سمت چپ ترين ستون خالي قرار ميدهد، بطوری که هيچ وزيری آن را گارد ندهدآزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرنداين فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش ميدهد

اسلاید 16: 16حل مسئله با جستجومثال: مسئله 8 وزيرفرمول بندی حالت کاملحالتها: چيدمان n وزير (0≤ n≤ 8) ، بطوريکه در هر ستون از n ستون سمت چپ، يک وزير قرار گيرد و هيچ دو وزيری بهم گارد نگيرندحالت اوليه: با 8 وزير در صفحه شروع ميشودتابع جانشين: وزيری را در سمت چپ ترين ستون خالي قرار ميدهد، بطوری که هيچ وزيری آن را گارد ندهدآزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرنداين فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش ميدهد

اسلاید 17: 17حل مسئله با جستجواندازه گيری کارايي حل مسئلهکامل بودن: آيا الگوريتم تضمين ميکند که در صورت وجود راه حل، آن را بيابد؟بهينگي: آيا اين راهبرد، راه حل بهينه ای را ارائه ميکند.پيچيدگي زمانی: چقدر طول ميکشد تا راه حل را پيدا کند؟تعداد گره های توليد شده در اثنای جستجوپيچيدگی فضا: برای جستجو چقدر حافظه نياز دارد؟حداکثر تعداد گره های ذخيره شده در حافظه

اسلاید 18: 18حل مسئله با جستجواندازه گيری کارايي حل مسئلهکامل بودن: آيا الگوريتم تضمين ميکند که در صورت وجود راه حل، آن را بيابد؟بهينگي: آيا اين راهبرد، راه حل بهينه ای را ارائه ميکند.پيچيدگي زمانی: چقدر طول ميکشد تا راه حل را پيدا کند؟تعداد گره های توليد شده در اثنای جستجوپيچيدگی فضا: برای جستجو چقدر حافظه نياز دارد؟حداکثر تعداد گره های ذخيره شده در حافظه

اسلاید 19: 19حل مسئله با جستجوجستجوی ناآگاهانهناآگاهی اين است که الگوريتم هيچ اطلاعاتی غير از تعريف مسئله در اختيار ندارداين الگوريتمها فقط ميتواند جانشينهايي را توليد و هدف را از غير هدف تشخيص دهندراهبردهايي که تشخيص ميدهد يک حالت غير هدف نسبت به گره غير هدف ديگر، اميد بخش تر است، جست و جوی آگاهانه يا جست و جوی اکتشافي ناميده ميشود.راهبردهاجست و جوی عرضیجست و جوی عمقیجست و جوی عميق کننده تکراریجست و جوی هزينه يکنواختجست و جوی عمقی محدودجست و جوی دو طرفه

اسلاید 20: 20حل مسئله با جستجوجستجوی عرضیABCDEFGHIJKLNMOPQ

اسلاید 21: 21 حل مسئله با جستجوجستجوی عرضیکامل بودن: بلهبهينگی: بله (مشروط)در صورتی بهينه است که هزينه مسير، تابعی غير نزولی از عمق گره باشد.(مثل وقتي که فعاليتها هزينه يکسانی دارند)پيچيدگي زماني:پيچيدگی فضا:کامل بودن:بهينگی: بله (مشروط)

اسلاید 22: 22حل مسئله با جستجوجستجوی هزينه يکنواختABCDEFGHIJKLNMOPQ113اين جستجو گره n را با کمترين هزينه مسير بسط ميدهد

اسلاید 23: 23حل مسئله با جستجوکامل بودن: بلههزينه هر مرحله بزرگتر يا مساوی يک مقدار ثابت و مثبت ε باشد.(هزينه مسير با حرکت در مسير افزايش مي يابد)بهينگی: بله هزينه هر مرحله بزرگتر يا مساوی ε باشد پيچيدگي زماني:پيچيدگی فضا:جستجوی هزينه يکنواختکامل بودن:بهينگی:

اسلاید 24: 24حل مسئله با جستجوجستجوی عمقی234567ABCDEFGHIJKLNMOPQ

اسلاید 25: 25حل مسئله با جستجوجستجوي عمقي:اين استراتژي، يکي از گره‌ها را در پائين‌ترين سطح درخت بسط مي‌دهد؛ اما اگر به نتيجه نرسيد، به سراغ گره‌هايي در سطوح کم عميق‌تر مي‌رود.مزايا:اين جستجو، نياز به حافظه نسبتاً کمي فقط براي ذخيره مسير واحدي از ريشه به يک گره برگي، و گره‌هاي باقي‌مانده بسط داده نشده دارد.پيچيدگي فضا O(bm) مي‌باشد. به طوريکه b فاکتور انشعاب فضاي حالت، و m حداکثر عمق درخت باشد.

اسلاید 26: 26حل مسئله با جستجومعايب:اگر مسيري را اشتباه طي کند، هنگام پائين رفتن گير مي‌کند.جستجوي عمقي نه کامل و نه بهينه است.در درخت‌هاي با عمق نامحدود و بزرگ اين استراتژي کار نمي‌کند.

اسلاید 27: 27حل مسئله با جستجوکامل بودن: خيراگر زير درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل باشد، جستجو هرگز خاتمه نمي يابد.بهينگی: خير پيچيدگي زماني:پيچيدگی فضا:جستجوی عمقی

اسلاید 28: 28حل مسئله با جستجوجستجوی عمقی محدودABCDEFGHIJKLNMOPQمسئله درختهای نامحدود ميتواند به وسيله جست و جوی عمقي با عمق محدود L بهبود يابد

اسلاید 29: 29حل مسئله با جستجوجستجوي عمقي محدود شده:اين استراتژي، براي رهايي از دامي که جستجوي عمقي در آن گرفتار مي‌شد، از يک برش استفاده مي‌کند.جستجوي عمقي محدود شده کامل است اما بهينه نيست.زمان و پيچيدگي فضاي جستجوي عمقي محدودشده، مشابه جستجوي عمقي است. اين جستجو پيچيدگي زماني O(b^L) و فضاي O(bL) را خواهد داشت، که L محدودة عمق است.

اسلاید 30: 30حل مسئله با جستجودر يک درخت جستجوي نمايي، تقريباً تمام گره‌ها در سطح پائين هستند، بنابراين موردي ندارد که سطوح بالايي چندين مرتبه بسط داده شوند. تعداد بسط‌ها در يک جستجوي عمقي محدود شده با عمق d و فاکتور انشعاب b به قرار زير است:1+b+b^2+…+b^d-2+b^d-1+b^d

اسلاید 31: 31حل مسئله با جستجوجستجوی عمقی محدودکامل بودن: خيراگر L<d و سطحی ترين هدف در خارج از عمق محدود قرار داشته باشد، اينراهبرد کامل نخواهد بود.بهينگی: خير اگر L>d انتخاب شود، اين راهبرد بهينه نخواهد بود.پيچيدگي زماني:پيچيدگی فضا:کامل بودن:بهينگي:

اسلاید 32: 32حل مسئله با جستجوجستجوی عميق کننده تکراريABCDEFGHIJKLNMOPQ

اسلاید 33: 33حل مسئله با جستجوجستجوی عميق کننده تکراريABCDEFGHIJKLNMOPQ

اسلاید 34: 34حل مسئله با جستجوجستجوی عميق کننده تکراريABCDEFGHIJKLNMOPQSR

اسلاید 35: 35حل مسئله با جستجوجستجوي عميق‌کننده تکراري:قسمت دشوار جستجوي عمقي محدود شده، انتخاب يک محدودة خوب است.اگر محدودة عمق بهتري را پيدا کنيم، اين محدوده، ما را به سوي جستجوي کاراتري سوق مي‌دهد. اما براي بيشتر مسائل، محدودة عمقي مناسب را تا زماني که مسئله حل نشده است، نمي‌شناسيم.جستجوي عميق‌کنندة تکراري استراتژي است که نظريه انتخاب بهترين محدودة عمقي، توسط امتحان تمام محدودة مسيرهاي ممکن را يادآوري مي‌کند.

اسلاید 36: 36حل مسئله با جستجومزايا:ترکيبي از مزاياي جستجوي سطحي و عمقي را دارد.اين جستجو مانند جستجوي سطحي کامل و بهينه است، اما فقط مزيت درخواست حافظه اندک را از جستجوي عمقي دارد.مرتبه بسط حالات مشابه جستجوي سطحي است، به جز اينکه بعضي حالات چند بار بسط داده مي‌شوند.

اسلاید 37: 37حل مسئله با جستجودر جستجوي عميق‌کننده تکراري، گره‌هاي سطوح پائيني يک بار بسط داده مي‌شوند، آنهايي که يک سطح بالاتر قرار دارند دوبار بسط داده مي‌شوند و الي‌آخر تا به ريشه درخت جستجو برسد، که d+1 بار بسط داده مي‌شوند.بنابراين مجموع دفعات بسط در اين جستجو عبارتست از:(d+1)1+(d)b^1+(d-1)b^2+…+3b^d-2+2b^d-1+1b^dپيچيدگي زماني اين جستجو هنوز O(b^d) است، و پيچيدگي فضا O(bd) است.در حالت کلي، عميق‌کننده تکراري، روش جستجوي برتري است؛ زماني که فضاي جستجوي بزرگي وجود دارد و عمق راه حل نيز مجهول است.

اسلاید 38: 38حل مسئله با جستجوجستجوی عميق کننده تکراريکامل بودن: بلهدر صورتی که فاکتور انشعاب محدود باشدبهينگی: بله وقتی که هزينه مسير، تابعی غير نزولی از عمق گره باشدپيچيدگي زماني:پيچيدگی فضا:

اسلاید 39: 39حل مسئله با جستجوجستجوی دو طرفهانجام دو جست و جوی همزمان، يکي از حالت اوليه به هدف و ديگری از هدف به حالت اوليه تا زمانی که دو جست و جو به هم برسند

اسلاید 40: 40حل مسئله با جستجوجستجوي دوطرفه:ايده جستجوي دوطرفه در واقع شبيه‌سازي جستجويي به سمت جلو از حالت اوليه و به سمت عقب از هدف است و زماني که اين دو جستجو به هم برسند، متوقف مي‌شود.براي پياده‌سازي الگوريتم سؤالات زير بايد پاسخ داده شوند:سؤال اصلي اين است که، جستجو از سمت هدف به چه معني است؟ ماقبل‌هاي يک گره n را گره‌هايي درنظر مي‌گيريم که n مابعد آنها باشد. جستجو به سمت عقب بدين معناست که توليد ماقبل‌ها از گرة هدف آغاز شود.

اسلاید 41: 41حل مسئله با جستجوزماني که تمام عملگرها، قابل وارونه‌شدن باشند، مجموعه ماقبل‌ها و مابعدها يکسان هستند.چه کار مي‌توان کرد زماني که هدف‌هاي متفاوتي وجود داشته باشد؟ اگر ليست صريحي از حالت‌هاي هدف وجود داشته باشد، مي‌توانيم يک تابع ماقبل براي مجموعه حالت تقاضا کنيم در حاليکه تابع مابعد يا (جانشين) در جستجوي مسائل چندوضعيته به کار مي‌رود.بايد يک راه موثر براي کنترل هر گره جديد وجود داشته باشد تا متوجه شويم که آيا اين گره قبلاً در درخت جستجو توسط جستجوي طرف ديگر، ظاهر شده است يا خير.نياز داريم که تصميم بگيريم که چه نوع جستجويي در هر نيمه قصد انجام دارد.

اسلاید 42: 42حل مسئله با جستجوجستجوی دو طرفهکامل بودن: بلهاگر هر دو جستجو، عرضی باشند و هزينه تمام مراحل يکسان باشدبهينگی: بله اگر هر دو جستجو، عرضی باشند و هزينه تمام مراحل يکسان باشدپيچيدگي زماني:پيچيدگی فضا:کامل بودن:بهينگي:

اسلاید 43: 43حل مسئله با جستجومقايسه استراتژي‌هاي جستجو:ارزيابي استراتژي‌هاي جستجو. b فاکتور انشعاب، d عمل پاسخ، m ماکزيمم عمق درخت جستجو، l محدوديت عمق است.Bidirectional (if applicable)Iterative DeepeningDepth-LimitedDepth-FirstUniform-CostBreadth-FirstCriterionbd/2bdblbmbdbdTimebd/2bdblbmbdbdSpaceYesYesNoNoYesYesOptimal?YesYesYes, ifNoYesYes‍Complete

اسلاید 44: 44حل مسئله با جستجواجتناب از حالتهای تکراریوجود حالتهای تکراری در يک مسئله قابل حل، ميتواند آن را به مسئله غير قابل حل تبديل کند

اسلاید 45: 45حل مسئله با جستجواجتناب از حالات تکراري:براي مسائل زيادي، حالات تکراري غيرقابل اجتناب هستند. اين شامل تمام مسائلي مي‌شود که عملگرها قابل وارونه شدن باشند، مانند مسائل مسيريابي و کشيش‌ها و آدمخوارها.

اسلاید 46: 46حل مسئله با جستجوسه راه براي حل مشکل حالات تکراري براي مقابله با افزايش مرتبه و سرريزي فشار کار کامپيوتر وجود دارد: به حالتي که هم اکنون از آن آمده‌ايد، برنگرديد. از ايجاد مسيرهاي دوار بپرهيزيد. حالتي را که قبلاً توليد شده است، مجدداً توليد نکنيد. اين مسئله باعث مي‌شود که هر حالت در حافظه نگهداري شود، پيچيدگي فضايي O(bd) داشته باشد. بهتر است که به O(s) توجه کنيد که s تعداد کل حالات در فضاي حالت ورودي است.

اسلاید 47: 47حل مسئله با جستجوجستجو با اطلاعات ناقصمسئله های فاقد حسگر: اگر عامل فاقد حسگر باشد، ميتواند در يکي از چند حالت اوليه باشد و هر فعاليت ميتواند آن را به يکي از چند حالت جانشين ببردمسئله های اقتضايي: اگر محيط به طور جزئی قابل مشاهده باشد يا اگر فعاليتها قطعي نباشد، ادراکات عامل، پس از هر عمل، اطلاعات جديدي را تهيه ميکنند. هر ادراک ممکن، اقتضايی را تعريف ميکند که بايد برای آن برنامه ريزی شودمسائل خصمانه: اگرعدم قطعيت در اثر فعاليتهای عامل ديگری بوجود آيد، مسئله را خصمانه گويندمسئله های اکتشافی: وقتی حالتها و فعاليتهای محيط ناشناخته باشند، عامل بايد سعي کند آنها را کشف کند. مسئله های اکتشافی را ميتوان شکل نهايی مسئله های اقتضايي دانست

اسلاید 48: 48حل مسئله با جستجومثال: دنيای جاروبرقی فاقد حسگرعامل جارو تمام اثرات فعاليتهايش را ميداند اما فاقد حسگر است.حالت اوليه آن يکي از اعضای مجموعه{1،2،3،4،5،6،7،8} ميباشدفعاليت ((Right {2،4،6،8}فعاليت (Right,Suck) {4،8}فعاليت (Right,Suck,Left,Suck) تضمين ميکند که صرف نظر از حالت اوليه، به حالت هدف، يعنی 7 برسد

اسلاید 49: 49هوش مصنوعيفصل چهارمجست و جوی آگاهانه و اکتشاف

اسلاید 50: 50هوش مصنوعي Artificial Intelligenceفهرستمتدهای جست و جوی آگاهانهيادگيری برای جست و جوی بهترجست و جوی محلی و بهينه سازیجست و جوی محلی در فضاهای پيوستهعاملهای جست و جوی Online

اسلاید 51: 51جست و جوی آگاهانه و اکتشافمتدهای جستجوی آگاهانهبهترين جستجوحريصانهA*IDA*RBFSMA* و SMA*جستجوی محلی و بهينه سازیتپه نوردیشبيه سازی حرارتپرتو محلیالگوريتمهای ژنتيک

اسلاید 52: 52حل مسئله با جستجوجستجوي بهترين:اين استراتژي به اين صورت بيان مي‌شود که در يک درخت، زماني که گره‌ها مرتب مي‌شوند، گره‌اي که بهترين ارزيابي را داشته باشد، قبل از ديگر گره‌ها بسط داده مي‌شود.هدف: يافتن راه‌حل‌هاي کم‌هزينه است، اين الگوريتم‌ها عموماً از تعدادي معيار تخمين براي هزينه راه‌حل‌ها استفاده مي‌‌کنند و سعي بر حداقل کردن آنها دارند.جست و جوی آگاهانه و اکتشاف

اسلاید 53: 53حداقل هزينه تخمين زده شده براي رسيدن به هدف: جستجوي حريصانهيکي از ساده‌ترين استراتژي‌هاي جستجوي بهترين، به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف است. بدين صورت که حالت گره‌اي که به حالت هدف نزديک‌تر است، ابتدا بسط داده مي‌شود.تابع کشف‌کننده: هزينه رسيدن به هدف از يک حالت ويژه مي‌تواند تخمين زده شود اما دقيقاً تعيين نمي‌شود. تابعي که چنين هزينه‌هايي را محاسبه مي‌کند تابع کشف‌کننده h ناميده مي‌شود.جستجوي حريصانه: جستجوي بهترين که h را به منظور انتخاب گره بعدي براي بسط استفاده مي‌کند، جستجوي حريصانه (greedy search) ناميده مي‌شود.جست و جوی آگاهانه و اکتشاف

اسلاید 54: 54جست و جوی آگاهانه و اکتشافتعاريفتابع هزينه مسير، g(n) : هزينه مسير از گره اوليه تا گره nتابع اکتشافی، h(n) : هزينه تخمينی ارزان ترين مسير از گره n به گره هدفتابع بهترين مسير، h*(n) : ارزان ترين مسير از گره n تا گره هدفتابع ارزيابي، f(n) : هزينه تخمينی ارزان ترين مسير از طريق nf(n): g(n) + h(n)f*(n) : هزينه ارزان ترين مسير از طريقn f*(n): g(n) + h*(n)

اسلاید 55: 55جست و جوی آگاهانه و اکتشافABCDEFGHIKMLNO3PQJWVXYZRSTU1121332323231112321113231253013231221121021312332جستجوی حريصانه

اسلاید 56: 56جست و جوی آگاهانه و اکتشاف1ABCDEFGNO3X112111131253031322345جستجوی حريصانه

اسلاید 57: 57جست و جوی آگاهانه و اکتشافجستجوی حريصانهAFGHIMLNOPQWVXYZRSTU1332323111232111323BC2114DE1151KJ33013231221121021312333

اسلاید 58: 58جست و جوی آگاهانه و اکتشافجستجوی حريصانه2ABC2114DE1151KJ330113

اسلاید 59: 59ويژگي‌هاي جستجوي حريصانه: جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف، مانند جستجوي عمقي است، اما زماني که به بن‌بست مي‌رسد، برمي‌گردد. اين جستجو بهينه نيست و ناکامل است. پيچيدگي زماني در بدترين حالت براي جستجوي حريصانه O(bm)، که m حداکثر عمق فضاي جستجو است. جستجوي حريصانه تمام گره‌ها را در حافظه نگه مي‌دارد، بنابراين پيچيدگي فضاي آن مشابه پيچيدگي زماني آن است. ميزان کاهش پيچيدگي به مسئله و کيفيت تابع h بستگي دارد.جست و جوی آگاهانه و اکتشاف

اسلاید 60: 60جست و جوی آگاهانه و اکتشافجستجوی حريصانهکامل بودن: خيراما اگر h = h* آنگاه جستجو کامل ميشودبهينگی: خيراما اگر h = h* آنگاه جستجو کامل ميشودپيچيدگي زماني:اما اگر h = h* آنگاهپيچيدگی فضا:اما اگر h = h* آنگاهکامل بودن:بهينگی:

اسلاید 61: 61جست و جوی آگاهانه و اکتشافحداقل‌سازي مجموع هزينه مسير: جستجوي A*جستجو با هزينه يکسان، هزينه مسير، g(n) را نيز حداقل مي‌کند.با ترکيب دو تابع ارزيابي داريم:f(n) = g(n) + h(n):g(n) هزينه مسير از گره آغازين به گره n را به ما مي‌دهد.h(n): هزينه تخمين زده شده از ارزانترين مسير از n به هدف استو ما داريم:هزينه تخمين زده شده ارزانترين راه حل از طريق n = f(n)

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

اسلاید 63: 63جست و جوی آگاهانه و اکتشافجستجوی A*A/5B/4C/4D/5E/1F/3G/2H/2I/3K/0M/2L/3N/1O/32P/3Q/1J/1W/1V/2X/0Y/2Z/1R/2S/2T/1U/1111133332323111232111323

اسلاید 64: 64جست و جوی آگاهانه و اکتشافجستجوی A*132A/5B/4C/42165X/014N/1O/31384F/3G/21154

اسلاید 65: 65جست و جوی آگاهانه و اکتشافجستجوی A*A/5B/1C/4D/5E/1F/3G/2H/2I/3K/0M/2L/3N/1O/32P/3Q/1J/1W/1V/2X/0Y/2Z/1R/2S/2T/1U/1111133332323111232111323

اسلاید 66: 66جستجوی A*جست و جوی آگاهانه و اکتشافA/521345B/1C/42135D/5E/11184K/0J/13367X/014N/1O/31384F/3G/21154

اسلاید 67: 67جستجوی A*جست و جوی آگاهانه و اکتشافA/5B/1C/9D/5E/1F/3G/2H/2I/3K/0M/2L/3N/1O/32P/3Q/1J/1W/1V/2X/0Y/2Z/1R/2S/2T/1U/1111133332323111232111323

اسلاید 68: 68جستجوی A*جست و جوی آگاهانه و اکتشافA/5213B/1C/921310D/5E/11184K/0J/13361

اسلاید 69: 69جست و جوی آگاهانه و اکتشافh*(n) : هزينه واقعي رسيدن از n به هدف است.در استفاده عملي، خطاها با هزينه مسير متناسب هستند، و سرانجام رشد نمايي هر کامپيوتر را تسخير مي‌کند. البته، استفاده از يک کشف‌کنندگي خوب هنوز باعث صرفه‌جويي زيادي نسبت به جستجوي ناآگاهانه مي‌شود.A* معمولاً قبل از اينکه دچار کمبود زمان شود، دچار کمبود فضا مي‌شود. زيرا اين جستجو تمام گره‌هاي توليد شده را در حافظه ذخيره مي‌کند.

اسلاید 70: 70جستجوی A*جست و جوی آگاهانه و اکتشافکامل بودن: بلهبهينگی: بلهپيچيدگي زماني:اما اگر h = h* آنگاهپيچيدگی فضا:اما اگر h = h* آنگاه

اسلاید 71: 71جست و جوی آگاهانه و اکتشافABCDEFG1H1111111211001ABCDEFG1H1111113421001h ≤ h*h ≤ h*/جستجوی A*

اسلاید 72: 72جست و جوی آگاهانه و اکتشافجستجوی A*1234ABCDEFG1H1111111211001ABCDEFG1H1111113421001123456h ≤ h*h ≤ h*/

اسلاید 73: 73جست و جوی آگاهانه و اکتشافA/100B/80C/95E/86F/78G/90T/60H/80J/82N/72L/80K/85W/52X/58M/75Y/47Z/50O/78P/79D/90M/75I/87P/79O/78U/81V/83T/60R/20Q/0W/52X/58Y/47Z/50S/7010جستجوی A* و اجتناب از گره های تکراریهزينه هر مرحله 10 ميباشد

اسلاید 74: 74جست و جوی آگاهانه و اکتشافجستجوی A* و اجتناب از گره های تکراریA/100B/80C/95D/9090105100E/86F/7810698M/75I/8795107P/79O/78108109G/90T/6080110W/52X/58Y/47Z/5088829087R/20Q/07050N/72M/75105102T/60S/70100110W/52X/58102108Y/47Z/5010711012345678910

اسلاید 75: 75جست و جوی آگاهانه و اکتشافمثال ديگر از جستجوی A*f(n)=g(n) + h(n)

اسلاید 76: 76جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانیجستجوی Bucharest با شروع از Aradf(Arad) = g(Arad)+h(Arad)=0+366=366

اسلاید 77: 77جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانیََArad را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449بهترين انتخاب شهر Sibiu است

اسلاید 78: 78جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانیََSibiu را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413بهترين انتخاب شهر Rimnicu Vilcea است

اسلاید 79: 79جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانیََRimnicu Vilcea را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:f(Craiova)=c(Rimnicu Vilcea, Craiova)+h(Craiova)=360+160=526f(Pitesti)=c(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417f(Sibiu)=c(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553بهترين انتخاب شهر Fagaras است

اسلاید 80: 80جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانیََ Fagaras را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450بهترين انتخاب شهر Pitesti !!! است

اسلاید 81: 81جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانیََ Pitesti را باز کرده و f(n) را برای هر يک از زيربرگها محاسبه ميکنيم:f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418بهترين انتخاب شهر Bucharest !!! است

اسلاید 82: 82جست و جوی آگاهانه و اکتشافجستجوی A* در نقشه رومانی

اسلاید 83: 83جست و جوی آگاهانه و اکتشافجستجوی اکتشافی با حافظه محدود IDA*ساده ترين راه برای کاهش حافظه مورد نياز A* استفاده از عميق کننده تکرار در زمينه جست و جوی اکتشافي است.الگوريتم عميق کننده تکرار A* IDA* در جستجوی IDA* مقدار برش مورد استفاده، عمق نيست بلکه هزينه f(g+h) است.IDA* برای اغلب مسئله های با هزينه های مرحله ای، مناسب است و از سربار ناشي از نگهداری صف مرتبي از گره ها اجتناب ميکند

اسلاید 84: 84بهترين جستجوی بازگشتي RBFSجست و جوی آگاهانه و اکتشافساختار آن شبيه جست و جوی عمقي بازگشتي است، اما به جای اينکه دائما به طرف پايين مسير حرکت کند، مقدار f مربوط به بهترين مسير از هر جد گره فعلی را نگهداری ميکند، اگر گره فعلی از اين حد تجاوز کند، بازگشتی به عقب برميگردد تا مسير ديگري را انتخاب کند.اين جستجو اگر تابع اکتشافی قابل قبولی داشته باشد، بهينه است.پيچيدگي فضايي آن O(bd) استتعيين پيچيدگی زمانی آن به دقت تابع اکتشافی و ميزان تغيير بهترين مسير در اثر بسط گره ها بستگی دارد.

اسلاید 85: 85جست و جوی آگاهانه و اکتشافبهترين جستجوی بازگشتي RBFSRBFS تا حدی از IDA* کارآمدتر است، اما گره های زيادی توليد ميکند. IDA* و RBFS در معرض افزايش تواني پيچيدگي قرار دارند که در جست و جوی گرافها مرسوم است، زيرا نميتوانند حالتهای تکراری را در غير از مسير فعلي بررسي کنند. لذا، ممکن است يک حالت را چندين بار بررسي کنند. IDA* و RBFS از فضای اندکي استفاده ميکنند که به آنها آسيب ميرساند. IDA* بين هر تکرار فقط يک عدد را نگهداری ميکند که هزينه فعلي f است. RBFS اطلاعات بيشتری در حافظه نگهداری ميکند

اسلاید 86: 86جست و جوی آگاهانه و اکتشافبهترين جستجوی بازگشتي در نقشه رومانی

اسلاید 87: 87جست و جوی آگاهانه و اکتشافبهترين جستجوی بازگشتي در نقشه رومانی

اسلاید 88: 88بهترين جستجوی بازگشتي در نقشه رومانیجست و جوی آگاهانه و اکتشاف

اسلاید 89: 89جست و جوی آگاهانه و اکتشافجستجوی حافظه محدود ساده SMA* SMA* بهترين برگ را بسط ميدهد تا حافظه پر شود. در اين نقطه بدون از بين بردن گره های قبلي نميتواند گره جديدی اضافه کندSMA* هميشه بدترين گره برگ را حذف ميکند و سپس از طريق گره فراموش شده به والد آن بر ميگردد. پس جد زير درخت فراموش شده، کيفيت بهترين مسير را در آن زير درخت ميدانداگر عمق سطحی ترين گره هدف کمتر از حافظه باشد, کامل است. SMA* بهترين الگوريتم همه منظوره برای يافتن حلهای بهينه ميباشد

اسلاید 90: 90جست و جوی آگاهانه و اکتشافجستجوی حافظه محدود ساده SMA* اگر مقدار f تمام برگها يکسان باشد و الگوريتم يک گره را هم برای بسط و هم برای حذف انتخاب کند، SMA* اين مسئله را با بسط بهترين برگ جديد و حذف بهترين برگ قديمی حل ميکندممکن است SMA* مجبور شود دائما بين مجموعه ای از مسيرهای حل کانديد تغيير موضع دهد، در حالی که بخش کوچکی از هر کدام در حافظه جا شودمحدوديتهای حافظه ممکن است مسئله ها را از نظر زمان محاسباتی، غير قابل حل کند.

اسلاید 91: 91حل مسئله با جستجوSMA* داراي خواص زير است: مي‌تواند از تمام حافظه قابل دسترس استفاده کند. از حالات تکراري تا جايي که حافظه اجازه مي‌دهد، جلوگيري مي‌کند. اين الگوريتم کامل است به شرط آنکه حافظه براي ذخيره کم عمق‌ترين مسير راه حل کافي باشد. اين الگوريتم بهينه است، اگر حافظه کافي براي ذخيره کم‌عمق‌ترين مسير راه‌حل کافي باشد. بعلاوه بهترين راه‌حلي را برمي‌گرداند که بتواند با حافظه موجود مطابقت داشته باشد. زماني که حافظه موجود براي درخت جستجوي کامل کافي باشد، جستجو Optimally efficient است.

اسلاید 92: 92حل مسئله با جستجوطراحي SMA* ساده است. زماني که نياز به توليد فرزند داشته باشد ولي حافظه‌اي نداشته باشد، نياز به ساختن فضا بر روي صف دارد. براي انجام اين امر، يک گره را حذف مي‌کند. گره‌هايي که به اين طريق از صف حذف مي‌شوند، گره‌هاي فراموش‌شده يا (forgotten nodes) ناميده مي‌شوند. براي اجتناب از جستجوي مجدد زيردرخت‌هايي که از حافظه حذف شده‌اند، در گره‌هاي اجدادي، اطلاعاتي در مورد کيفيت بهترين مسير در زير درخت فراموش شده، نگهداري مي‌شود.

اسلاید 93: 93جستجوی گراف با A* جست و جوی آگاهانه و اکتشاف21411112431H/0A/6B/5C/1D/1E/2F/2G/1J/11

اسلاید 94: 94جست و جوی آگاهانه و اکتشافA/6B/5C/114651جستجوی گراف با A*

اسلاید 95: 95جست و جوی آگاهانه و اکتشافجستجوی گراف با A* A/6B/5C/1D/1G/11421656712

اسلاید 96: 96جست و جوی آگاهانه و اکتشافجستجوی گراف با A* A/6B/5C/1D/1G/11421J/1165673127

اسلاید 97: 97جست و جوی آگاهانه و اکتشافجستجوی گراف با A* A/6B/5C/1D/1E/2F/2G/11443211J/1165446567531274

اسلاید 98: 98جست و جوی آگاهانه و اکتشافجستجوی گراف با A* A/6B/5C/1D/1E/2F/2G/114413211J/116544656765312745

اسلاید 99: 99جست و جوی آگاهانه و اکتشافجستجوی گراف با A* A/6B/5C/1D/1E/2F/2G/11132211J/1164456765312564

اسلاید 100: 100جست و جوی آگاهانه و اکتشافجستجوی گراف با A* H/0A/6B/5C/1D/1E/2F/2G/1113211J/1116544656765631275647

اسلاید 101: 101جست و جوی آگاهانه و اکتشافيادگيری برای جست و جوی بهتر روشهای جست و جوی قبلي، از روشهای ثابت استفاده ميکردند.عامل با استفاده از فضای حالت فراسطحی ميتواند ياد بگيرد که بهتر جست و جو کندهر حالت در فضای حالت فرا سطحی، حالت(محاسباتی) داخلیِ برنامه ای را تسخير ميکند که فضای حالت سطح شیء، مثل رومانی را جست و جو ميکندالگوريتم يادگيری فراسطحی ميتواند چيزهايي را از تجربيات بياموزد تا زيردرختهای غير قابل قبول را کاوش نکند.هدف يادگيری، کمينه کردن کل هزينه، حل مسئله است

اسلاید 102: 102جست و جوی آگاهانه و اکتشافتوابع اکتشافیمثال برای معمای8ميانگِين هزينه حل تقريبا 22 مرحله و فاکتور انشعاب در حدود 3 است.جست و جوی جامع تا عمق 22 : با انتخاب يک تابع اکتشافی مناسب ميتوان مراحل جستجو را کاهش داد

اسلاید 103: 103جست و جوی آگاهانه و اکتشافدو روش اکتشافي متداول برای معمای8تعداد کاشيها در مکانهای نادرستدر حالت شروع اکتشاف قابل قبولی است، زيرا هر کاشي که در جای نامناسبی قرار دارد، حداقل يکبار بايد جابجا شود

اسلاید 104: 104جست و جوی آگاهانه و اکتشافدو روش اکتشافي متداول برای معمای8مجموعه فواصل کاشيها از موقعيتهای هدف آنهادر حالت شروعچون کاشيها نميتوانند در امتداد قطر جا به جا شوند, فاصله ای که محاسبه ميکنيم مجموع فواصل افقی و عمودی است. اين فاصله را فاصله بلوک شهر يا فاصله مانهاتان مينامند.

اسلاید 105: 105جست و جوی آگاهانه و اکتشافدو روش اکتشافي متداول برای معمای8مجموعه فواصل کاشيها از موقعيتهای هدف آنها قابل قبول است، زيرا هر جابجايي که ميتواند انجام گيرد، به اندازه يک مرحله به هدف نزديک ميشود.هيچ کدام از اين برآوردها، هزينه واقعی راه حل نيستهزينه واقعي 36 است

اسلاید 106: 106جست و جوی آگاهانه و اکتشافاثر دقت اکتشاف بر کاراييفاکتور انشعاب مؤثر b*اگر تعداد گره هايي که برای يک مسئله خاص توسط A* توليد ميشود برابر با N و عمق راه حل برابر با d باشد، آن گاه b* فاکتور انشعابی است که درخت يکنواختی به عمق d بايد داشته باشد تا حاوی N+1 گره باشدفاکتور انشعاب مؤثر معمولاً برای مسئله های سخت ثابت استاندازه گيريهای تجربي b* بر روی مجموعه کوچکي از مسئله ها ميتواند راهنمای خوبي برای مفيد بودن اکتشاف باشدمقدار b* در اکتشافي با طراحي خوب، نزديک 1 است

اسلاید 107: 107جست و جوی آگاهانه و اکتشافاثر دقت اکتشاف بر کاراييهزينه جست و جوفاکتور انشعاب مؤثرميانگين گره های بسط يافته در جستجویIDS و A* و فاکتور انشعاب مؤثر با استفاده ازh1 و h2

اسلاید 108: 108جست و جوی آگاهانه و اکتشافاثر دقت اکتشاف بر کارايياگر برای هر گره n داشته باشيم: h2(n) >= h1(n) h2 بر h1غالب استغالب بودن مستقيما به کارايي ترجمه ميشودتعداد گره هايي که با بکارگيری h2 بسط داده ميشود، هرگز بيش از بکارگيری h1 نيستهميشه بهتر است از تابع اکتشافی با مقادير بزرگ استفاده کرد، به شرطی که زمان محاسبه اکتشاف، خيلي بزرگ نباشد

اسلاید 109: 109جست و جوی آگاهانه و اکتشافالگوريتم های جست و جوی محلی و بهينه سازیالگوريتم های قبلی، فضای جست و جو را به طور سيستماتيک بررسی ميکنندتا رسيدن به هدف يک يا چند مسير نگهداری ميشوندمسير رسيدن به هدف، راه حل مسئله را تشکيل ميدهددر الگوريتم های محلی مسير رسيدن به هدف مهم نيستمثال: مسئله 8 وزيردو امتياز عمده جست و جوهای محلياستفاده از حافظه کمکیارائه راه حلهای منطقي در فضاهای بزرگ و نامتناهیاين الگوريتمها برای حل مسائل بهينه سازی نيز مفيدنديافتن بهترين حالت بر اساس تابع هدف

اسلاید 110: 110جست و جوی آگاهانه و اکتشافالگوريتم های جست و جوی محلی و بهينه سازی

اسلاید 111: 111جست و جوی تپه نوردیجست و جوی آگاهانه و اکتشافحلقه اي که در جهت افزايش مقدار حرکت ميکند(بطرف بالای تپه)رسيدن به بلندترين قله در همسايگی حالت فعلی، شرط خاتمه است.ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه ميداردجست و جوی محلی حريصانه نيز نام داردبدون فکر قبلي حالت همسايه خوبي را انتخاب ميکندتپه نوردی به دلايل زير ميتواند متوقف شود:بيشينه محليبرآمدگي هافلات

اسلاید 112: 112جست و جوی آگاهانه و اکتشافانواع تپه نوردی:تپه نوردی غيرقطعی، تپه نوردی اولين انتخاب، تپه نوردی شروع مجدد تصادفیمثال: مسئله 8 وزيرمسئله 8 وزير با استفاده از فرمولبندی حالت کاملدر هر حالت 8 وزير در صفحه قرار دارندتابع جانشين: انتقال يک وزير به مربع ديگر در همان ستونتابع اکتشاف: جفت وزيرهايي که نسبت به هم گارد دارندمستقيم يا غير مستقيمجست و جوی تپه نوردی

اسلاید 113: 113جست و جوی آگاهانه و اکتشافمثال جست و جوی تپه نوردیالف- حالت با هزينه h=17 که مقدار h را برای هر جانشين نشان ميدهدب- کمينه محلی در فضای حالت 8 وزير؛ h=1الفب

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

اسلاید 115: 115جست و جوی آگاهانه و اکتشافجست و جوی پرتو محليبه جای يک حالت، k حالت را نگهداری ميکندحالت اوليه: k حالت تصادفیگام بعد: جانشين همه k حالت توليد ميشوداگر يکي از جانشين ها هدف بود، تمام ميشودوگر نه بهترين جانشين را انتخاب کرده، تکرار ميکندتفاوت عمده با جستجوی شروع مجدد تصادفیدر جست و جوی شروع مجدد تصادفی، هر فرايند مستقل از بقيه اجرا ميشوددر جست و جوی پرتو محلی، اطلاعات مفيدی بين k فرايند موازی مبادله ميشودجست و جوی پرتو غيرقطعیبه جای انتخاب بهترين k از جانشينها، k جانشين تصادفی را بطوريکه احتمال انتخاب يکي تابعی صعودی از مقدارش باشد، انتخاب ميکند

اسلاید 116: 116جست و جوی آگاهانه و اکتشافالگوريتم های ژنتيکشکلی از جست و جوی پرتو غير قطعی که حالتهای جانشين از طريق ترکيب دو حالت والد توليد ميشود

اسلاید 117: 117الگوريتم های ژنتيکجست و جوی آگاهانه و اکتشافجهت اوليهتابع برازشانتخابتقاطعجهش

اسلاید 118: 118جست و جوی آگاهانه و اکتشافجست و جوی محلی در فضاهای پيوستهگسسته در مقابل محيط های پيوستهدر فضاهای پيوسته، تابع جانشين در اغلب موارد، حالتهای نامتناهی را بر ميگرداندحل مسئله:گسسته کردن همسايه هر حالتاستفاده از شيب منظرهروش نيوتن رافسون

اسلاید 119: 119جست و جوی آگاهانه و اکتشافعاملهای جست و جوی Online و محيطهای ناشناختهتا به حال همه الگوريتمها برون خطي بودندبرون خطی(Offline):راه حل قبل از اجرا مشخص استدرون خطی(Online):با يک در ميان کردن محاسبات و فعاليت عمل ميکندجستجوی درون خطی در محيطهای پويا و نيمه پويا مفيد استآنچه را که بايد واقعا اتفاق بيفتد، در نظر گرفته نميشودجست و جوی درون خطی ايده ضروری برای مسئله اکتشاف استفعاليتها و حالتها برای عامل مشخص نيستندمثال:قرار گرفتن روبات در محيطي جديد, نوزاد تازه بدنيا آمده

اسلاید 120: 120جست و جوی آگاهانه و اکتشافمسئله های جست و جوی Onlineاطلاعات عاملActions(s): ليستی از فعاليتهای مجاز در حالت sتابع هزينه مرحله ای c(s,a,s’): استفاده وقتی که بداند s’ نتيجه استGoal-Test(s): آزمون هدفعامل حالت ملاقات شده قبلی را تشخيص ميدهدفعاليتها قطعی انددسترسی به تابع اکتشافی قابل قبول h(s)

اسلاید 121: 121جست و جوی آگاهانه و اکتشافمسئله های جست و جوی Online هدف: رسيدن به G با کمترين هزينههزينه: مجموع هزينه های مراحل مسيری است که عامل طی ميکندنسبت رقابتی: مقايسه هزينه با هزينه مسيری که اگر عامل فضای حالت را از قبل ميشناخت، طی ميکرددر بعض موارد، بهترين نسبت رقابتی نامتناهی استممکن است جستجو به يک حالت بن بست برسد که نتوان از طريق آن به هدف رسيد

اسلاید 122: 122جست و جوی آگاهانه و اکتشافمسئله های جست و جوی Onlineدو فضای حالت که عامل جست و جوی Online را به بن بست ميرسانند. هر عاملي حداقل در يکي از اين دو فضا شکست می خورد

اسلاید 123: 123جست و جوی آگاهانه و اکتشافمسئله های جست و جوی Onlineيک محيط دو بعدی که موجب ميشود عامل جست و جویOnline مسير دلخواه ناکارآمدی را برای رسيدن به هدف حل کند