informatics
electronicsSimilar presentations:
هوش مصنوعی
1. هوش مصنوعی
هوش مصنوعینام مرجع :
Artificial Intelligence A Modern
Approach
نویسنده :
استوارت راسل ،پیتر نورویگ
1
ك تاب دروس تخصصي هوش مصنوعي از سري ك تاب هاي راهيان ارشد ،انتشارات ازاده
هوش مصنوعي ،نوشته بن كوپين ،مترجم داورپناه و ميرزاي ي
2.
هوش مصنوعيفصل اول
مقدمه
2
3.
هوش مصنوعيArtificial Intelligence
فهرست
هوش مصنوعي چيست؟
مباني هوش مصنوعي
تاريخچه هوش مصنوعي
4.
مقدمههوش مصنوعي چيست؟
4
عاقالنه فکر کردن
مانند انسان فکر کردن
عاقالنه عمل کردن
مانند انسان عمل کردن
5.
مقدمهمانند انسان عمل کردن
هنر ساخت ماشينهاي ي که کارهاي ي را انجام ميدهند که ان کارها
Acting humanly
توسط انسان با فکر کردن انجام ميشوند.
ا
مطالعه براي ساخت کامپيوترها براي انجام کارهاي ي که فعال انسان
انها را بهتر انجام ميدهد.
5
6.
مقدمه(مانند انسان عمل کردن)
تست تورينگ
B
A
6
7.
مقدمهمانند انسان فکر کردن
Thinking humanly
تالش جديد و هيجان انگيز براي ساخت ماشين هاي ي متفکر و
با حس کامل
خودکارسازي فعاليت هاي مرتبط با تفکر انسان ،فعاليتهاي ي مثل
تصميم گيري ،حل مسئله ،يادگيري
7
8.
مقدمهعاقالنه فکر کردن
Think rationally
مطالعه تواناي ي هاي ذهني از طريق مدل هاي محاسباتي
(منطق گراي ي)
مطالعه محاسباتي که منجر به درک و استدالل مي شود.
8
9.
مقدمهعاقالنه عمل کردن
Act rationally
طوري عمل کند که بهترين نتيجه را ارائه دهد
هوش محاسباتي ،مطالعه طراحي عامل هاي هوشمند است
9
10.
مقدمهمباني هوش مصنوعي
فلسفه :منطق ،استدالل ،ناشي
شدن تفکر از مغز فيزيکي ،مباني
يادگيري ،زبان و عقالنيت
زبان شناسي :علم
ارائه ،گرامر
10
روان شناسي :تطبيق ،اثر طبيعي
ادراک و تاثير ان بر محيط
رياضيات :نمايش رسمي الگوريتمها،
محاسبات ،تصميم پذيري و تصميم
ناپذيري ،احتمال
11.
مقدمهمباني هوش مصنوعي
نظريه کنترل و سيبرنتيک:
تحت
کنترل در اوردن محصوالت مصنوعي ،ثبات و پايداري،
طراحي عامل بهينه
اقتصاد:
نظريه بازي
11
نظريه تصميمهاي عقالي ي،
علوم عصبي:
نحوه پردازش
اطالعات توسط مغز
مهندسي کامپيوتر:
کامپيوترهاي سريع
ساخت
12.
مقدمهتاريخچه هوش مصنوعي
،1943 مک کولوچ و والتر پيتز :ارايه مدل نرون مصنوعي بيتي( دو حالته) قابل يادگيري به منظور محاسبه هر
تابع قابل محاسبه.
،1950 الن تورينگ اولين بار ديد کاملي از هوش مصنوعي را تحت عنوان “ محاسبات ماشيني و هوشمند” ارايه
نمود.
،1951 هينسکي و ادموندز اولين کامپيوتر شبکه عصبي را طراحی کردند.
،1952 ارتور سامويل :برنامه اي ساخت که ياد ميگرفت بهتر از نويسنده اش بازي کند؛ در نتيجه اين تصور را که
“کامپيوتر فقط کاري را انجام ميدهد که به ان گ فته شود” نقض کرد.
12
13.
مقدمه(تاريخچه هوش مصنوعي)
،1956 نشست کارگروهي دورتموند :انتخاب نام هوش مصنوعي
،1959 هربرت جلونتر :برنامه( )GTPرا ساخت که قضايا را با اصل موضوعات مشخص ثابت مي کرد.
،1958 جان مک کارتي :تعريف زبان ليسپ که بهترين زبان هوش مصنوعي شد.
،1973-1958 جيمز اسالگل :برنامه حل مسايل انتگرالگيري فرم بسته
تام ايوانز :برنامه حل مشابهت هاي هندسي
دانيل بابروز :برنامه حل مسايل جبري
ديويد هافمن :پروژه محدوده بيناي ي روبات در جهان بلوکها
ديويد والتز :سيستم بيناي ي و انتشار محدود
13
پاتريک ونيستون :نظريه يادگيري
14.
مقدمه(تاريخچه هوش مصنوعي)
( )1966-1973کند شدن مسير تحقيقات هوش مصنوعی
پيچيده شدن الگوريتم برنامه های جديد
برنامه ترجمه متون
انجام ناپذيری بسياری از مسائلی که سعی در حل انها بود
عدم موفقيت اثبات قضايا با مفروضات بيشتر
بکارگيری بعضی محدوديتها روی ساختارهای اساسی
محدوديت نمايش پرسپترون دو ورودی
14
15.
مقدمه(تاريخچه هوش مصنوعي)
( )1979 -1969سيستم های مبتنی بر دانش
جست و جوی همه منظوره که سعی بر يادگيری داشت تا پيمودن راه حل کامل
مثل برنامه ،DENDRALبوچانان و همکارانش در سال 1969
• مزيت برنامه DENDRALاين بود که اولين سيستم پاداش غنی بود
متدولوژی جديد سيستم خبره
مثل سيستم MYCINکه برای تشخيص عفونتهای خونی طراحی شد
• استفاده از فاک تورهای قطعيت
افزايش تقاضا برای ِشمای نمايش دانش
استفاده از منطق در پرولوگ ،استفاده از ايده مينسکی يعنی قابها و ...
15
16.
مقدمه(تاريخچه هوش مصنوعي)
1980تا کنون :تبديل هوش مصنوعی به يک صنعت
1986تاکنون :برگشت به شبکه های عصبی
1987تاکنون :هوش مصنوعی به علم تبديل ميشود
1995تاکنون :ظهور عاملهای هوشمند
16
17.
هوش مصنوعيفصل دوم
عاملهاي هوشمند
17
18.
هوش مصنوعيArtificial Intelligence
فهرست
عامل
خواص محيطهای وظيفه
برنامه های عامل
18
19.
عاملهای هوشمندعامل:
به هر چيزي اطالق ميشود ،که قادر به درک محيط پيرامون خود از طريق حسگرها( )sensorو اثرگذاري
بر روي محيط از طريق اثرکنندهها ( )effectorباشد.
عامل نرمافزاري:
عامل نرمافزاري رشتههاي بيتي را به عنوان درک محيط و عمل ،کدگذاري ميکند.
20.
عاملهای هوشمندعوامل انساني
.1
حس کردن :گوش ،چشم ،ديگر ارگانها
.2
اثرگذاري :دست ،پا ،بيني ،اندامهاي ديگر
عوامل روباتيک
.1
حس کردن :دوربين ،يابندههاي مادون قرمز
.2
اثرگذاري :موتور
21.
عاملهای هوشمند دنباله ادراک
سابقه کامل هر چيزی است که عامل تاکنون درک کرده است.
تابع عامل
رفتار عامل توسط تابع عامل توصيف ميشود که هر دنباله ادراک را به يک فعاليت نقش ميکند.
f : P* A
فعاليت
21
دنباله ادراک :تابع عامل
22.
عاملهای هوشمند عامل
ادراک ها
محيط
?
فعاليت ها
22
حسگرها
محرکها
عامل
23.
عاملهای هوشمندعاملها چگونه بايد عمل کنند؟
عامل منطقي :چيزي است که کار درست انجام ميدهد.
عمل درست :ان است که باعث موفقترين عامل گردد.
کاراي ي :چگونگي موفقيت يک عامل را تعيين ميکند.
24.
عاملهای هوشمندان چه در هر زماني منطقي است به چهار چيز وابسته است:
معيار کاراي ي که درجه موفقيت را تعيين ميکند.
هر چيزي که تا کنون عامل ،ادراک نموده است .ما اين تاريخچه کامل ادراکي را دنباله ادراکي ميناميم.
انچه که عامل درباره محيط خود ميداند.
اعمالي که عامل ميتواند صورت دهد.
25.
عاملهای هوشمندرفتار عامل وابسته به دنباله ادراکي تا حال است.
عامل را بايد بهعنوان ابزاري براي تحليل سيستمها قلمداد کرد؛
نه شخصيتي مطلق که جهان را به دو بخش عامل و غيرعاملها تقسيم ميکند.
26.
عاملهای هوشمندخودمختاري:
اگر رفتار عامل هاي تنها مبتني بر دانش دروني باشد و هيچ توجهي به ادراك خود نكند ،انگاه عامل فاقد خود
مختاري خواهد بود .زيرا همواره به يك صورت عمل خواهد كرد.
عامل هوشمند خود مختار بايد قادر باشد كه در دامنه وسيعي از محيط ها موفقيت اميز عمل كند و خود را با
ان منطبق سازد.
سيستم به وسعتي خود مختار است که رفتار ان بر اساس تجربه خودش تعيين ميکند .زماني که عامل فاقد
تجربه و يا کم تجربه استً ،
مسلما تصادفي عمل خواهد کرد ،مگر انکه طرح کمکهاي ي به ان داده باشد.
27.
محيط عاملهای هوشمندارتباط بين عامل و محيط :اعمال بوسيله عامل بر محيط انجام ميشود ،که خود ادراک عامل را مهيا ميسازد.
خواص محيط:
قابل دسترسي در مقابل غير دسترسي (رويت پذير و نيمه رويت پذير)
قطعي در برابر غير قطعي(اتفاقي)
اپيزوديک در مقابل غيراپيزوديک (مرحله اي در مقابل ترتيبي -دوره اي در مقابل غير دوره اي – واقعه اي در مقابل
غير واقعه اي )
ايستا در مقابل پويا
گسسته در مقابل پيوسته
تك عاملي در مقابل چند عاملي
•چند عاملي رقابتي درمقابل چندعاملي همياری
28.
محيط عاملهای هوشمند قابل دسترسي در مقابل غيرقابل دسترسي
محيط قابل دسترسي :محيطي که عامل ان توسط ابزار حسکنندهاش امکان دسترسي به وضعيت کامل محيط را
داشته باشد.
محيط قابل دسترسي راحت است ،زيرا عامل نيازمند دستکاري هيچ وضعيت داخلي براي حفظ دنيا را نخواهد
داشت.
29.
محيط عاملهای هوشمند قطعي در مقابل غير قطعي
محيط قطعي :محيطي است که دقيقا بدانيم در وضعيت كنوني دنيا عامل چه عملي را انتخاب مي كند و انجام مي
دهد ،وضعيت بعدي دنيا چه خواهد بود.
هر چه محيط پيچيده تر باشد احتمال اين كه غيرقطعي باشد بيشتر خواهد بود.
بهتر است به قطعي يا غير قطعي بودن محيط از ديدگاه عامل نگاه کنيم.
30.
محيط عاملهای هوشمند اپيزوديک در مقابل غير اپيزوديک
درمحيط اپيزوديک ( ،)episodicتجربه عامل به مرحله هاي ي تقسيم ميگردد.
هر مرحله شامل درک و عمل عامل است.
کيفيت اعمال ان تنها به خود مرحله وابسته است .و به مرحله هاي قبلي بستگي ندارد.
محيطهاي مرحله اي بسيار سادهترند زيرا عامل نبايد به جلوتر فکر کند.
مثال :راننده تاكسي و شطرنج :ترتيبي
تشخيص قطعات معيوب :مرحله اي
31.
محيط عاملهای هوشمند ايستا در مقابل پويا
محيط پويا :محيطي که در حين سنجيدن عامل تغيير ميکند.
محيط نيمهپويا :محيطي که با گذر زمان تغيير نميکند اما امتياز کاراي ي تغيير ميکند.
(شطرنج ساعتي :انجام عمل عامل به زمان وابسته است اما محيط تغيير نمي كند).
محيطهاي ايستا براي کار ساده هستند زيرا عامل نياز به نگاهکردن به دنيا در حين تصميمگيري عملي نداشته و
همچنين در مورد گذر زمان نيز نگران نميباشد.
32.
محيط عاملهای هوشمند گسسته در مقابل پيوسته
محيط گسسته :اگر تعداد محدود و مجزا از ادراک و اعمال بوضوح تعريف شده باشد.
بازي شطرنج گسسته است. رانندگي تاکسي پيوسته است.سختترين حالت در بين حاالت موجود براي محيط:
غير قابل دسترسي ،غير اپيزوديک ،پويا و پيوسته
33.
محيط عاملهای هوشمندمثالهاي ي از انواع محيط و ويژگيهاي انها
محيط
قابل دسترسي
قطعي
اپيزوديک
ايستا
گسسته
شطرنج به همراه ساعت
YES
YES
NO
Semi
YES
شطرنج بدون ساعت
YES
YES
NO
YES
YES
پوکر
NO
NO
NO
YES
YES
تخته نرد
YES
NO
NO
YES
YES
راندن تاکسي
NO
NO
NO
NO
NO
سيستم تشخيص پزشکي
NO
NO
NO
NO
NO
سيستم تحليل تصوير
YES
YES
YES
Semi
NO
ربات جابجا کننده اشياء
NO
NO
YES
NO
NO
کنترلکننده پااليشگاه
NO
NO
NO
NO
NO
اموزشدهنده انگليسي با ارتباط متقابل
NO
NO
NO
NO
YES
34.
عاملهای هوشمندساختار عاملها
برنامه +معماری = عامل
کار هوش مصنوعی طراحی برنامه عامل است که تابع عامل را پياده سازی ميکند
اين طراحي شامل تابعي است که نگاشت عامل از ادراک به عمليات را پياده سازي ميکند.
معماري :فرض ميکنيم برنامه عامل بر روي نوعي ابزار محاسبهگر اجرا ميگردد که ان را معماري ميناميم.
برنامه عامل ،بايد توسط معماري قابل پذيرش و اجرا باشد.
35.
عاملهای هوشمندبرنامه های عامل
عاملهای واکنشی ساده
عاملهای واکنشی مدل گرا
عاملهای هدف گرا
عاملهای سودمند
عاملهای يادگيرنده
36
36.
عاملهای هوشمندعاملهای واکنشی ساده
اين عاملها فعاليت را بر اساس درک فعلی
و بدون در نظر گرفتن سابقه ادراک ،انتخاب
ميکند
داراي يك مجموعه از قوانين شرط -عمل
38
عامل
جهان چگونه است
محيط
به خاطر حذف سابقه ادراک برنامه عامل
در مقايسه با جدول ان بسيار کوچک است
حسگرها
اکنون چه عملی بايد انجام
دهم
محرکها
قانون
شرط عمل
37.
عاملهای هوشمندمثالي از عامل واکنشی ساده در دنيای جاروبرقي
تصميم گيری ان بر اساس مک ان فعل ی
و ک ثيف بودن ان مکان صورت ميگيرد
در برنام ه عام ل در مقايس ه ب ا ج دول
ان ،تع داد حالته ای ممک ن از 4ب ه 4
کاهش مي يابد
انتخ اب فعالي ت ب ر اس اس موقعي ت)]function REFLEX-VACUUM-AGENT ([location, status
return an action
شرطي:
if status == Dirty then return Suck
If dirty then suck
else if location == A then return Right
else if location == B then return Left
39
38.
عاملهای هوشمندعاملهای واکنشي مدل گرا
حسگرها
عام ل بخش ي از دني اي ي را ک ه فع ا
ميبيند رديابی ميکند
جهان چگونه است
عامل بايد حال ت داخل ي را ذخي ره کن د
که به سابقه ادراک بستگي دارد
در هر وضعيت ,عامل ميتواند توصيف
جديدی از جهان را کسب کند
40
محيط
اس تفاده از دان ش “چگ ونگی عملک رد
جهان” که مدل نام دارد
حالت
جهان چگونه تکامل
می يابد
کار فعاليت چيست
اکنون چه عملی بايد انجام
دهم
محرکها
قانون
شرط عمل
عامل
39.
عاملهای هوشمندعاملهای هدف گرا
حسگرها
اين عامل عاوه بر توص يف حال ت فعل ی ،ب رای
انتخ اب موقعي ت مطل وب نيازمن د اطاع ات ه دف
نيز ميباشد
اي ن ن وم تص ميم گي ری هم واره اين ده را در نظ ر
دارد و با قوانين شرط عمل تفاوت دارد
اي ن ن وم عام ل ک اراي ي چن دانی ن دارد ،ام ا
قابليت انعطاف بيشتری دارد
41
جهان چگونه است
محيط
جس ت و ج و و برنام ه ري زی ،دنبال ه ای از
فعاليتها را برای رسيدن عامل به هدف ،پيدا ميکند
حالت
جهان چگونه تکامل
می يابد
اگر فعاليت Aرا انجام
دهم چه خواهد شد
اکنون چه عملی بايد انجام
دهم
محرکها
کار فعاليت چيست
اهداف
عامل
40.
عاملهای هوشمندعاملهای سودمند
حسگرها
اي ن عام ل ب راي اه داف مش خص ،راه ه ای
مختلف ی دارد ،ک ه راه ح ل بهت ر ب رای عام ل
سودمندتر است.
جهان چگونه است
محيط
ت ابع س ودمندی ،حال ت ي ا دنبال ه ای از حالته ا
را ب ه ي ک ع دد حقيق ی نگاش ت ميکن د ک ه درج ه
رضايت را توصيف ِميکند.
جهان چگونه تکامل
می يابد
اگر فعاليت Aرا انجام
دهم چه خواهد شد
وقت ی اه داف متض اد باش ند ،بعض ی از انه ا
براورده ميشوند
در چنين حالتی چقدر
رضايت دارم
اگ ر هيچي ک از اه داف ب ه ط ور قطع ی قاب ل
حصول نباشند ،احتمال موفقي ت ب ا اهمي ت ه دف
مقايسه ميشود
اکنون چه عملی بايد انجام
دهم
42
حالت
محرکها
کار فعاليت چيست
سودمند
عامل
41.
عاملهای هوشمندعاملهای يادگيرنده
استاندارد کاراي ي
عنصرِِيادگيرنده مسئول ايجاد بهبودها
ِ
حسگرها
تغييرات
عنصر کاراي ي
عنصر يادگيرنده
دانش
اهداف
يادگيری
مولد مسئله مس ئول پيش نهاد فعاليته اي ي اس ت
که منجر به تجربيات اموزنده جديدی ميشود
محيط
منتقد مشخص ميکن د ک ه يادگيرن ده ب ا توج ه ب ه
استانداردهای کاراي ي چگونه عمل ميکند
بازخورد
عنص ر ک اراي ي مس ئول انتخ اب فعاليته ای
خارجی
منتقد
مولد مسئله
43
محرکها
عامل
42.
عاملهای هوشمندتفاوت عاملهاي واکنشي و هدفگرا:
در طراحي عاملهاي واکنشي طراح براي حاالت متفاوت عملي درست را پيش محاسبه ميکند .در عاملهاي
هدفگرا ،عامل ميتواند دانش خود را در مورد چگونگي واکنش بهنگام سازد.
43.
عاملهای هوشمند .1براي عامل واکنشي ما مجبور به دوباره نويسي تعداد زيادي قوانين شرط –عمل خواهيم بود.
.2عامل هدفگرا نسبت به رسيدن به مقاصد متفاوت انعطاف پذير است.
.3بسادگي با تعيين يک هدف تازه ،ميتوانيم عامل هدفگرا را به رفتار تازه برسانيم.
44.
هوش مصنوعيفصل سوم
حل مسئله با جستجو
46
45.
هوش مصنوعيفهرست
47
Artificial Intelligence
عاملهای حل مسئله
مسئله
اندازه گيری کاراي ي حل مسئله
جستجوی نااگاهانه
اجتناب از حالتهای تکراری
جستجو با اطالعات ناقص
46.
حل مسئله با جستجويک نوم عامل هدفگرا ،عامل حل مسئله ناميده ميشود.
عاملهاي حل مسئله توسط يافتن ترتيب عمليات تصميم ميگيرند که چه انجام دهند تا انها را به حالتهاي
مطلوب سوق دهد.
47.
حل مسئله با جستجوعاملهاي حل مسئله
ً
مستقيما به داخل دنباله حالتهاي ي وارد شود که معيار
عاملهاي هوشمند به طريقي عمل ميکنند که محيط
کاراراي ي را افزايش ميدهند.
عمليات به گونهاي سادهسازي ميشوند که عامل قادر باشد تا هدفي را قبول کرده و به ان برسد.
الگوريتم جستجو مسئلهاي را به عنوان ورودي دريافت نموده و راهحلي را به صورت دنباله عمليات بر
ميگرداند.
48.
حل مسئله با جستجوفاز اجراي ي :مرحلهاي است که در ان زمان ،راهحلي پيدا ميشود و عمليات پيشنهادي ميتوانند انجام شوند.
به طور ساده براي طرح يک عامل مراحل «فرمولهسازي ،جستجو ،اجرا» را در نظر ميگيريم.
49.
حل مسئله با جستجوعاملهای حل مسئله
چهار گام اساسي برای حل مسائل
فرموله کردن هدف :وضعيتهای مطلوب نهاي ي کدامند؟
فرموله کردن مسئله :چه فعاليتها و وضعيتهاي ي برای رسيدن به هدف موجود است؟
جستجو :انتخاب بهترين دنباله از فعاليتهاي ي که منجر به حاالتی با مقدار شناخته شده ميشود.
اجرا :وقتی دنباله فعاليت مطلوب پيدا شد ،فعاليتهای پيشنهادی ان ميتواند اجرا شود.
51
50.
حل مسئله با جستجوپس از فرمولهسازي يک هدف و يک مسئله براي حل عامل،
.1رويه جستجوي ي را براي حل ان مسئله فراخواني ميکند.
.2از راه حل براي راهنماي ي عملياتش استفاده ميکند و هرانچه که راه حل پيشنهاد ميکند را
انجام ميدهد.
.3ان مرحله را از دنباله حذف ميکند.
.4زماني که راهحل اجرا شد ،عامل هدف جديدي را پيدا ميکند.
51.
حل مسئله با جستجومسائل و راهحلهاي خوب تعريف شده
مسئله :در واقع مجموعهاي از اطاعات است که عامل از انها براي تصميمگيري در مورد اينکه چه کاري انجام دهد،
استفاده ميکند.
عناصر اوليه تعريف يک مسئله ،وضعيتها عمليات هستند.
52.
حل مسئله با جستجوبراي تعريف يک مسئله موارد زير نياز داريم:
وضعيت اغازين ( )initial stateکه عامل خودش از بودن در ان اگاه است.
مجموعهاي از عمليات ممکن ،که براي عامل قابل دسترسي باشد.
ازمون هدف ( ،)goal testکه عامل ميتواند در يک تعريف وضعيت منفرد ان را تقاضا کند تا تعيين
گردد که ان حالت ،وضعيت هدف است يا خير.
تابع هزينه مسير ،تابعي است که براي هر مسير ،هزينهاي را در نظر ميگيرد؛ و با حرف cمشخص ميشود.
هزينه يک سفر= مجموع هزينههاي عمليات اختصاصي در طول مسير
53.
حل مسئله با جستجوبراي حل مسئله چند حالته ،فقط به يک اصاح جزئي نياز داريم:
يک مسئله شامل:
يک مجموعه حالت اوليه
مجموعهاي از عملگرهاي ويژه براي هر عمل به گونهاي که از هر وضعيت داده شده مجموعهاي حاالت رسيده
شده و يک ازمون هدف و تابع هزينه مسير را معين کند.
54.
حل مسئله با جستجويک عملگر:
توسط اجتمام نتايج اعمال عملگر در هر وضعيت مجموعه ،به کار برده ميشود.
يک مسير:
مجموعه حاالت را مرتبط ميکند.
يک راه حل:
مسيري است که به مجموعهاي از حاالت که تمام انها ،وضعيت هدف هستند ،سوق ميدهند.
55.
حل مسئله با جستجواندازهگيري کاراي ي حل مسئله:
کاراي ي يک جستجو ،حداقل از سه طريق ميتواند اندازهگيري شود:
.1ايا اين جستجو راه حلي پيدا ميکند؟
.2ايا راه حلي مناسبي است؟
.3هزينه جستجو از نظر زماني و حافظه مورد نياز براي يافتن راه حل چيست؟
مجموع هزينه جستجو= هزينه مسير +هزينه جستجو
عامل بايد تصميم بگيرد که چه منابعي را فداي جستجو و چه منابعي را صرف اجرا کند.
56.
حل مسئله با جستجوانتخاب حاالت و عمليات
هنر واقعي حل مسئله ،تصميمگيري در مورد اين است که چه چيزهاي ي در تعريف حاالت و عملگرها بايد به حساب
اورده شوند و چه چيزهاي ي بايد کنار گذاشته شوند.
57.
حل مسئله با جستجوانتزاع:
فرايند حذف جزئيات از يک بارنماي ي انتزام ( )abstractionناميده ميشود.
همانگونه که تعريف را خاصه ميکنيم ميبايست عمليات را نيز خاصه نمائيم.
انتزام به اين دليل مفيد است ،که انجام هر کدام از عمليات اسانتر از مسئله اصلي است.
انتخاب يک انتزام خوب از اين رو شامل حذف تا حد ممکن ميشود تا زماني که عمليات خاصه شده براي انجام
اسان باشند.
58.
حل مسئله با جستجومثال :نقشه رومانی
61
59.
حل مسئله با جستجومثال :نقشه رومانی
صورت مساله :رفتن از اراد به بخارست
فرموله کردن هدف :رسيدن به بخارست
فرموله کردن مسئله:
وضعيتها :شهرهای مختلف
فعاليتها :حرکت بين شهرها
جستجو :دنباله ای از شهرها مثل:اراد ،سيبيو ،فاگارس ،بخارست
62
اين جستجو با توجه به کم هزينه ترين مسير انتخاب ميشود
60.
حل مسئله با جستجو حالت اوليه :حالتی که عامل از ان شروم ميکند.
مسئله
در مثال رومانی :شهر اراد )n(Arad
تابع جانشين :توصيفي از فعاليتهای ممکن که برای عامل مهيا است.
در مثال رومانیS(Arad)={ Zerind,Sibui,Timisoara} :
فضای حالت :مجموعه ای از حالتها که از حالت اوليه ميتوان به انها رسيد.
در مثال رومانی :کليه شهرها که با شروم از اراد ميتوان به انها رسيد
63
تابع جانشين +حالت اوليه = فضای حالت
61.
حل مسئله با جستجو ازمون هدف :تعيين ميکند که ايا حالت خاصی ،حالت هدف است يا خير
هدف صريح :در مثال رومانی ،رسيدن به بخارست
هدف انتزاعی :در مثال شطرنج ،رسيدن به حالت کيش و مات
مسير :دنباله ای از حالتها که دنباله ای از فعاليتها را به هم متصل ميکند.
در مثال رومانی Arad, Sibiu, Fagaras :يک مسير است
هزينه مسير :برای هر مسير يک هزينه عددی در نظر ميگيرد.
در مثال رومانی :طول مسير بين شهرها بر حسب کيلومتر
64
راه حل مسئله مسيری از حالت اوليه به حالت هدف است
راه حل بهينه کمترين هزينه مسير را دارد
62.
حل مسئله با جستجومثال :دنيای جارو برقي
حالته ا :دو مک ان ک ه ه ر ي ک ممک ن اس ت ک ثي ف ي ا تمي ز
باشند.لذا 2 *2^2 = 8حالت در اين جهان وجود دارد
حالت اوليه :هر حالتی ميتواند ب ه عن وان حال ت اولي ه طراح ی
شود
تابع جانشين :حالتهای معتبر از سه عملي ات :راس ت ،چ ،،
مکش
ازمون هدف :تميزی تمام مربعها
هزينه مسير :تعداد مراحل در مسير
65
63.
حل مسئله با جستجومثال :دنيای جارو برقي
حالته ا :دو مک ان ک ه ه ر ي ک ممک ن اس ت ک ثي ف ي ا تمي ز
باشند.لذا 2 *2^2 = 8حالت در اين جهان وجود دارد
حالت اوليه :هر حالتی ميتواند ب ه عن وان حال ت اولي ه طراح ی
شود
تابع جانشين :حالتهای معتبر از سه عملي ات :راس ت ،چ ،،
مکش
ازمون هدف :تميزی تمام مربعها
هزينه مسير :تعداد مراحل در مسير .هر عمل ارزش 1دارد.
66
64.
معماي :8حل مسئله با جستجو
مثال :معمای8
معماي 8نمونهاي است شامل يک صفحة 3*3با 8مربع شماره دار
در يک صفحه خالي.
هر مربع که مجاور خانه خالي است .ميتواند به درون ان خانه برود.
هدف رسيدن به ساختاري است که در سمت راست شکل نشان داده
شده است .نک ته مهم اين است که بجاي اينکه بگوييم «مربع شماره
4را به داخل فضاي خالي حرکت بده» بهتر است بگوييم «فضاي
خالي جايش را با مربع سمت چپش عوض کند».
67
65.
حل مسئله با جستجومثال :معمای8
حالتها :توصيف وضعيت مکان هر 8مربع را در يکي از 9خانة صفحه
مشخص ميکند .براي کاراي ي بيشتر ،بهتر است که فضاهاي خالي نيز ذکر
شود.
عملگرها :فضاي خالي به چ ،،راست ،باال و پائين حرکت کند.
ازمون هدف :وضعيت با ساختار هدف مطابقت ميکند.
هزينه مسير :هر قدم ارزش 1دارد ،بنابراين هزينه مسير همان طول مسير
است.
68
66.
حل مسئله با جستجومثال :مسئله 8وزير
هدف از مسئله 8وزير ،قرار دادن 8وزير بر روي صفحه
شطرنج به صورتي است که هيچ وزيري نتواند به ديگري حمله
کند.
دو نوم بيان رياضي اصلي وجود دارد بيان افزايشي که با
جايگزيني وزيرها ،به صورت يکي يکي کار ميکند و ديگري
بيان وضعيت کامل که با تمام 8وزير روي صفحه شروم
ميکند و انها را حرکت ميدهد.
در اين فرمول ما 64امکان داريم.
69
67.
حل مسئله با جستجومثال :مسئله 8وزير
فرمول بندی افزايشي
حالتها :هر ترتيبي از 0تا 8وزير در صفحه ،يک حالت است
حالت اوليه :هيچ وزيری در صفحه نيست
تابع جانشين :وزيری را به خانه خالی اضافه ميکند
ازم ون ه دف8 :وزي ر در ص فحه وج ود دارن د و ه يچ ک دام ب ه يک ديگر گ ارد
نميگيرند
در اين فرمول بندی بايد 3*10^14دنباله ممکن بررسی
ميشود
70
68.
حل مسئله با جستجومثال :مسئله 8وزير
فرمول بندی حالت کامل
حالته ا :چي دمان nوزي ر ) ،(0≤ n≤ 8بطوريک ه در ه ر س تون از nس تون
سمت چ ،،يک وزير قرار گيرد و هيچ دو وزيری بهم گارد نگيرند
حالت اوليه :با 8وزير در صفحه شروم ميشود
تابع جانشين :وزيری را در سمت چ ،ت رين س تون خ الي ق رار ميده د ،بط وری ک ه
هيچ وزيری ان را گارد ندهد
ازمون هدف8 :وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
اين فرمول بندی فضای حالت را از 3*10^14به 2057
کاهش ميدهد
71
69.
حل مسئله با جستجومثال :مسئله 8وزير
*
فرمول بندی حالت کامل
*
حالته ا :چي دمان nوزي ر ) ،(0≤ n≤ 8بطوريک ه در ه ر س تون از nس تون
سمت چ ،،يک وزير قرار گيرد و هيچ دو وزيری بهم گارد نگيرند
حالت اوليه :با 8وزير در صفحه شروم ميشود
*
*
*
تابع جانشين :وزيری را در سمت چ ،ت رين س تون خ الي ق رار ميده د ،بط وری ک ه
هيچ وزيری ان را گارد ندهد
ازمون هدف8 :وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند
اين فرمول بندی فضای حالت را از 3*10^14به 2057
کاهش ميدهد
72
*
*
*
70.
مسائل دنياي واقعيمسيريابي:
الگوريتمهاي مسير يابي کاربردهاي زيادي دراند ،مانند مسيريابي در شبکههاي کامپيوتري ،سيستمهاي خودکار
مسافرتي و سيستمهاي برنامهنويسي مسافرتي هواي ي.
71.
مسائل دنياي واقعيمسائل فروشنده دوره گرد و تور :
مسئله فروشنده دوره گرد مسئله مشهوري است که در ان هر شهر حداقل يکبار بايد ماقات شود هدف يافتن
کوتاهترين مسير است.
عاوه بر مکان عامل ،هر حالت بايد مجموعه شهرهاي ي را که عامل ماقات کرده ،نگه دارد.
عاوه بر برنامهريزي صفر براي فروشنده دورهگرد ،اين الگوريتمها براي اعمالي نظير برنامهريزي حرکات مته
خوردکار سوراخکننده برد مدار استفاده ميشود.
72.
حل مسئله با جستجواندازه گيری کاراي ي حل مسئله
کامل بودن :ايا الگوريتم تضمين ميکند که در صورت وجود راه حل ،ان را بيابد؟
بهينگي :ايا اين راهبرد ،راه حل بهينه ای را ارائه ميکند.
پيچيدگي زمانی :چقدر طول ميکشد تا راه حل را پيدا کند؟
تعداد گره های توليد شده در اثنای جستجو
پيچيدگی فضا :برای جستجو چقدر حافظه نياز دارد؟
حداک ثر تعداد گره های ذخيره شده در حافظه
75
73.
حل مسئله با جستجواندازه گيری کاراي ي حل مسئله
کامل بودن :ايا الگوريتم تضمين ميکند که در صورت وجود راه حل ،ان را بيابد؟
بهينگي :ايا اين راهبرد ،راه حل بهينه ای را ارائه ميکند.
پيچيدگي زمانی :چقدر طول ميکشد تا راه حل را پيدا کند؟
تعداد گره های توليد شده در اثنای جستجو
پيچيدگی فضا :برای جستجو چقدر حافظه نياز دارد؟
حداک ثر تعداد گره های ذخيره شده در حافظه
76
74.
حل مسئله با جستجوجستجوی نااگاهانه
نااگاهی اين است که الگوريتم هيچ اطاعاتی غير از تعريف مسئله در اختيار ندارد
اين الگوريتمها فقط ميتواند جانشينهاي ي را توليد و هدف را از غير هدف تشخيص دهند
راهبردهاي ي که تشخيص ميدهد يک حالت غير هدف نسبت به گره غير هدف ديگر ،اميد بخش تر است ،جست و جوی اگاهانه
يا جست و جوی اک تشافي ناميده ميشود.
راهبردها
جست و جوی عرضی
جست و جوی هزينه يکنواخت
جست و جوی عمقی
جست و جوی عمقی محدود
جست و جوی عميق کننده تکراری
جست و جوی دو طرفه
77
75.
حل مسئله با جستجوجستجوی عرضی
در اين استراتژي که بسيار سيستماتيک است ،ابتدا گره ريشه ،و سپس تمام گرههاي ديگر گسترش داده
ميشوند.
به عبارت کليتر ،تمام گرههاي عميق ،dقبل از گرههاي عميق d+1گسترش داده ميشوند.
مزايا:جستجوي سطحي ،کامل و بهينه ميباشد زيرا هزينه مسير ،يک تابع کاهشنيابنده از عمق گره است.
معايب:مرتبه زماني ) O(bd+1مي باشد که نماي ي است.
نياز به حافظه زياد.
76.
حل مسئله با جستجوجستجوی عرضی
A
D
C
I
H
Q
79
B
P
G
O
N
F
M
L
E
K
J
77.
حل مسئله با جستجوجستجوی عرضی
کامل بودن :بله
بهينگی :بله (مشروط)
بله (مشروط)
در صورتی بهينه است که هزينه مسير ،تابعی غير نزولی از عمق گره باشد(.مثل وقتي که
فعاليتها هزينه يکسانی دارند)
پيچيدگي زماني:
پيچيدگی فضا:
80
d 1
) O(b
)
d 1
O(b
78.
حل مسئله با جستجوجستجوی هزينه يکنواخت
در اين روش گره اي بسط داده مي شود كه هزينه رسيدن به ان حداقل بوده است.
در اين استراتژي ،در شرايط عمومي ،اولين راه حل ،ارزانترين راه نيز هست.
اگر هزينه مسير توسط تابع ) g(nاندازهگيري شود ،در اين صورت جستجوي سطحي همان جستجوي با هزينه
يکسان است با:
)g(n)=DEPTH(n
79.
حل مسئله با جستجوجستجوی هزينه يکنواخت
اين جستجو گره nرا با کمترين هزينه مسير بسط ميدهد
A
3
1
D
C
I
B
H
Q
82
1
P
G
O
N
F
M
L
E
K
J
80.
حل مسئله با جستجوجستجوی هزينه يکنواخت
کامل بودن :بله
هزينه هر مرحله بزرگ تر يا مساوی يک مقدار ثابت و مثبت ε
در مسير افزايش مي يابد)
باشد(.هزينه مسير با حرکت
بهينگی :بله
هزينه هر مرحله بزرگ تر يا مساوی εباشد
پيچيدگي زماني:
پيچيدگی فضا:
83
)
)
] [C*/
O(b
] [C*/
O(b
81.
حل مسئله با جستجوجستجوی عمقی
اين استراتژي ،يکي از گرهها را در پائينترين سطح درخت بسط ميدهد؛ اما اگر به نتيجه نرسيد ،به سراغ گرههاي ي
در سطوح کم عميقتر ميرود.
مزايا:
اين جستجو ،نياز به حافظه ً
نسبتا کمي فقط براي ذخيره مسير واحدي از ريشه به يک گره برگي ،و گرههاي باقيمانده
بسط داده نشده دارد.
پيچيدگي زماني ) O(bmميباشد .به طوريکه bفاک تور انشعاب فضاي حالت ،و mحداک ثر عمق درخت باشد.
معايب:اگر مسيري را اشتباه طي کند ،هنگام پائين رفتن گير ميکند.
جستجوي عمقي نه کامل و نه بهينه است.
در درختهاي با عمق نامحدود و بزرگ اين استراتژي کار نميکند.
82.
حل مسئله با جستجوجستجوی عمقی
A
D
C
I
B
H
6
G
2
E
F
3
7
Q
P
O
N
M
L
K
5
85
J
4
83.
حل مسئله با جستجوجستجوی عمقی
بودن :خير
بودن:
کاملکامل
اگر زير درخت چ ،عمق نامحدود داشت و فاقد هر گونه راه حل باشد ،جستجو هرگز خاتمه
نمي يابد.
خير
بهينگی:
بهينگي:
m
پيچيدگي زماني:
) O(b
پيچيدگی فضا:
)O(bm
86
84.
حل مسئله با جستجوجستجوی عمقی محدود
اين استراتژي ،براي رهاي ي از دامي که جستجوي عمقي در ان گرفتار ميشد ،از يک برش استفاده ميکند.جستجوي
عمقي محدود شده کامل است اما بهينه نيست.
زمان و پيچيدگي فضاي جستجوي عمقي محدودشده ،مشابه جستجوي عمقي است .اين جستجو پيچيدگي زماني
) O(bLو فضاي ) O(bLرا خواهد داشت ،که Lمحدودة عمق است.
در يک درخت جستجوي نماي يً ،
تقريبا تمام گرهها در سطح پائين هستند ،بنابراين موردي ندارد که سطوح
باالي ي چندين مرتبه بسط داده شوند .تعداد بسطها در يک جستجوي عمقي محدود شده با عمق dو فاک تور
انشعاب bبه قرار زير است:
1+b+b^2+…+b^(d-2)+b^(d-1)+b^d
85.
حل مسئله با جستجوجستجوی عمقی محدود
مسئله درختهای نامحدود ميتواند به وسيله جست و جوی عمقي با عمق محدود Lبهبود يابد
A
D
C
I
H
Q
88
B
P
G
O
N
F
M
L
E
K
J
86.
حل مسئله با جستجوجستجوی عمقی محدود
بودن :خير
بودن:
کاملکامل
اگر L<dو سطحی ترين هدف در خارج از عمق محدود قرار داشته باشد ،اين
راهبرد کامل نخواهد بود.
خير
بهينگی:
بهينگي:
اگر L<dانتخاب شود ،اين راهبرد بهينه نخواهد بود.
L
پيچيدگي زماني:
) O(b
پيچيدگی فضا:
)O(bL
89
87.
حل مسئله با جستجوجستجوی عميق کننده تکراري
قسمت دشوار جستجوي عمقي محدود شده ،انتخاب يک محدودة خوب است.
اگر محدودة عمق بهتري را پيدا کنيم ،اين محدوده ،ما را به سوي جستجوي کاراتري سوق ميدهد .اما براي بيشتر مسائل ،محدودة
عمقي مناسب را تا زماني که مسئله حل نشده است ،نميشناسيم.
جستجوي عميقکنندة تکراري استراتژي است که نظريه انتخاب بهترين محدودة عمقي ،توسط امتحان تمام محدودة مسيرهاي ممکن را
ياداوري ميکند.
مزايا:
ترکيبي از مزاياي جستجوي سطحي و عمقي را دارد.
اين جستجو مانند جستجوي سطحي کامل و بهينه است ،اما فقط مزيت درخواست حافظه اندک را از جستجوي عمقي دارد.
مرتبه بسط حاالت مشابه جستجوي سطحي است ،به جز اينکه بعضي حاالت چند بار بسط داده ميشوند.
88.
حل مسئله با جستجودر جستجوي عميقکننده تکراري ،گرههاي سطوح پائيني يک بار بسط داده ميشوند ،انهاي ي که يک سطح باالتر
قرار دارند دوبار بسط داده ميشوند و الياخر تا به ريشه درخت جستجو برسد ،که d+1بار بسط داده ميشوند.
بنابراين مجموم دفعات بسط در اين جستجو عبارتست از:
(d+1)1+(d)b+(d-1)b2+…+3bd-2+2bd-1+1bd
پيچيدگي زماني اين جستجو هنوز ) O(bdاست ،و پيچيدگي فضا ) O(bdاست.
در حالت کلي ،عميقکننده تکراري ،روش جستجوي برتري است؛ زماني که فضاي جستجوي بزرگي وجود دارد و
عمق راه حل نيز مجهول است.
89.
حل مسئله با جستجوجستجوی عميق کننده تکراري
A
D
C
I
H
Q
92
B
P
G
O
N
F
M
L
E
K
J
90.
حل مسئله با جستجوجستجوی عميق کننده تکراري
A
D
C
I
H
Q
93
B
P
G
O
N
F
M
L
E
K
J
91.
حل مسئله با جستجوجستجوی عميق کننده تکراري
A
D
C
I
S
94
B
H
R
Q
P
G
O
N
F
M
L
E
K
J
92.
حل مسئله با جستجوجستجوی عميق کننده تکراري
بودن :بله
بودن:
کاملکامل
در صورتی که فاک تور انشعاب محدود باشد
بهينگی:
بهينگيبله:
وقتی که هزينه مسير ،تابعی غير نزولی از عمق گره باشد
d
پيچيدگي زماني:
) O(b
پيچيدگی فضا:
)O(bd
95
93.
حل مسئله با جستجونك ته :پيچيدگي زماني اين جستجو هنوز ) O(bd/2است ،اگر ازمون اشتراك بوسيله الگوريتم
هاي hashبا ) O(1باشد.
در صورتي كه ازمون اشتراك ) O(nباشد ،پيچيدگي زماني ) O(bdخواهد بود ،زيرا به ازاي
تعداد گره هاي هر سطح كه bnمي باشد ،بايد ازمون اشتراك صورت گيرد.
94.
حل مسئله با جستجوجستجوی دو طرفه
انجام دو جست و جوی همزمان ،يکي از حالت اوليه به هدف و ديگری از هدف به حالت اوليه تا زمانی که دو
جست و جو به هم برسند
97
95.
حل مسئله با جستجوجستجوی دو طرفه
بودن :بله
بودن:
کاملکامل
اگر هر دو جستجو ،عرضی باشند و هزينه تمام مراحل يکسان باشد
بهينگی:
بهينگيبله:
اگر هر دو جستجو ،عرضی باشند و هزينه تمام مراحل يکسان باشد
پيچيدگي زماني:
پيچيدگی فضا:
98
d/2
) O(b
d/2
) O(b
96.
حل مسئله با جستجو:مقايسه استراتژيهاي جستجو
. محدوديت عمق استl ، ماکزيمم عمق درخت جستجوm ، عمل پاسخd ، فاک تور انشعابb .ارزيابي استراتژيهاي جستجو
Criterion
BreadthFirst
UniformCost
DepthFirst
DepthLimited
Iterative
Deepening
Bidirectional (if
applicable)
Time
bd
bd
bm
bl
bd
bd/2
Space
bd
bd
bm
bl
bd
bd/2
Optimal?
Yes
Yes
No
No
Yes
Yes
Complete
Yes
Yes
No
Yes, if
Yes
Yes
l d
97.
حل مسئله با جستجواجتناب از حالتهای تکراری
وجود حالتهای تکراری در يک مسئله قابل حل ،ميتواند ان را به مسئله غير قابل حل تبديل کند
100
98.
حل مسئله با جستجوجستجو با اطالعات ناقص
مسئله های فاقد حسگر :اگر عامل فاقد حسگر باشد ،ميتواند در يکي از چند حالت اوليه باشد و هر فعاليت ميتواند
ان را به يکي از چند حالت جانشين ببرد
مسئله های اقتضاي ي :اگر محيط به طور جزئی قابل مشاهده باشد يا اگر فعاليتها قطعي نباشد ،ادراکات عامل ،پس
از هر عمل ،اطاعات جديدي را تهيه ميکنند .هر ادراک ممکن ،اقتضاي ی را تعريف ميکند که بايد برای ان برنامه ريزی شود
مسائل خصمانه :اگرعدم قطعيت در اثر فعاليتهای عامل ديگری بوجود ايد ،مسئله را خصمانه گويند
مسئله های اک تشافی :وقتی حالتها و فعاليتهای محيط ناشناخته باشند ،عامل بايد سعي کند انها را کشف کند .مسئله
های اک تشافی را ميتوان شکل نهاي ی مسئله های اقتضاي ي دانست
101
99.
حل مسئله با جستجومثال :دنيای جاروبرقی فاقد حسگر
عام ل ج ارو تم ام اث رات فعاليته ايش را ميدان د ام ا فاق د حس گر
است.
حال ت اولي ه ان يک ي از اعض ای مجموع ه{}1،2،3،4،5،6،7،8
ميباشد
فعاليت ((Right
فعاليت ()Right,Suck
{}2،4،6،8
{}4،8
فعالي ت ( )Right,Suck,Left,Suckتض مين ميکن د
که صرف نظر از حالت اوليه ،به حالت هدف ،يعنی 7برسد
102
100.
حل مسئله با جستجودنيای جاروبرقی فاقد
حسگر
عام ل باي د راج ع ب ه مجموع ه ه اي ح التی
ک ه ميتوان د ب ه انه ا برس د اس تدالل کن د .اي ن
مجموعه از حالتها را حالت باور گوييم.
اگ ر فض ای حال ت فيزيک ي دارای sحال ت
باش د فض ای حال ت ب اور 2^sحال ت ب اور
خواهد داشت.
103
101.
هوش مصنوعيفصل چهارم
جست و جوی اگاهانه و اک تشاف
104
102.
هوش مصنوعيفهرست
Artificial Intelligence
متدهای جست و جوی اگاهانه
يادگيری برای جست و جوی بهتر
جست و جوی محلی و بهينه سازی
جست و جوی محلی در فضاهای پيوسته
عاملهای جست و جوی Online
105
103.
جست و جوی اگاهانه و اک تشافمتدهای جستجوی اگاهانه
بهترين جستجو
حريصانه
A*
IDA*
RBFS
MA* و*SMA
106
جستجوی محلی
تپه نوردی
شبيه سازی حرارت
پرتو محلی
الگوريتمهای ژنتيک
و بهينه سازی
104.
جستجوي بهترين:اين استراتژي به اين صورت بيان ميشود که در يک درخت ،زماني که گرهها مرتب ميشوند ،گرهاي که بهترين
ارزيابي را داشته باشد ،قبل از ديگر گرهها بسط داده ميشود.
هدف :يافتن راهحلهاي کمهزينه است ،اين الگوريتمها ً
عموما از تعدادي معيار تخمين براي هزينه راهحلها
استفاده ميکنند و سعي بر حداقل کردن انها دارند.
105.
حداقل هزينه تخمين زده شده براي رسيدن به هدف :جستجوي حريصانهيکي از سادهترين استراتژيهاي جستجوي بهترين ،به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف
است .بدين صورت که حالت گرهاي که به حالت هدف نزديکتر است ،ابتدا بسط داده ميشود.
تابع کشفکننده :هزينه رسيدن به هدف از يک حالت ويژه ميتواند تخمين زده شود اما ً
دقيقا تعيين نميشود.
تابعي که چنين هزينههاي ي را محاسبه ميکند تابع کشفکننده hناميده ميشود.
جستجوي حريصانه :جستجوي بهترين که hرا به منظور انتخاب گره بعدي براي بسط استفاده ميکند ،جستجوي
حريصانه ) (greedy searchناميده ميشود.
106.
ويژگيهاي جستجوي حريصانه: جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف ،مانند جستجوي عمقي است ،اما زماني که
به بنبست ميرسد ،برميگردد.
اين جستجو بهينه نيست و ناکامل است.
پيچيدگي زماني در بدترين حالت براي جستجوي حريصانه ) ،O(bmکه mحداک ثر عمق فضاي جستجو است.
جستجوي حريصانه تمام گرهها را در حافظه نگه ميدارد ،بنابراين پيچيدگي فضاي ان مشابه پيچيدگي زماني ان است.
ميزان کاهش پيچيدگي به مسئله و کيفيت تابع hبستگي دارد.
107.
جست و جوی اگاهانه و اک تشافتعاريف
تابع هزينه مسير : g(n) ،هزينه مسير از گره اوليه تا گره n
تابع اک تشافی : h(n) ،هزينه تخمينی ارزان ترين مسير از گره nبه گره هدف
تابع بهترين مسير : h*(n) ،ارزان ترين مسير از گره nتا گره هدف
تابع ارزيابي : f(n) ،هزينه تخمينی ارزان ترين مسير از طريق n
)f(n): g(n) + h(n
: f*(n) هزينه ارزان ترين مسير از طريقn
110
)f*(n): g(n) + h*(n
108.
جست و جوی اگاهانه و اک تشافجستجوی حريصانه
A
1
2
3
B
C
1
1
2
G
3
3
3
Z
111
1
3
F
1
1
O
2
Y
2
2
N
2
1
M
L 3
K
1
2
3
V
U
1
X
0
W
1
2
5
E
2
1
1
2
3
1
D
3
1
I 3
3
2
3
2
T
S
2
R
2
Q
1
J
0
1
3
1
H
2
3
P
3
109.
جست و جوی اگاهانه و اک تشافجستجوی حريصانه
A
2
2
3
1
C
1
1
23
3
O
F
1
1
4
N
5
112
3
G
3
B
1
X
0
2
3
1
1
1
5
E
D
110.
جست و جوی اگاهانه و اک تشافجستجوی حريصانه
A
1
4
2
B
C
1
1
3
G
3
3
3
Z
113
1
3
F
1
1
O
2
Y
2
2
N
2
1
M
L 3
K
1
2
3
V
U
1
X
0
W
1
2
5
E
3
1
1
1
1
1
D
3
1
I 3
3
2
3
2
T
S
2
R
2
Q
1
J
0
1
3
1
H
2
3
P
3
111.
جست و جوی اگاهانه و اک تشافجستجوی حريصانه
A
1
4
2
1
1 B
C
2
3
0
114
1
1
3
K
1
5
D
E
3
J
1
112.
جست و جوی اگاهانه و اک تشافجستجوی حريصانه
کامل بودن :خير
اما اگر * h = hانگاه جستجو کامل ميشود
بهينگی :خير
اما اگر * h = hانگاه جستجو کامل ميشود
پيچيدگي زماني:
) O(b m
اما اگر * h = hانگاه
) O(bd
) O(b m
پيچيدگی فضا:
) O(bd
اما اگر * h = hانگاه
115
113.
جست و جوی اگاهانه و اک تشافA* جستجوی
A/5
2
1
B/4
1
C/4
1
1
D/5
1
H/2
3
P/3
E/1
3
3
2
3
Q/1
R/2
2
S/2
F/3
3
J/1
I/3
1
K/0
3
T/1
1
L/3
3
U/1
G/2
2
1
M/2
N/1
2
1
1
V/2
W/1
X/0
3
O/3
2
Y/2
3
Z/1
116
114.
جست و جوی اگاهانه و اک تشافجستجوی *A
A/5
1
51
6
C/4
8
3
G/2
1
N/1 4
1
X/0
117
5
F/3
3
O/3
B/4
1
1
42
2
4
115.
جست و جوی اگاهانه و اک تشافA* جستجوی
A/5
2
1
B/1
1
C/4
1
1
D/5
1
H/2
3
P/3
E/1
3
3
2
3
Q/1
R/2
2
S/2
F/3
3
J/1
I/3
1
K/0
3
T/1
1
L/3
3
U/1
G/2
2
1
M/2
N/1
2
1
1
V/2
W/1
X/0
3
O/3
2
Y/2
3
Z/1
118
116.
جست و جوی اگاهانه و اک تشافجستجوی *A
A/5
1
53
8
3
1
5
F/3
G/2
1
2
4
3
O/3
N/1 4
X/0
4
1
1
8
D/5
E/1
3
5
1
119
3B/1
C/4
1
44
2
1
K/0 6
J/1
7
117.
جست و جوی اگاهانه و اک تشافA* جستجوی
A/5
2
1
B/1
1
C/9
1
1
D/5
1
H/2
3
P/3
E/1
3
3
2
3
Q/1
R/2
2
S/2
F/3
3
J/1
I/3
1
K/0
3
T/1
1
L/3
3
U/1
G/2
2
1
M/2
N/1
2
1
1
V/2
W/1
X/0
3
O/3
2
Y/2
3
Z/1
120
118.
جست و جوی اگاهانه و اک تشافجستجوی *A
A/5
1
10
2
B/1
3
C/9
2
4
3
K/0
6
121
1
1
8
E/1
3
1
D/5
3
J/1
7
119.
جست و جوی اگاهانه و اک تشافجستجوی *A
کامل بودن :بله
بهينگی :بله
پيچيدگي زماني:
پيچيدگی فضا:
122
) O(b m
) O(b m
120.
رفتار جستجوي *Aنگاهي گذرا به اثبات کامل و بهينه بودن *:A
مشاهده مقدماتي:
ً
تقريبا تمام کشفکنندگيهاي مجاز داراي اين ويژگي هستند که در طول هر مسيري از ريشه ،هزينه fهرگز کاهش
پيدا نميکند.
اين خاصيت براي کشفکنندگي ،خاصيت يکنواي ي ) (monotonicityگ فته ميشود.
اگر يکنوا نباشد ،با ايجاد يک اصاح جزئي ان را يکنوا ميکنيم.
121.
بنابراين هر گره جديدي که توليد ميشود ،بايد کنترل کنيم که ايا هزينة fاين گره از هزينه fپدرش کمتر است ياخير .اگر کمتر باشد ،هزينة fپدر به جاي فرزند مينشيند:
بنابراين:
fهميشه در طول هر مسيري از ريشه غيرکاهشي خواهد بود ،مشروط بر اينکه hامکانپذير باشد.
122.
) :h*(nهزينه واقعي رسيدن از nبه هدف است.در استفاده عملي ،خطاها با هزينه مسير متناسب هستند ،و سرانجام رشد نماي ي هر کامپيوتر را تسخير ميکند.
البته ،استفاده از يک کشفکنندگي خوب هنوز باعث صرفهجوي ي زيادي نسبت به جستجوي نااگاهانه ميشود.
ً
معموال قبل از اينکه دچار کمبود زمان شود ،دچار کمبود فضا ميشود .زيرا اين جستجو تمام گرههاي توليد
*A
شده را در حافظه ذخيره ميکند.
123.
جست و جوی اگاهانه و اک تشافجستجوی *A
A
1
C 4
1
0
A
1
1
3 B
1
C 2
1
1 B
1
E 1
2 D
E 1
1 D
1
1
1
1
G
1 F
0
G
1
h126
*≤/ h
1
1 F
1
0 H
0 H
*h ≤ h
124.
جست و جوی اگاهانه و اک تشافA* جستجوی
A
1
1
1
2
1
3
1
B
1
D
1
F
A
1
3
3
C 2
5
E
6
1
2
2
1
1
G
1
3
0
1
1
1
B
1
D
1
F
h ≤ h*
C 4
1
E 1
1
G
0
1
4
0 H
0 H
1
h127
≤/ h*
125.
جست و جوی اگاهانه و اک تشافجستجوی * Aو اجتناب از گره های تکراری
A/100
10
D/90
I/87
V/83
C/95
M/75
U/81
P/79
T/60
O/78
X/58
G/90
W/52
Z/50
هزينه هر مرحله 10ميباشد
128
B/80
R/20
L/80
F/78
K/85
N/72
Y/47
Q/0
E/86
T/60
X/58
Z/50
M/75
S/70
W/52
Y/47
P/79
O/78
J/82
H/80
126.
جست و جوی اگاهانه و اک تشافجستجوی * Aو اجتناب از گره های تکراری
A/100
8
3
100 D/90
105 C/95
B/80 90
I/87 107
T/60 80
F/78 98
G/90 110
5
P/79
O/78
109
108
88 X/58
N/72 102
82 W/52
6
T/60 100
9
Z/50 90
87 Y/47
S/70 110
7
129
2
4
95 M/75
1
R/20
Q/0
70
50
10
X/58 108
Z/50 110
102 W/52
107 Y/47
M/75 105
106 E/86
127.
جست و جوی اگاهانه و اک تشافمثال ديگر از جستجوی *A
)f(n)=g(n) + h(n
130
128.
جست و جوی اگاهانه و اک تشافجستجوی * Aدر نقشه رومانی
جستجوی Bucharestبا شروع از Arad
f(Arad) = g(Arad)+h(Arad)=0+366=366
131
129.
جست و جوی اگاهانه و اک تشافجستجوی * Aدر نقشه رومانی
ََ Aradرا باز کرده و ) f(nرا برای هر يک از زيربرگها محاسبه ميکنيم:
f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393
f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447
f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449
بهترين انتخاب شهر Sibiuاست
132
130.
جست و جوی اگاهانه و اک تشاف در نقشه رومانیA* جستجوی
: را برای هر يک از زيربرگها محاسبه ميکنيمf(n) را باز کرده وSibiuََ
f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646
f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415
f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671
f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413
استRimnicu Vilcea بهترين انتخاب شهر
133
131.
جست و جوی اگاهانه و اک تشاف در نقشه رومانیA* جستجوی
: را برای هر يک از زيربرگها محاسبه ميکنيمf(n) را باز کرده وRimnicu Vilceaََ
f(Craiova)=c(Rimnicu Vilcea, Craiova)+h(Craiova)=360+160=526
f(Pitesti)=c(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417
f(Sibiu)=c(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553
استFagaras بهترين انتخاب شهر
134
132.
جست و جوی اگاهانه و اک تشافجستجوی * Aدر نقشه رومانی
ََ Fagarasرا باز کرده و ) f(nرا برای هر يک از زيربرگها محاسبه ميکنيم:
f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591
f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450
135
بهترين انتخاب شهر !!! Pitestiاست
133.
جست و جوی اگاهانه و اک تشافجستجوی * Aدر نقشه رومانی
ََ Pitestiرا باز کرده و ) f(nرا برای هر يک از زيربرگها محاسبه ميکنيم:
f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418
136
بهترين انتخاب شهر !!! Bucharestاست
134.
جست و جوی اگاهانه و اک تشافجستجوی * Aدر نقشه رومانی
137
135.
رفتار جستجوي *Aنگاهي گذرا به اثبات کامل و بهينه بودن *:A
مشاهده مقدماتي:
ً
تقريبا تمام کشفکنندگيهاي مجاز داراي اين ويژگي هستند که در طول هر مسيري از ريشه ،هزينه fهرگز کاهش
پيدا نميکند(.يعني fفرزندان بايد بيشتر از fپدر باشد).
اين خاصيت براي کشفکنندگي ،خاصيت يکنواي ي ) (monotonicityگ فته ميشود.
اگر يکنوا نباشد ،با ايجاد يک اصاح جزئي ان را يکنوا ميکنيم.
136.
بنابراين هر گره جديدي که توليد ميشود ،بايد کنترل کنيم که ايا هزينة fاين گره از هزينه fپدرش کمتر است ياخير .اگر کمتر باشد ،هزينة fپدر به جاي فرزند مينشيند:
بنابراين:
* Aبهينه و كامل است اگر
*h ≤ h
137.
نك ته :1اگر خطاي تابع هيوريستيك كمتر از لگاريتم هزينه مسير واقعي باشد يعني))| h(n)-h*(n) |≤ O(log h*(n
انگاه تعداد گره هاي ي كه در كانتور هدف قرار مي گيرند ،نسبت به طول راه حل مرتبه نماي ي نخواهند داشت.
ً
معموال قبل از اينکه دچار کمبود زمان شود ،دچار کمبود فضا ميشود .زيرا اين جستجو تمام
نك ته A* :2
گرههاي توليد شده را در حافظه ذخيره ميکند.به همين دليل در بسياري از مسايل بزرگ ،عملي نيست.
138.
جست و جوی اگاهانه و اک تشافجستجوی اک تشافی با حافظه محدود *IDA
س اده ت رين راه ب رای ک اهش حافظ ه م ورد ني از * Aاس تفاده از عمي ق کنن ده تک رار در زمين ه جس ت و ج وی
اک تشافي است.
الگوريتم عميق کننده تکرار *A
*IDA
در جستجوی * IDAمقدار برش مورد استفاده ،عمق نيست بلکه هزينه ماکزيمم ) f(g+hاست.
IDA* ب رای اغل ب مس ئله ه ای ب ا هزين ه ه ای مرحل ه ای ،مناس ب اس ت و از س ربار ناش ي از نگه داری ص ف
مرتبي از گره ها اجتناب ميکند
141
139.
جست و جوی اگاهانه و اک تشافبهترين جستجوی بازگشتي RBFS
س اختار ان ش بيه جس ت و ج وی عمق ي بازگش تي اس ت ،ام ا ب ه ج ای اينک ه دائم ا ب ه ط رف پ ايين مس ير حرک ت
کند ،مقدار fمربوط به بهترين مسير از هر جد گره فعلی را نگهداری ميکند ،اگر گره فعلی از اين حد تجاوز کن د،
بازگشتی به عقب برميگردد تا مسير ديگري را انتخاب کند.
اين جستجو اگر تابع اک تشافی قابل قبولی داشته باشد ،بهينه است.
پيچيدگي فضاي ي ان ) O(bdاست
تعيين پيچيدگی زمانی ان به دقت تابع اک تشافی و ميزان تغيير بهترين مسير در اثر بسط گره ها بستگی دارد.
142
140.
جست و جوی اگاهانه و اک تشافبهترين جستجوی بازگشتي RBFS
RBFS تا حدی از * IDAکارامدتر است ،اما گره های زيادی توليد ميکند.
IDA* و RBFSدر مع رض اف زايش ت واني پيچي دگي ق رار دارن د ک ه در جس ت و ج وی گرافه ا مرس وم
است ،زيرا نميتوانند حالتهای تکراری را در غير از مسير فعلي بررسي کنند .لذا ،ممکن است يک حالت را چندين
بار بررسي کنند.
IDA* و RBFSاز فض ای ان دکي اس تفاده ميکنن د ک ه ب ه انه ا اس يب ميرس اند IDA* .ب ين ه ر تک رار
فقط يک عدد را نگهداری ميکند که فعلي هزينه fاست RBFS .اطاعات بيشتری در حافظه نگهداری ميکند
143
141.
بهترين جستجوی بازگشتي RBFS142.
جست و جوی اگاهانه و اک تشافبهترين جستجوی بازگشتي در نقشه رومانی
145
143.
جست و جوی اگاهانه و اک تشافبهترين جستجوی بازگشتي در نقشه رومانی
146
144. بهترين جستجوی بازگشتي RBFS
جست و جوی اگاهانه و اک تشافبهترين جستجوی بازگشتي در نقشه رومانی
147
145.
جست و جوی اگاهانه و اک تشافيادگيری برای جست و جوی بهتر
روشهای جست و جوی قبلي ،از روشهای ثابت استفاده ميکردند.
عامل با استفاده از فضای حالت فراسطحی ميتواند ياد بگيرد که بهتر جست و جو کند
ه ر حال ت در فض ای حال ت ف را س طحی ،حال ت(محاس باتی) داخل ِی برنام ه ای را تس خير ميکن د ک ه فض ای
حالت سطح شیء ،مثل رومانی را جست و جو ميکند
الگ وريتم ي ادگيری فراس طحی ميتوان د چيزه اي ي را از تجربي ات بي اموزد ت ا زيردرخته ای غي ر قاب ل قب ول را
کاوش نکند.
هدف يادگيری ،کمينه کردن کل هزينه ،حل مسئله است
148
146.
جست و جوی اگاهانه و اک تشافتوابع اک تشافی
مثال برای معمای8
149
ميان ِگين هزينه حل تقريبا 22مرحله و فاک تور انشعاب در حدود 3است.
جست و جوی جامع تا عمق : 22
322 3.1 1010
با انتخاب يک تابع اک تشافی مناسب ميتوان مراحل جستجو را کاهش داد
147.
جست و جوی اگاهانه و اک تشافدو روش اک تشافي متداول برای معمای8
تعداد کاشيها در مکانهای نادرست
در حالت شروع
h1
h1 8
h1اک تش اف قاب ل قب ولی اس ت ،زي را ه ر کاش ي ک ه در
ج ای نامناس بی ق رار دارد ،ح داقل يکب ار باي د جابج ا
شود
150
148.
جست و جوی اگاهانه و اک تشافدو روش اک تشافي متداول برای معمای8
مجموعه فواصل کاشيها از موقعيتهای هدف انها
در حالت شروع
h2
h2 3 1 2 2 2 3 3 2 18
چون کاشيها نميتوانند در امتداد قطر جا به جا ش وند ,فاص له ای ک ه
محاسبه ميکنيم مجموم فواصل افقی و عمودی اس ت .اي ن فاص له را
فاصله بلوک شهر مينامند.
151
149.
جست و جوی اگاهانه و اک تشافدو روش اک تشافي متداول برای معمای8
مجموعه فواصل کاشيها از موقعيتهای هدف انها
h2
h2قابل قب ول اس ت ،زي را ه ر جابج اي ي ک ه ميتوان د انج ام گي رد ،ب ه
اندازه يک مرحله به هدف نزديک ميشود.
هيچ کدام از اين براوردها ،هزينه واقعی راه حل نيست
هزينه واقعي 36است
152
150.
جست و جوی اگاهانه و اک تشافاثر دقت اک تشاف بر کاراي ي
فاک تور انشعاب مؤثر *b
اگر تعداد گره هاي ي که برای يک مسئله خاص توسط * Aتوليد ميشود برابر با Nو عمق راه حل برابر ب ا dباش د ،ان گ اه
* bفاک تور انشعابی است که درخت يکنواختی به عمق dبايد داشته باشد تا حاوی N+1گره باشد
)*N 1 1 b* (b
...
)*(b
ً
فاک تور انشعاب مؤثر معموال برای مسئله های سخت ثابت است
d
2
اندازه گيريهای تجربي * bبر روی مجموعه کوچکي از مسئله ها ميتواند راهنمای خوبي برای مفيد بودن اک تشاف باشد
مقدار * bدر اک تشافي با طراحي خوب ،نزديک 1است
153
151.
جست و جوی اگاهانه و اک تشافاثر دقت اک تشاف بر کاراي ي
فاک تور انشعاب مؤثر
هزينه جست و جو
154
ميانگين گره های بسط يافته در جستجوی IDSو * Aو فاک تور انشعاب مؤثر با استفاده از h1و h2
152.
جست و جوی اگاهانه و اک تشافاثر دقت اک تشاف بر کاراي ي
اگر برای هر گره nداشته باشيمh2(n) >= h1(n) :
h2 بر h1غالب است
غالب بودن مستقيما به کاراي ي ترجمه ميشود
تعداد گره هاي ي که با بکارگيری h2بسط داده ميشود ،هرگز بيش از بکارگيری h1نيست
هميشه بهتر است از تابع اک تشافی با مقادير بزرگ استفاده کرد ،به
شرطی که زمان محاسبه اک تشاف ،خيلي بزرگ نباشد
155
153.
جست و جوی اگاهانه و اک تشافالگوريتم های جست و جوی محلی و بهينه سازی
الگوريتم های قبلی ،فضای جست و جو را به طور سيستماتيک بررسی ميکنند
تا رسيدن به هدف يک يا چند مسير نگهداری ميشوند
مسير رسيدن به هدف ،راه حل مسئله را تشکيل ميدهد
در الگوريتم های محلی مسير رسيدن به هدف مهم نيست
مثال :مسئله 8وزير
دو امتياز عمده جست و جوهای محلي
استفاده از حافظه کمکی
ارائه راه حلهای منطقي در فضاهای بزرگ و نامتناهی
اين الگوريتمها برای حل مسائل بهينه سازی نيز مفيدند
156
يافتن بهترين حالت بر اساس تابع هدف
154.
جست و جوی اگاهانه و اک تشافالگوريتم های جست و جوی محلی و بهينه سازی
157
155.
جست و جوی اگاهانه و اک تشافجست و جوی تپه نوردی
حلقه اي که در جهت افزايش مقدار حرکت ميکند(بطرف باالی تپه)
رسيدن به بلندترين قله در همسايگی حالت فعلی ،شرط خاتمه است.
ساختمان داده گره فعلی ،فقط حالت و مقدار تابع هدف را نگه ميدارد
جست و جوی محلی حريصانه نيز نام دارد
بدون فکر قبلي حالت همسايه خوبي را انتخاب ميکند
تپه نوردی به داليل زير ميتواند متوقف شود:
بيشينه محلي
برامدگي ها
فات
158
156.
اين سياست ساده ،سه زيان عمده دارد: :Local Maxima يک ماکزيمم محلي ،برخاف ماکزيمم عمومي ،قلهاي است که پائينتر از بلندترين قله
درفضاي حالت است .زماني که روي ماکزيمم محلي هستيم ،الگوريتم توقف خواهد نمود .اگرچه راه حل نيز ممکن است دور
از انتظار باشد.
:Plateaux يک فات محوطهاي از فضاي حالت است که تابع ارزياب يکنواخت باشد .جستجو يک قدم تصادفي
را برخواهد داشت.
:Ridges نوک کوه ،داراي لبههاي سراشيب است .بنابراين جستجو به باالي نوک کوه به اساني ميرسد ،اما بعد با
ً
مستقيما به سمت باالي نوک کوه حرکت کنند .جستجو
مايمت به سمت قله ميرود .مگر اينکه عملگرهاي ي موجود باشند که
ممکن است از لبهاي به لبه ديگر نوسان داشته باشد و پيشرفت کمي را حاصل شود.
157.
جست و جوی اگاهانه و اک تشافجست و جوی تپه نوردی
انوام تپه نوردی:
تپه نوردی غيرقطعی ،تپه نوردی اولين انتخاب ،تپه نوردی شروم مجدد تصادفی
مثال :مسئله 8وزير
مسئله 8وزير با استفاده از فرمولبندی حالت کامل
در هر حالت 8وزير در صفحه قرار دارند
تابع جانشين :انتقال يک وزير به مربع ديگر در همان ستون
تابع اک تشاف :جفت وزيرهاي ي که نسبت به هم گارد دارند
مستقيم يا غير مستقيم
160
158.
جست و جوی اگاهانه و اک تشافمثال جست و جوی تپه نوردی
ب
الف -حالت با هزينه h=17که مقدار hرا برای هر جانشين نشان ميدهد
ب -کمينه محلی در فضای حالت 8وزير؛ h=1
161
الف
159.
160.
161.
162.
163.
164.
هوش مصنوعيفصل ششم
جستجوی خصمانه
167
165.
هوش مصنوعيفهرست
168
Artificial Intelligence
بازيها چيستند و چرا مطالعه ميشوند؟
انواع بازيها
الگوريتم minimax
بازيهای چند نفره
هرس الفا-بتا
بازيهای قطعی با اطالعات ناقص
بازيهاي ي که حاوی عنصر شانس هستند
166.
جستجوی خصمانهمثال :هرس الفا-بتا
]∞[3,+
این گره برای Maxمناسب نیست
][-∞,2
169
][3,3
167.
جستجوی خصمانهاثر افق
وقت ی بوج ود م ي اي د ک ه برنام ه ب ا اث ری از رقي ب
مواجه شود که منجر به خرابی جدی گش ته و اجتن اب
پذير است
مثال :شکل مقابل؛
س ياه در اص ل جلوس ت ،ام ا اگ ر س فيد پي اده اش را از
سطر هفتم به هشتم ببرد ،پي اده ب ه وزي ر تب ديل ميش ود
و موقعيت برد برای سفيد بوجود مي ايد
170
168.
هوش مصنوعيفصل هفتم
عامل های منطقی
171
169.
هوش مصنوعيفهرست
Artificial Intelligence
عاملهای مبتنی بر دانش
منطق
منطق گزاره ای
الگوهای استدالل در منطق گزاره ای
الگوريتم resolution
زنجير پيشرو و عقبگرد
172
170.
عاملهای منطقیعاملهای مبتنی بر دانش
مؤلفه اصلي عامل مبتنی بر دانش ،پايگاه دانش ان است
پايگاه دانش :مجموعه ای از جمات
جمله :زبان نمايش دانش و بيان ادعاهاي ي در مورد جهان
محدوده الگو ِريتمهای مستقل
خاص
اطالعات
محدوده
خاص
اطالعات
محدوده
برای اضافه کردن جمات به پايگاه دانش و درخواست دانسته ها
TELL و ASK
هر دو ممکن است شامل استنتاج باشند
173وی:انجام فرايند استنتاج تحت مقررات خاص
پير
ask
بخش استنتاج
پايگاه دانش
tell
171.
عاملهای منطقیعاملهای مبتنی بر دانش
عامل مبتنی بر دانش بايد بتواند:
نمايش حاالت و فعاليتها
ترکيب ادراکات جديد
بروز کردن تصور داخلی خود از جهان
استنباط خصوصيات مخفی جهان
استنتاج فعاليتهای مناسب
عامل پايگاه دانش خيلی شبيه به عاملهاي ي با حالت درونی است
عاملها در دو سطح متفاوت تعريف ميشوند:
سطح دانش :عامل چه چيزی ميداند و اهداف ان کدامند؟
سطح پياده سازی :ساختمان داده اطاعات پايگاه دانش و چگونگی دستکاری انها
174
172.
عاملهای منطقی معيار کاراي ي:
جهان WUMPUS
+1000 انتخاب طا -1000 ،افتادن در گودال يا خورده شدن -1 ،هر
مرحله -10 ،برای استفاده از تير
محيط:
بوی تعفن در مربعهای همجوار WUMPUS
نسيم در مربعهای همجوار گودال
درخشش در مربع حاوی طا
کشته شدن WUMPUSبا شليک در صورت مقابله
تير فقط مستقيم عمل ميکند
برداشتن و انداختن طا
حسگرها:
بو تعفن ،نسيم ،تابش ،ضربه ،جيغ زدن
محرکها:
گردش به چ ،،گردش به راست ،جلو رفتن ،برداشتن ،انداختن ،شليک
175
کردن
173.
عاملهای منطقیتوصيف جهان WUMPUS
قابل مشاهده کامل :خير ,فقط ادراک محلي
قطعی :بله ،نتيجه دقيقا مشخص است
رويدادی :خير ،ترتيبي از فعاليتهاست
ايستا :بله WUMPUS ,و گودالها حرکت ندارند
گسسته :بله
تک عامله :بله WUMPUS ،در اصل يک خصوصيت طبيعي است
176
174.
عاملهای منطقیکاوش در جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
177
175.
عاملهای منطقیتوصيف جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
178
176.
عاملهای منطقیتوصيف جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
179
177.
عاملهای منطقیتوصيف جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
180
178.
عاملهای منطقیتوصيف جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
181
179.
عاملهای منطقیتوصيف جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
182
180.
عاملهای منطقیتوصيف جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
183
181.
عاملهای منطقیتوصيف جهان WUMPUS
عامل = A
نسيم = B
درخشش،طال = G
مربع امن = OK
گودال = P
تعفن = S
مالقات شده = V
W = Wumpus
184
182.
عاملهای منطقیمنطق
يک زبان رسمي:
ترکيب(نحو) :چه کلمه بندی صحيح است(.خوش فرم)
معناشناسی :يک کلمه بندی صحيح چه معناي ي دارد
در منطق ،معنای زبان ،درستی هر جمله را در برابر هر جهان ممکن تعريف ميکند
مثال ،در زبان رياضيات
X+2 >= y يک جمله اما x2+yجمله نيست
X+2 >= y در جهان درست است اگر x=7و y =1
X+2 >= y در جهان غلط است اگر x=0و y =6
185
183.
عاملهای منطقیاستلزام
استلزام منطقي بين جمات اين است که جمله ای بطور منطقي از جمله ديگر پيروی ميکند
a╞b
جمله aاستلزام جمله bاست
جمله aجمله bرا ايجاد ميکند
اگر و فقط اگر ،در هر مدلي که aدرست است b ،نيز درست است
اگر aدرست باشد b ،نيز درست است
درستی bدر درستي aنهفته است
مثال :جمله x+y=4مستلزم جمله 4=x+yاست
186
184.
عاملهای منطقیمنطق گزاره ای
نحو منطق گزاره ای ،جمات مجاز را تعريف ميکند
جمات اتميک(عناصر غير قابل تعميم) تشکيل شده از يک نماد گزاره
هر يک از اين نمادها به گزاره ای درست يا نادرست اختصاص دارد
نمادها از حروف بزرگ مثل R,Q,Pاستفاده ميکنند
جمات پيچيده با استفاده از رابطهای منطقي ،از جمات ساده تر ساخته ميشوند
187
)not( ┐ جمله ای مثل ┐W1,3نقيض W1,3است
ليترال يک جمله اتميک(ليترال مثبت) ،يا يک جمله اتميک منفي(ليترال منفي) است
)and( ^ مثل W1,3 ^ P1,3ترکيب عطفی نام دارد.هر بخش ان يک عطف ناميده ميشود
)or( ν مثل )W1,3 ^ P3,1( ν W2,2ترکيب فصلي مربوط به فصل های W2,2و W1,3 ^ P3,1
( => اس تلزام) )W1,3 ^ P3,1( => ┐ W2,2 :اس تلزام ي ا ش رطی نامي ده ميش ود .مقدم ه ي ا مق دم ان W1,3 ^ P3,1و
نتيجه يا تالي ان ┐ W2,2است
جمله W1,3 W2,2دو شرطی نام دارد
185.
عاملهای منطقیمنطق گزاره ای
188
186.
عاملهای منطقیجدول درستی پنج رابطه منطقی
P
Q
┐P
P ^ Q P ν Q P=>Q P Q
F
F
T
F
F
T
T
F
T
T
F
T
T
F
T
F
F
F
T
F
F
T
T
F
T
T
T
T
189
187.
عاملهای منطقیمنطق گزاره ای در دنيای Wumpus
در B1,1نسيمي وجود دارد
)B1,1 (P1,2 ν P2,1
در ] [1,1گودالی وجود ندارد
R1: ┐P1,1
190
188.
عاملهای منطقیالگوهای استدالل در منطق گزاره ای
قوانين استنتاج :الگوهاي ي استاندارد که زنجيره ای از نتايج را برای رسيدن به هدف ايجاد ميکند
قياس استثناي ي :با استفاده از ترکيب عطفی ،ميتوان هر عطف را استنتاج کرد(يعنی هر وقت جمله ای به شکل
a=>bداده شود ،جمله bرا ميتوان استنتاج کرد).
ميتوان از
)(WumpusAhead ^ WumpusAlive
و
(WumpusAhead ^ WumpusAlive) => Shoot
Shootرا استنتاج کرد
191
,
189.
عاملهای منطقی حذف :andهر عطف را ميتوان از ترکيب عطفی استنتاج کرد
مثال WumpusAlive :را ميتوان از جمله زير استناج کرد
)(WumpusAhead ^ WumpusAlive
خاصيت يکنواختی
مجموعه ای از جمات استلزامی که فقط ميتواند در صورت اضافه شدن اطاعات به پايگاه دانش رشد کند.
برای جمات aو bداريم:
192
KB | KB |
190.
هوش مصنوعيفصل هشتم
منطق رتبه اول
193
191.
هوش مصنوعيArtificial Intelligence
فهرست
مروری بر منطق گزاره ای
منطق رتبه اول
انواع منطق
نحو و معنای منطق رتبه اول
مهندسی دانش
194
192.
منطق رتبه اولمروری بر منطق گزاره ای
ويژگيها
ماهيت اعانی
دانش و استنتاج متمايزند و استنتاج ً
کاما مستقل از دامنه است
قدرت بيان کافی برای اداره کردن اطاعات جزئي
با استفاده از ترکيب فصلی و نقيض
قابليت ترکيب
معنای جمله ،تابعي از معنای بخشهای ان
معنا ،مستقل از متن است
بر خاف زبانهای طبيعي که ،معنای جمات وابسته به متن است
معايب
فاقد قدرت بياني برای تشريح دقيق محيطی با اشياي مختلف
195
بر خاف زبانهای طبيعی
193.
منطق رتبه اولمنطق رتبه اول
اساس منطق گزاره ای را پذيرفته و بر اساس ان يک منطق بيانی ميسازيم
از ايده های نمايشي زبان طبيعي استفاده کرده ،از عيوب ان اجتناب ميکنيم
زبانهای طبيعی از جهان طبقه بندی زير را دارند
نگها،اتش و
فوتبال،
بازيهای
اعداد،ر راد،نگها،
بازيهای...فوتبال ،اتش و ...
اعداد ،ر
خانه،
خانه،اشياء :اف
اشياء :افراد ،
رابطه ها :رابطه ها:
مثلو ...
خواصاول
قرمز ،گرد،
هایمثل
خواص
قرمز ،گرد ،اول و ...
يکاني يا
رابطه های يکاني يارابطه
مالکيت و ...
بودن،
بودن،ي بزرگ
مثل بر
رابطه های چندتاي
بخشی از ،مالکيت و ...
از ،بودن،
بخشیرگ تر
بودن ،بز
مثل بتررادر
هایادرچندتاي
ريابطه
بيشتر از و
بودن،يکي
دوست،
توابع :پدر بودن،
دوست ...،يکي بيشتر از و ...
بهترين
بهترينپدر
توابع:
منطق رتبه اول توسط اشيا و رابطه ها ساخته ميشود
196
194.
منطق رتبه اولانوام منطق
هستی شناسی
حقيقت شناسی
(انچه در جهان هست)
(اعتقادات عامل راجع به حقايق)
منطق گزاره ای
منطق رتبه اول
حقايق
حقايق ،اشيا ،رابطه ها
درست/نادرست/نامشخص
درست/نادرست/نامشخص
منطق موقتی
حقايق ،اشيا ،رابطه ها ،زمان
درست/نادرست/نامشخص
نظريه احتمال
حقايق
حقايق با درجه ای از درستی متعلق به
][0,1
درجه ای از اعتقاد متعلق به ][0,1
زبان
منطق فازی
197
در فاصله معين
195.
منطق رتبه اولنحو و معنای منطق رتبه اول
نمادهای ثابت؛ اشيا را نشان ميدهد .مثال :علی ،2 ،رضا... ،
نمادهای محمول؛ رابطه ها را نشان ميدهد .مثال:برادر بودن ،بزرگ تر بودن از
نمادهای تابع؛ توابع را نشان ميدهند .مثال :تابع پای چ)LeftLeg(،
متغيرهاx , y , a ,b :
روابط منطقی , , , , :
تساوی= :
سورها , :
198
196.
منطق رتبه اولجمات اتميک
هر ترم يک عبارت منطقی است که به شيئ اشاره ميکند
نمادهای ثابت ترم هستند
هميشه استفاده از نماد متمايز برای نامگذاری شیء اسان نيست
)LeftLeg(John
پای چ ،پای پادشاه John
.
متغير
ثابت
يا
يا )ترم ،1ترم ، ... ،2ترم(nتابع = ترم
جمات اتميک :ترکيب ترمهای اشياء و محولهای روابط
.
ترم =2ترم1
مثال:
199
يا
)ترم ،1ترم ، ... ،2ترم(nمحمول = جمالت اتميک
))Married(Father(Richard),Mother(John
پدر ريچارد با مادر جان ازدواج کرده است
197.
منطق رتبه اولجمات پيچيده
با ترکيب جمات اتميک و روابط منطقی ميتوان جمات پيچيده تری ساخت
S, S1 S2, S1 S2, S1 S2, S1 S2
Brother(LeftLeg(Richard),John)
:مثال
Brother(Richard,John) Brother(John,Richard)
King(Richard) King(John)
King(Richard) King(John)
200
198.
منطق رتبه اول مثال
مدلی با پنج شیء،
دو رابطه دودوي ي،
سه رابطه يکانی و
يک تا يکانی به نام
پای چ،
201
199.
منطق رتبه اولسورها
کمک ميکنند تا به جای شمارش اشيا از طريق نام انها ،خواص کلکسيون اشيا را
بيان کرد
سور عمومی؛ “ برای همه”
سور وجودی؛ “ وجود دارد حداقل”...
202
200.
منطق رتبه اولسور عمومی
>جمله< >متغيرها<
x P که در ان Pيک عبارت منطقي است ،بيان ميکند که Pبرای
هر شیء xدرست است
مثال:
203
) x King(x) Person(x
201.
منطق رتبه اولسور وجودی
>جمله< >متغيرها<
x P که در ان Pيک عبارت منطقي است ،بيان ميکند که P
حداقل برای يک شیء xدرست است
مثال x Crown(x) OnHead(x , John) :
204
202.
منطق رتبه اولخصوصيات سورها
رابط طبيعي برای کار با و رابط طبيعي برای کار با ميباشد
استفاده از بعنوان رابط اصلی با منجر به حکم قوی ميشود
استفاده از با منجر به حکم ضعيفي ميشود
x y برابر است با y xو x yبرابر است با y x
x y برابر نيست با y x
x y Loves(x,y)
حداقل يک نفر وجود دارد که همه چيز در جهان را دوست دارد
y x Loves(x,y)
همه در دنيا حداقل يک نفر را دوست دارند
205
203.
منطق رتبه اولخصوصيات سورها
“ هر کسی بستنی را دوست دارد” به معنای اين است که “هيچ کس وجود ندارد که بستنی را
دوست نداشته باشد”
x Likes(x , IceCream) هم ارز ) x Likes(x , IceCream
x P هم ارز x P
x P هم ارز x P
x P
هم ارز x P
x P
هم ارز x P
206
204.
منطق رتبه اولتساوی
با استفاده از = دو ترم به يک شیء اشاره ميکنند
برای تعيين درستی جمله تساوی بايد ديد که ايا ارجام ها به دو ترم ،اشيای
يکسانی اند يا خير
مثال :ريچارد حداقل دو برادر دارد
) x,y Brother(x,Richard) ^ Brother(y,Richard) ^ (x=y
207
205.
منطق رتبه اولادعاها و تقاضاها
جمات از طريق TELLبه پايگاه دانش اضافه ميشوند
اين جمات را ادعا گويند
TELL (KB , King(John))
TELL (KB , x King(x) => Person(x))
با استفاده از ASKتقاضاهاي ي را از پايگاه دانش انجام ميدهيم
اين پرسشها ،تقاضا يا هدف نام دارد
ASK (KB , Person(John))
ASK(KB , x Person(x))
ليست جانشيني يا انقياد
ليستي از جانشينيها در صورت وجود بيش از يک پاسخ
208
206.
منطق رتبه اولدامنه خويشاوندی
مادر هر فرد والد مؤنث ان فرد است
m,c Mother(c) = m Femail(m) ^ Parent(m,c)
شوهر هر فرد ،همسر مذکر ان فرد است
w,h Husband(h,w) Male(h) ^ Spouse(h,w)
مذکر و مؤنث بودن طبقه های متمايزی هستند
x, Male(x) Female(x)
والد و فرزند ،رابطه های معکوس هستند
p,c Parent(p,c) Child(c,p)
والدين والدين هر فرد است
پدر بزرگ يا مادربزرگ
ِ
g,c Grandparent(g,c) p Parent(g,p) ^ Parent(p,c)
209
207.
منطق رتبه اولاعداد و مجموعه ها
s Set(s) (s = {} ) ( x,s2 Set(s2) s = {x|s2})
x,s {x|s} = {}
x,s x s s = {x|s}
x,s x s [ y,s2} (s = {y|s2} (x = y x s2))]
210
208.
منطق رتبه اولمهندسي دانش
فرايند کلی ساخت پايگاه دانش که شامل مراحل ذيل ميباشد:
مشخص کردن کار
مونتاژ دانش مربوطه
تصميم گيری در مورد واژه نامه محمولها ،توابع و وراثت
کدگزاری دانش کلی در مورد دامنه
کد گزاری توصيف نمونه مسئله خاص
ِ اعمال تقاضاها به رويه استنتاج و دريافت پاسخ
211
اشکال زداي ي پايگاه دانش