بخشی از پاورپوینت
اسلاید 1 :
هوش مصنوعی
فصل سوم: حل مسئله با جستجو
Solving Problems by Searching
اسلاید 2 :
فهرست
گامهای حل مسئله
عاملهاي حل مسئله
اندازه گيري کارايي حل مسئله
جستجوي ناآگاهانه
اجتناب از حالتهاي تکراري
جستجو با اطلاعات ناقص
اسلاید 3 :
حل مسئله با جستجو
گام های اساسي براي حل مسائل
فرموله کردن هدف: وضعيتهاي مطلوب نهايي کدامند؟
فرموله کردن مسئله: چه فعاليتها و وضعيتهايي براي رسيدن به هدف موجود است؟
جستجو: انتخاب بهترين دنباله از فعاليتهايي که منجر به حالاتي با مقدار شناخته شده ميشود.
اسلاید 4 :
عامل حل مسئله، يک نوع عامل هدفگراميباشد.
عاملهاي هوشمند به طريقي عمل ميکنند که محيط مستقيماً به دنباله حالتهايي وارد شود که معيار کارآرايي را افزايش ميدهند.
الگوريتم جستجو مسئلهاي را به عنوان ورودي دريافت نموده و راهحلي را به صورت دنباله عمليات بر ميگرداند.
عاملهاي حل مسئله (problem solving agents)
اسلاید 5 :
چهار نوع اساسي از مسائل وجود دارند:
مسائل تک حالته (Single-state)
مسائل چند حالته (Multiple-state)
مسائل احتمالي (Contingency)
مسائل اکتشافي (Exploration)
اسلاید 6 :
مدلهاي مختلف براي مسئله جاروبرقي:
- مدل تک حالته:
حسگرهاي عامل به آن اطلاعات کافي ميدهند تا وضعيت دقيق مشخص شود. (دنيا قابل دسترسي است). عامل ميتواند محاسبه کند که کدام وضعيت پس از هر دنباله از عمليات قرار خواهد گرفت.
اسلاید 7 :
- مدل چند حالته:
عامل تمام اثرهاي عملياتش را ميداند اما دسترسي به حالت دنيا محدود است.
زماني که دنيا تماماً قابل دسترسي نيست عامل بايد در مورد مجموعه حالتهايي که ممکن است به آن برسد استدلال کند.
اسلاید 8 :
- مدل احتمالي:
با اين مدل حل مسئله، حسگرهايي را در طول فاز اجرايي نياز داريم. عامل اکنون بايد تمام درخت عملياتي را بر خلاف دنباله عملياتي منفرد، محاسبه کند. که به طور کلي هر شاخه درخت، با يک امکان احتمالي که از آن ناشي ميشود، بررسي ميشود.
اسلاید 9 :
مدل اکتشافي:
عاملي که هيچ اطلاعاتي در مورد اثرات عملياتش ندارد.
در اين حالت، عامل بايد تجربه کند و به تدريج کشف کند که چه عملياتي بايد انجام شود و چه وضعيتهايي وجود دارند. اين روش يک نوع جستجو است.
اگر عامل نجات يابد، «نقشهاي» از محيط را ياد ميگيرد که ميتواند مسائل بعدي را حل کند.
اسلاید 10 :
دنياي مکش:
مسئله تک حالته: عامل از جاي خودش اطلاع دارد و تمام مکانهاي آلوده را ميشناسد و دستگاه مکنده ما درست کار ميکند.
حالات: يکي از 8 حالت نشان داده شده.
عملگرها: حرکت به چپ، حرکت به راست، عمل مکش.
آزمون هدف: هيچ خاکي در چهار گوشها نباشد.
هزينه مسير: هر عمل هزینه1 دارد.
اسلاید 11 :
دنياي مکش (جاروبرقي):(Vacuum cleaner)
اگر دنيا حاوي دو محل باشد:
هر محل ممکن است که شامل خاک باشد و يا
نباشد و عامل ممکن است که در يک محل يا
ديگر محلها باشد؛ که داراي هشت حالت متفاوت خواهد بود. هدف تميز کردن تمام خاکهاست که در اينجا معادل با مجموعه حالت {8و 7} است.
اسلاید 12 :
مسئله چند حالته: عامل داراي حسگر نميباشد.
مجموعه وضعيتها : زير مجموعهاي از حالات.
عملگرها: حرکت به چپ، حرکت به راست، عمل مکش.
آزمون هدف: تمام حالات در مجموعه حالتها فاقد خاک باشند.
هزينه مسير: هر عمل هزينه 1 دارد.
مثال: دنياي جاروبرقي فاقد حسگر
اسلاید 13 :
حل مسئله با جستجو
مثال: دنياي جاروبرقي فاقد حسگر
عامل جارو تمام اثرات فعاليتهايش را ميداند اما فاقد حسگر است.
حالت اوليه آن يکي از اعضاي مجموعه{1،2،3،4،5،6،7،8} ميباشد
فعاليت ((Right {2،4،6،8}
فعاليت (Right,Suck) {4،8}
فعاليت (Right,Suck,Left,Suck) تضمين ميکند که صرف نظر از حالت اوليه، به حالت هدف، يعني 7 برسد
اسلاید 14 :
حل مسئله با جستجو
دنياي جاروبرقي فاقد حسگر
عامل بايد راجع به مجموعه هاي حالتي که ميتواند به آنها برسد استدلال کند. اين مجموعه از حالتها را حالت باور گوييم.
اگر فضاي حالت فيزيکي داراي s حالت باشد فضاي حالت باور 2^s حالت باور خواهد داشت.
اسلاید 15 :
اندازهگيري کارايي حل مسئله:
کارايي يک جستجو، حداقل از سه طريق ميتواند اندازهگيري شود:
آيا اين جستجو راه حلي پيدا ميکند؟
آيا راه حلي مناسبي است؟
هزينه جستجو از نظر زماني و حافظه مورد نياز براي يافتن راه حل چقدر است؟
اسلاید 16 :
حل مسئله با جستجو
مثال: نقشه روماني
اسلاید 17 :
حل مسئله با جستجو
صورت مسأله: رفتن از آراد به بخارست
فرموله کردن هدف: رسيدن به بخارست
فرموله کردن مسئله:
وضعيتها: شهرهاي مختلف
فعاليتها: حرکت بين شهرها
جستجو: دنباله اي از شهرها مثل:آراد، سيبيو، فاگارس، بخارست
اين جستجو با توجه به کم هزينه ترين مسير انتخاب ميشود
مثال: نقشه روماني
اسلاید 18 :
حل مسئله با جستجو
مسئله
حالت اوليه: حالتي که عامل از آن شروع ميکند. (initial state)
در مثال روماني: شهر آراد (Arad)
تابع جانشين: توصيفي از فعاليتهاي ممکن که براي عامل مهيا است. (actions)
در مثال روماني:Zerind,Sibui,Timisoara} S(Arad)={
فضاي حالت: مجموعه اي از حالتها که از حالت اوليه ميتوان به آنها رسيد.(state space)
در مثال روماني: کليه شهرها که با شروع از آراد ميتوان به آنها رسيد
حالت هدف: مجموعه اي از حالتها که در نهایت ميخواهیم به آنها برسيم. (goal state)
اسلاید 19 :
حل مسئله با جستجو
آزمون هدف: تعيين ميکند که آيا یک حالت خاص، حالت هدف است يا خير
هدف صريح: در مثال روماني، رسيدن به بخارست
هدف انتزاعي: در مثال شطرنج، رسيدن به حالت کيش و مات
مسير: دنباله اي از حالتها که دنباله اي از فعاليتها را به هم متصل ميکند.
در مثال روماني: Arad, Sibiu, Fagaras يک مسير است
هزينه مسير: براي هر مسير يک هزينه عددي در نظر ميگيرد.
در مثال روماني: طول مسير بين شهرها بر حسب کيلومتر
راه حل مسئله مسيري از حالت اوليه به حالت هدف است
راه حل بهينه کمترين هزينه مسير را دارد
اسلاید 20 :
براي تعريف يک مسئله به موارد زير نياز داريم:
وضعيت آغازين (initial state) که عامل خودش از بودن در آن آگاه است.
مجموعهاي از عمليات ممکن، که براي عامل قابل دسترسي باشد.
آزمون هدف (goal test)، که عامل ميتواند در يک تعريف وضعيت منفرد آن را تقاضا کند تا تعيين گردد که آن حالت، وضعيت هدف است يا خير.
تابع هزينه مسير، تابعي است که براي هر مسير، هزينهاي را در نظر ميگيرد؛ و با حرف g مشخص ميشود.
هزينه يک سفر= مجموع هزينههاي عمليات اختصاصي در طول مسير
