هوش مصنوعی

هوش مصنوعی

اسلاید 1: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )1هوش مصنوعي نام مرجع : Artificial Intelligence A Modern Approach نويسنده :استوارت راسل، پيتر نورويگ تهيه کننده :محمدمهدي يزدان پناه رستمي

اسلاید 2: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )2هوش مصنوعيفصل اولمقدمه

اسلاید 3: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )3AI: به طور رسمي در سال 1956 مطرح شده است.علل مطالعه Al: AI سعي دارد تا موجوديت‌هاي هوشمند را درک کند. از اين رو يکي از علل مطالعه آن يادگيري بيشتر در مورد خودمان است. جالب و مفيد بودن موجوديت‌هاي هوشمند .

اسلاید 4: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )4AI چيست؟‌تعاريفي از AI که به چهار قسمت تقسيم شده‌اند: پردازش فکري و استدلالي پردازش رفتاري ايده‌آل هوشمندي (منطقي بودن) ارائه انساني

اسلاید 5: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )5سيستم‌هايي که مانند انسان فکر مي‌کنندسيستم‌هايي که به طور منطقي فکر مي‌کنندسيستم‌هايي که مانند انسان عمل مي‌کنندسيستم‌هايي که به طور منطقي عمل مي‌کنند تمرکز بر روي پردازش‌هاي رفتاري پردازش‌هاي فکري و استدلاليايده‌آل هوشمنديارائه انساني

اسلاید 6: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )6انسان گونه عمل کردن: رهيافت آزمون تورينگآزموني از کامپيوتر به عمل آيد، و آزمون گيرنده نتواند دريابد که در آن طرف انسان قرار دارد يا کامپيوتر. براي اين کار کامپيوتر بايد قابليت‌هاي زير را داشته باشد: پردازش زبان طبيعي = محاورهبازنمايي دانش= ذخيره اطلاعات استدلال خودکار= استدلال و استخراج يادگيري ماشيني= کشف الگو و برون ريزي

اسلاید 7: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )7تست تورينگ: اين آزمون از ارتباط فيزيکي مستقيم بين کامپيوتر و محقق اجتناب مي‌کند.به منظور قبول شدن در تست تورينگ کلي، کامپيوتر به موارد زير احتياج دارد: بينايي ماشين براي درک اشياء روباتيک به منظور حرکت آنها

اسلاید 8: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )8مقدمه (مانند انسان عمل کردن)تست تورينگABکدام انسان است؟A يا B

اسلاید 9: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )92. انساني فکر کردن-: رهيافت مدلسازي شناختي:چگونگي شناسايي عملکرد افکار انسان:1- درون گرايي 2- تجارب روانشناسيعلوم شناختي : مدل‌هاي کامپيوتر از AI و همچنين تکنيک‌هاي روانشناختي را گرد هم مي‌آورد تا بتواند تئوري‌هاي دقيقي از کارکرد ذهن انسان به دست آورند.

اسلاید 10: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )103. منطقي فکر کردن: قوانين رهيافت تفکررمز «تفکر درست»: ارسطو سعي در کشف آن داشت.قياس: از موضوعات مطرح شده توسط ارسطو مي‌باشد، که الگوهايي براي ساختار توافقي ايجاد کرد که همواره نتايج صحيحي به اندازه مقدمات صحيح به دست مي‌آورد.مثال: «سقراط انسان است، تمام انسان‌ها مي‌ميرند، پس سقراط خواهد مرد.»

اسلاید 11: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )11دو مشکل عمده در اين رسم منطق‌گرايي وجود دارد: تبديل دانش غير رسمي به شکل رسمي توسط اعلام، منطقي ساده نيست.تفاوت عمده‌اي بين قادر به حل مسئله بودن در اصول و انجام آن در عمل وجود دارد.

اسلاید 12: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )124. منطقي عمل کردن: رهيافت عامل منطقيعامل: در اصل چيزي است که ابتدا درک مي‌کند و سپس عمل مي‌کند. در نگرش «قوانين تفکر» تأکيد عمده بر روي استنتاج‌هاي صحيح بوده است.«مهارت‌هاي شناخت» که براي آزمون تورينگ موردنياز است، براي انجام فعاليت‌هاي منطقي وجود دارند.

اسلاید 13: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )13مزاياي مطالعه AI به‌عنوان طراحي عامل منطقي:عمومي‌تر از رهيافت «قوانين تفکر»پيشرفت علمي، بسيار قانون‌پذيرتر از رهيافت‌هايي است که بر تفکر يا رفتار انساني متکي هستند.

اسلاید 14: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )14زيربناي هوش مصنوعي:AI، از علوم مختلفي بهره مي‌برد که از ميان آنها علوم زير مهم‌تر شناخته شده‌اند:علم فلسفهعلم رياضيعلم روانشناسيعلم زبان‌شناسيعلم کامپيوتر

اسلاید 15: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )15فلسفه: (428 قبل از ميلاد مسيح – تاکنون)پايه‌هاي تفکر و فرهنگ غرب تشکيل شده است از: افلاطون، استادش سقراط، و شاگردش ارسطو.قياس: ارسطو، سيستمي غيررسمي از قياس براي استدلال مناسب توسعه داد، امکان توليد نتايج، بر پايه فرضيات اوليه به طور مکانيکي وجود داشت.در نظر گرفتن ذهن به‌عنوان سيستمي فيزيکي

اسلاید 16: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )16رنه دکارت مدافع سرسخت قدرت استدلال بود؛ و همچنين طرفدار مکتب دواليسم.ماترياليسم: در مقابل دواليسم قرار دارد و معتقد است تمامي جهان مطابق قوانين فيزيکي عمل مي‌کنند.ويلهم لايبنيز: تبديل موقعيت ماترياليستي به نتايج منطقيساخت ابزاري مکانيکي براي انجام عمليات منطقي

اسلاید 17: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )17 ايجاد منبع دانش:فرانسيس بيکن، جنبش آزمون‌گرايان را آغاز کرد. و با شعار جان لاک مفهوم يافت:«هيچ چيز قابل فهم نيست اگر ابتدا در حس نباشد.»اصل استقراي امروزي، در حقيقت از کتاب ديويد هيوم نشأت مي‌گيرد: رسانه‌اي از طبيعت انسانبرتراندراسل، پايه‌گذار پوزيوتيزم منطقي، ارائه‌دهندة اين تئوري بود که:«قوانين عمومي توسط تکرار ارتباطات بين عناصر آنها به وجود مي‌آيند.»

اسلاید 18: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )18ارتباط بين دانش و عملاشياء را با تحليل، دسته‌بندي مي‌کنيم و در اطراف آنها، کارکرد مورد نيازشان نوسان مي‌نمايد.در اين ميان پايه سيستم‌مکاشفه‌اي GPS بنيان گذارده مي‌شود.

اسلاید 19: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )19رياضيات (800. C-تاکنون)براي ارتباط فلسفه با دانش نظري، نياز به فرمول‌سازي رياضي در سه زمينه اصلي است:محاسباتمنطقاحتمالات

اسلاید 20: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )20محاسبات: نظريه اظهار محاسبات به عنوان الگوريتمي رسمي به خوارزمي برمي‌گردد، رياضيدان عربي قرن نهم که نوشته‌هاي وي، جبر و تئوري اعداد عربي را به اروپا معرفي کرد.

اسلاید 21: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )21منطق:در اين زمينه، دانشمندان زيادي بر چگونگي شکل‌گيري و هدايت آن، نقش داشته‌اند که به چند نفر از آنها اشاره مي‌کنيم:ارسطو: دانشمندي که بيشترين شکل‌گيري نگرش فلسفي منطق را به او نسبت مي‌دهند.جورج بول: يک زبان رسمي براي ساخت استنتاج منطقي ارائه داد.FREGE: منطق مرتبه اول را به شکلي مطرح نمود که در بيشتر سيستم‌هاي نمايش دانش پايه استفاده مي‌شود.آلفرد تارسکي: تئوري چگونگي ارتباط بين اشياء موجود در محيط منطقي، و اشياء موجود در دنياي واقعي را ارائه نمود.

اسلاید 22: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22ديويد هيلبرت: رياضيدان بزرگي بود که شهرت وي به دليل مسائلي است که نتوانست حل کند.راسل: قضيه کامل نبودن (incompleteness) را مطرح نمود.تورينگ: ماشين تورينگ قادر به محاسبه هر تابع محاسبه‌پذيري است.تئوري پيچيدگي: انجام‌ناپذيرياستحالهاستيون کوک و ريچارد کارپ: تئوري NP-completeness را مطرح کردند.

اسلاید 23: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )23احتمالات: گاردنيوي: اولين کسي بود که ايده احتمال را مطرح کرد.پير فرمت، پاسکال، برنولي، لاپلاس و ديگر دانشمندان بر رشد و توسعه اين ايده تأثير داشتند.برنولي: ديدگاه «درجه باور» ذهني را در مقايسه با نرخ نتايج عيني مطرح کرد.بيس: قانوني براي بهنگام‌سازي احتمالات ذهني را به وجود آورد.نيومن و مورگنسترن: تئوري تصميم‌گيري را آغاز کردند. و از ترکيب تئوري احتمال، و تئوري سودمندي حاصل مي‌شود.

اسلاید 24: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )24روانشناسي (1879- تاکنون): هلمولتز: روشي علمي براي مطالعه بينايي انسان به کار برد؛ که اين کتاب به عنوان مرجع بينايي فيزيولوژيک و حتي به‌عنوان «مهمترين رساله فيزيکي و روانشناختي بينايي انسان تا به امروز» شناخته مي‌شود.وندت: اولين آزمايشگاه روانشناسي تجربي را در دانشگاه لايپزيک راه‌اندازي کرد.داتسون و تورن دايک: حرکت رفتارگرايي (behaviorism) را مطرح کردند.اساس مشخصه روانشناسي شناختي(congnitive psychology)، اين نگرش است که مغز دارنده و پردازش‌کننده اطلاعات است.

اسلاید 25: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )25کريک، کتاب ماهيت بيان را منتشر کرد. و سه مرحله کليدي را براي عامل مبتني بر داشن معين کرد: محرک‌ها بايد به شکل دروني تبديل شوند. بازنمايي توسط پردازش‌هاي شناختي بازنمايي‌هاي داخلي جديدي را مشتق کند. اينها دوباره به صورت عمل برگردند.

اسلاید 26: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )26مهندسي کامپيوتر (1940- تاکنون)براي پيشرفت هوش مصنوعي، به دو چيز احتياج داريم:هوشمحصول مصنوعيدر اين تقسيم‌بندي، کامپيوتر مي‌تواند به عنوان محصول مصنوعي محسوب گردد.

اسلاید 27: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )27Heath Robinson: اولين کامپيوتر مدرن عملياتي بود که در سال 1940 توسط تيم آلن تورينگ به منظور کدگشايي پيام‌هاي آلمان‌ها ساخته شد.Colossus: نام ماشين بعدي بود که تيوپ‌هاي مکنده در آن به کار برده شد.Z-3: اولين کامپيوتر قابل برنامه‌ريزي که توسط کنراد زوس در 1941 اختراع شد.

اسلاید 28: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )28اعداد با مميز شناور و زبان Plankalkul نيز توسط زوس اختراع شدند.ABC: اولين کامپيوتر الکترونيک در امريکا توسط جان آتاناسف و کليفورد در دانشگاه ايالتي ايوا ساخته شد. MARK I , II , III: توسط تيمي به رهبري هوراد ايکن در هاروارد توسعه داده شد.ENIAC: اولين کامپيوترديجيتال الکترونيک چند منظوره، توسط تيمي به سرپرستي ماچلي و اکرت در دانشگاه پنسيلوانيا ساخته شد.

اسلاید 29: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )29IBM 701: اولين کامپيوتر سودآور، توسط ناتانيل روچتر در 1952 ساخته شد. چارلز بابيج: طراحي ماشيني که جداول لگاريتمي را محاسبه کند. طراحي موتور آناليتيکي طرح حافظه قابل‌آدرس‌دهي، برنامه ذخيره شده و پرش‌هاي شرطي

اسلاید 30: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )30کار در زمينه AI منجر به ايده‌هاي بسيار متعددي شد که به علوم کامپيوتر برگشت؛ مانند:اشتراک زماني – مفسرهاي دوسويه – نوع داده ليست پيوندي – مديريت حافظه خودکار و برخي نکات کليدي برنامه‌نويسي شيءگرا و محيط‌هاي توسعه برنامه مجتمع با واسط کاربر گرافيکي.

اسلاید 31: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )31زبان‌شناسي (1975- تاکنون)اسکينر در سال 1975 کتابي در زمينه رفتارگرايان براي يادگيري زبان، با نام «رفتار زباني» منتشر کرد.نوآم چامسکي بر اساس تئوري خودش يعني ساختارهاي ترکيبي، اين کتاب را تجديد نظر و چاپ کرد. که به اندازه اصل کتاب شهرت پيدا کرد.تئوري چامسکي بر اساس مدل‌هاي نحوي قرار دارد.

اسلاید 32: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )32زبان‌شناسي مدرن و AI در يک زمان متولد شدند، بنابراين زبان‌شناسي نقش مهمي در رشد AI بازي نمي‌کند.اين دو دريک زمينه مشترک به نام زبان‌شناسي محاسباتي(Computatioal linguistics) يا پردازش زبان طبيعي (natural language processing)بهم تنيده شده‌اند که در آن بر روي مسئله استفاده زبان تمرکز شده است.

اسلاید 33: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )33تاريخچه هوش مصنوعيپيدايش هوش مصنوعي (1943- 1956) اشتياق زودهنگام، آرزوهاي بزرگ (1952-1969)مقداري واقعيت (1974-1966)سيستم‌هاي مبتني بر دانش: کليد قدرت؟ (1969-1979)بازگشت شبکه‌هاي عصبي (1986- تاکنون)حوادث اخير (1987- تاکنون)

اسلاید 34: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )34پيدايش هوش مصنوعياولين کار جدي در حيطه AI، توسط وارن مک‌کلود و والتر پيتز انجام شد.سه منبع استفاده شده توسط آنها:دانش فيزيولوژي پايه و عملکرد نرون در مغزتحليل رسمي منطق گزاره‌ها متعلق به راسل و رايت هدتئوري محاسبات تورينگ

اسلاید 35: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )35در 1949 دونالد هب، قانون ساده بهنگام‌سازي براي تغيير تقويت اتصالات بين نرون‌ها را تعريف کرد که از طريق آن يادگيري ميسر مي‌گردد.در زماني که کلود شانون و آلن تورينگ، برنامه بازي شطرنج را نوشتند ، SNARC، اولين کامپيوتر شبکه عصبي در دانشگاه پرينستون توسط مينسکي و ادموندز ساخته شد.اين کامپيوتر، از 3 هزار تيوپ مکشي و مکانيزم خلباني خودکار اضافي که مربوط به بمب‌افکن‌هاي B24 مي‌باشد براي شبيه‌سازي شبکه 40 نروني استفاده کرد.

اسلاید 36: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )36محققين علاقمند به تئوري آتوماتا، شبکه‌هاي عصبي و مطالعه هوش، گرد يکديگر جمع شدند و در کارگاهي در دورت موند مشغول فعاليت شدند. که در اين ميان نام هوش مصنوعي براي حيطه فعاليت آنها انتخاب شد.

اسلاید 37: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )37اشتياق زودهنگام، آرزوهاي بزرگ (1952-1969)فعالان در عرصه AI:روچستو و تيمش در IBM هربرت جلونتر: با ساخت Geometry Theorem Proverآرتور ساموئل: ساخت برنامه براي بازي چکر

اسلاید 38: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )38جان مک کارتي در MIT:تعريف زبان ليسپ (Lisp) مهمترين زبان هوش مصنوعي مفهوم اشتراک زماني (time sharing)نشر مقاله‌اي با عنوان برنامه‌ها با حواس مشترکتشريح يک سيستم فرضي به نام Advice Taker ، که به اصول پايه بازنمايي معرفت و استدلال تجسم بخشيد؛کار بر روي سيستم برنامه‌ريزي سؤال-جوابکار بر روي پروژه روبات‌هاي shakey

اسلاید 39: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )39مينسکي: کار بر روي ميکرو ورلدها و همکاري با مک‌کارتي، ولي بر سر اختلاف بر نگرش منطقي و ضدمنطقي کار تحقيقاتي خود را از هم جدا کردند.مينسکي با گروهي از دانشجويان بر روي ميکروورلدها کار کرد که برخي از آنها عبارتند از:جيمز اسلاگل، SAINT، قادر به حل مسائل انتگرال‌گيري فرم بسته اوانز: ANALOGY، حل مسائل مشابهت هندسي در تست‌هاي هوشرافائل: SIR: پاسخ به قضاياي پرسشي جملات ورودي بابرو: STUDENT: حل مسائل داستاني جبر

اسلاید 40: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )40مقداري واقعيت (1966-1974)مشکلات تقريباً تمام پروژه‌ها تحقيقي AI وقتي پديدار مي‌شدند که مسائل گسترده‌تري براي حل توسط آنها مطرح مي‌شد:برنامه‌هاي اوليه اغلب داراي دانش محدود يا فاقد دانش در مورد موضوع کار بودند.انجام ناپذيري بسياري از مسائلبه دليل اعمال برخي محدوديت‌هاي پايه‌اي بر روي ساختار پايه مورد استفاده براي توليد رفتار هوشمند

اسلاید 41: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )41سيستم‌هاي مبتني بر دانش: کليد قدرت؟ (1969-1979)روش‌هاي ضعيف: مبتني بر يک جستجوي همه‌منظوره مي‌باشند که قدم‌هاي اوليه يادگيري را برمي‌دارند اما تلاشي در جهت يافتن راه‌حل‌هاي کامل ندارند.به اين دليل که اطلاعات ضعيفي را در مورد دامنه فعاليت خود به کار مي‌برند.پس براي حل مسائل دشوار، تقريباً جواب را از قبل بايد بدانيم.برنامه DENDRAL از برنامه‌هايي است که از اين رهيافت استفاده مي‌کند.

اسلاید 42: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )42اهميت برنامه DENDRAL در اين بود که اولين سيستم موفق با دانش غني بود، يعني تبحر سيستم بر پايه تعداد بسيار زيادي قانون ايجاد شده بود. سيستم‌هاي بعدي ايده اصلي رهيافت Advice taker مک کارتي را دنبال مي‌کردند يعني جداسازي دانش (در شکل قوانين) و مؤلفه استدلال.

اسلاید 43: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )43MYCIN نسبت به DENDRAL دو تفاوت عمده دارد:برخلاف قوانين DENDRAL، هيچ مدل تئوري‌وار عمومي براي آنکه قوانين MYCIN استنتاج شود، وجود نداشت.قوانين مي‌بايست عدم قطعيت مربوط به دانش پزشکي را منعکس مي‌کرد.

اسلاید 44: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )44AI به يک صنعت تبديل مي‌شود (1980-1988)RI: اولين سيستم خبره تجاري موفق از شرکت DEC که سودآوري زيادي را براي شرکت بهمراه داشت.پروژه «نسل پنجم»: اين پروژه ژاپني به منظور ساخت کامپيوترهاي هوشمندي که پرولوگ را به جاي کد ماشين اجرا مي‌کردند، انجام شد.شرکت‌هاي ديگر جهان از جمله ميکروالکترونيک، MCC، ليسپ ماشين، تگزاس اينسترومنت، سمبوليکس، زيراکس و غيره در ساخت ايستگاه‌هاي کاري بهينه شده در اين عرصه فعاليت داشتند.

اسلاید 45: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )45بازگشت شبکه‌هاي عصبي:دانشمندان فعال در اين عرصه:هاپ فيلد: که به آناليز خواص ذخيره‌سازي و بهينه‌سازي شبکه‌ها پرداخت.راسل هارت و هينتون: مطالعه مدل‌هاي شبکه عصبي را ادامه دادند.بريسون و هو: الگوريتم يادگيري انتشار به عقب را مجدداً مطرح کردند.

اسلاید 46: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )46حوادث اخير:رهيافت HMM: رهيافت غالب در سال‌هاي اخير مي‌باشد که توسط مايکف به وجود آمده است.اين رهيافت از دو جنبه زير حائز اهميت است:مبتني بر نظريه رياضي محض است.طي فرايندي با يادگيري گروه عظيمي از داده گفتار واقعي خود را بهبود مي‌بخشد.

اسلاید 47: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )47برنامه‌ريزي: در دهه 70 فقط براي ميکرووردها مناسب بودند، اکنون براي زمانبندي کار در کارخانه‌ها و مأموريت‌هاي فضايي استفاده مي‌شوند.بيان شبکه باور: استدلال کارا را در مورد ترکيب رويدادهاي غيرمنطقي ممکن ساخت.

اسلاید 48: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )48ايده سيستم‌هاي خبره فرماتيو توسط کار جوداپير و ارديک هوروتيز و ديويد هکرمن مطرح شد:سيستم‌هايي که مطابق قوانين تئوري تصميم‌گيري به طور منطقي عمل مي‌کنند و سعي ندارند که تبحر انساني را تقليد کنند.

اسلاید 49: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )49شرايط کنوني:برخي از سيستم‌هايي موجود در جهان که از هوش مصنوعي استفاده مي‌کنند:HITECH: اولين برنامه کامپيوتري که موفق به شکست استاد بزرگ شطرنج جهان، آرنولد دنکر شده است.PEGASUS: يک برنامه درک گفتار که سؤالات کاربر را جواب مي‌دهد و تمامي برنامه‌هاي مسافرتي شخص را با يک برنامه‌ريزي درست، مقرون به صرفه مي‌کند.MARVEL: سيستم خبره‌اي که داده‌هاي ارسالي از سفينه فضايي را تحليل نموده و در صورت بروز مشکلات جدي، پيغام هشدار به تحليلگران مي‌دهد.

اسلاید 50: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )50هوش مصنوعيفصل دومعاملهاي هوشمند

اسلاید 51: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )51هوش مصنوعي Artificial Intelligenceفهرستعاملخواص محيطهاي وظيفهبرنامه هاي عامل

اسلاید 52: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )52عامل:به هر چيزي اطلاق مي‌شود، که قادر به درک محيط پيرامون خود از طريق حس‌گرها(sensor)و اثرگذاري‌ بر روي محيط از طريق اثرکننده‌ها (effector) باشد.عامل نرم‌افزاري: عامل نرم‌افزاري رشته‌هاي بيتي را به عنوان درک محيط و عمل، کدگذاري مي‌کند.عاملهاي هوشمند

اسلاید 53: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )53عوامل انسانيحس کردن: گوش، چشم، ديگر ارگان‌هااثرگذاري: دست، پا، بيني، اندام‌هاي ديگرعوامل روباتيکحس کردن: دوربين، يابنده‌هاي مادون قرمزاثرگذاري: موتورعاملهاي هوشمند

اسلاید 54: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )54عاملهاي هوشمند تابع عاملرفتار عامل توسط تابع عامل توصيف ميشود که هر دنباله ادراک را به يک فعاليت نقش ميکند. دنباله ادراکسابقه کامل هر چيزي است که عامل تاکنون درک کرده است. فعاليت دنباله ادراک : تابع عامل  f:P*®A

اسلاید 55: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )55environment?agentsensorseffectorsperceptsactionsعاملهاي هوشمند

اسلاید 56: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )56عاملهاي هوشمند معيارهاي کارايي معيار کارايي، معياري براي موفقيت رفتار عامل است. بر اساس خواسته هاي فرد در محيط انتخاب ميشودمعيار کارايي که ملاکهاي موفقيت را تعريف ميکند دانش قبلي عامل نسبت به محيط فعاليتهايي که عامل ميتواند انجام دهد دنباله ادراک عامل در اين زمان رفتار عقلايي

اسلاید 57: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )57عاملهاي هوشمند عامل عالـِم Omni science)) خروجي واقعي فعاليت خود را ميداند و ميتواند بر اساس آن عمل کند عامل خردمند (Rational agent)فعاليتي را انتخاب ميکند که معيار کارايي اش را حداکثر ميکند جمع آوري اطلاعات، اکتشاف، يادگيريعامل خود مختارنقص دانش قبلي خود را ميتواند جبران کند

اسلاید 58: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )58عاملهاي هوشمندخواص محيط هاي وظيفه کاملاً قابل مشاهده درمقابل قابليت مشاهده جزئي قطعي درمقابل غير قطعي راهبردي رويدادي(اپيزوديک) درمقابل ترتيبي ايستا درمقابل پويا گسسته درمقابل پيوسته تک عاملي درمقابل چند عامليچند عاملي رقابتي درمقابل چندعاملي همياري

اسلاید 59: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )59 قابل دسترسي در مقابل غيرقابل دسترسي( کاملاً قابل مشاهده در مقابل قابل مشاهده جزئي)محيط قابل دسترسي: محيطي که عامل آن توسط ابزار حس‌کننده‌اش امکان دسترسي به وضعيت کامل محيط را داشته باشد.محيط قابل دسترسي راحت است، زيرا عامل نيازمند دستکاري هيچ وضعيت داخلي براي حفظ دنيا را نخواهد داشت.

اسلاید 60: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )60 قطعي در مقابل غير قطعي محيط قطعي: محيطي است که اگر وضعيت بعدي محيط بوسيله وضعيت کنوني و اعمالي که با عامل‌ها انتخاب گردد، تعيين شود. بهتر است به قطعي يا غير قطعي بودن محيط از ديدگاه عامل نگاه کنيم.

اسلاید 61: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )61 اپيزوديک در مقابل غير اپيزوديک محيط اپيزوديک (episodic)، تجربه عامل به اپيزودهايي تقسيم مي‌گردد. هر اپيزود شامل درک و عمل عامل است. کيفيت اعمال آن تنها به خود اپيزود وابسته است. محيط‌هاي اپيزودي بسيار ساده‌ترند زيرا عامل نبايد به جلوتر فکر کند.

اسلاید 62: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )62 ايستا در مقابل پويا محيط پويا: محيطي که در حين سنجيدن عامل تغيير مي‌کند.محيط نيمه‌پويا: محيطي که با گذر زمان تغيير نمي‌کند اما امتياز کارايي تغيير مي‌کند.محيط‌هاي ايستا براي کار ساده هستند زيرا عامل نياز به نگاه‌کردن به دنيا در حين تصميم‌گيري عملي نداشته و همچنين در مورد گذر زمان نيز نگران نمي‌باشد.

اسلاید 63: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )63 گسسته در مقابل پيوسته محيط گسسته: اگر تعداد محدود و مجزا از ادراک و اعمال بوضوح تعريف شده باشد. - بازي شطرنج گسسته است. - رانندگي تاکسي پيوسته است. سخت‌ترين حالت در بين حالات موجود براي محيط:غير قابل دسترسي، غير اپيزوديک، پويا و پيوسته

اسلاید 64: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )64مثال‌هايي از انواع محيط و ويژگي‌هاي آنها

اسلاید 65: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )65عاملهاي هوشمندساختار عاملهابرنامه + معماري = عاملکار هوش مصنوعي طراحي برنامه عامل است که تابع عامل را پياده سازي ميکند

اسلاید 66: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )66براي مثال، 4 عامل را مورد بررسي قرار مي دهيم: عامل‌هاي واکنشي ساده عامل‌هايي که اثرات دنيا را حفظ مي‌کنند (مدل گرا) عامل‌هاي هدف‌گرا عامل‌هاي سودمند عامل های يادگيرنده

اسلاید 67: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )67عاملهاي واکنشي سادهعاملهاي هوشمندعاملمحيطحسگرهاجهان چگونه استمحرکهاقانونشرط عملاکنون چه عملي بايد انجام دهماين عاملها فعاليت را بر اساس درک فعلي و بدون در نظر گرفتن سابقه ادراک، انتخاب ميکندبه خاطر حذف سابقه ادراک برنامه عامل در مقايسه با جدول آن بسيار کوچک است(جدول خيلي بزرگ ولي برنامه در مقابل آن کوچک)انتخاب فعاليت بر اساس يکسري قوانين موقعيت شرطي انجام ميشود

اسلاید 68: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )68عامل‌هاي واکنشي سادهدر اينجا جدول رجوع بايد مورد توجه قرار گرفته و فيلدهاي مختلف آن توسط اطلاعات ورودي پر شود.اتصالاتي (واکنش‌هايي) وجود دارند که انسان‌ها بسياري از آنها را دارا بوده:برخي از آنها قابل يادگيري و برخي ديگر غريزي است.مربع مستطيل: نشان‌دهنده وضعيت داخلي جاري فرايند تصميم‌گيري عاملبيضي: نشان‌دهنده وضعيت اطلاعات پس‌زمينه

اسلاید 69: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )69عاملهاي هوشمندfunction REFLEX-VACUUM-AGENT ([location, status]) return an actionif status == Dirty then return Suckelse if location == A then return Rightelse if location == B then return Left مثالي از عامل واکنشي ساده در دنياي جاروبرقيتصميم گيري آن بر اساس مکان فعلي و کثيف بودن آن مکان صورت ميگيردانتخاب فعاليت بر اساس موقعيت شرطي:If dirty then suckT

اسلاید 70: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )70عاملهاي هوشمندعاملهاي واکنشي مدل گراعاملمحيطحسگرهاجهان چگونه استمحرکهاقانونشرط عملاکنون چه عملي بايد انجام دهماستفاده از دانش “چگونگي عملکرد جهان” که مدل نام داردعامل بخشي از دنيايي را که فعلا ميبيند رديابي ميکندعامل بايد حالت داخلي را ذخيره کند که به سابقه ادراک بستگي دارددر هر وضعيت, عامل ميتواند توصيف جديدي از جهان را کسب کندحالتجهان چگونه تکامل مي يابدکار فعاليت چيست

اسلاید 71: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )71عامل‌هايي که اثرات دنيا را حفظ مي‌کننداز آنجايي ناشي مي‌شود که حسگرها نمي‌توانند دسترسي کامل به وضعيت دنيا را به وجود آورند.در چنين شرايطي، عامل ممکن است نيازمند دستکاري برخي اطلاعات وضعيت داخلي باشد تا از طريق آن تمايز بين وضعيت‌هاي دنيا که در ظاهر ورودي ادراکي يکساني مي‌کنند ولي در واقع معني کاملاً متفاوتي دارند را ميسر سازد.

اسلاید 72: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )72بهنگام‌سازي اطلاعات وضعيت داخلي همزمان با گذر زمان نيازمند دو نوع دانش کد شده در برنامه عامل است.اول: نيازمند آنيم که برخي اطلاعات درباره چگونگي تغيير جهان مستقل از عامل را داشته باشيم.دوم: نيازمند اطلاعات درباره اعمال خود هستيم که بر روي دنيا اثرگذار است.

اسلاید 73: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )73عامل‌هاي هدف گرا:دانستن درباره وضعيت کنوني محيط همواره براي تصميم‌گيري عمل نمي‌تواند کافي باشد.به همان گونه که عامل نيازمند شرح وضعيت جاري است، به نوعي نيازمند اطلاعات هدف(goal) مي‌باشد که توضيح موقعيت مطلوب است.

اسلاید 74: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )74عاملهاي هوشمندعاملهاي هدف گراعاملمحيطحسگرهاجهان چگونه استمحرکهااهدافاکنون چه عملي بايد انجام دهمحالتجهان چگونه تکامل مي يابدکار فعاليت چيستاين عامل علاوه بر توصيف حالت فعلي، براي انتخاب موقعيت مطلوب نيازمند اطلاعات هدف نيز ميباشدجست و جو و برنامه ريزي، دنباله اي از فعاليتها را براي رسيدن عامل به هدف، پيدا ميکنداين نوع تصميم گيري همواره آينده را در نظر دارد و با قوانين شرط عمل تفاوت دارداين نوع عامل کارايي چنداني ندارد، اما قابليت انعطاف بيشتري دارداگر فعاليت A را انجام دهم چه خواهد شد

اسلاید 75: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )75برنامه‌ عامل مي‌تواند اين اطلاعات را با اطلاعاتي درباره نتايج اعمال ممکن (همانند اطلاعاتي که در عامل واکنش براي بهنگام‌سازي وضعيت داخلي استفاده شد) ترکيب نموده تا اعمال مناسب را براي دسترسي به هدف انتخاب نمايد.در مواقعي ساده است: که رضايت از هدف بلافاصله از عمل واحد توليد گردد.در مواقعي پيچيده است: که عامل بايد دنباله‌هاي طولاني را در نظرگرفته تا راهي براي دستيابي به هدف پيدا کند.در مواقع پيچيده، جستجو و برنامه‌ريزي به يافتن دنباله اعمال منجر خواهند شد.

اسلاید 76: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )76تفاوت عامل‌هاي واکنشي و هدف‌گرا:در طراحي عامل‌هاي واکنشي طراح براي حالات متفاوت عملي درست را پيش محاسبه مي‌کند. در عامل‌هاي هدف‌گرا، عامل مي‌تواند دانش خود را در مورد چگونگي واکنش بهنگام سازد.

اسلاید 77: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )77تفاوت عامل‌هاي واکنشي و هدف‌گرا: براي عامل واکنشي ما مجبور به دوباره نويسي تعداد زيادي قوانين شرط –عمل خواهيم بود.عامل هدف‌گرا نسبت به رسيدن به مقاصد متفاوت انعطاف پذير است.بسادگي با تعيين يک هدف تازه، مي‌توانيم عامل هدف‌گرا را به رفتار تازه برسانيم.

اسلاید 78: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )78عامل‌هاي سودمند:اهداف به تنهايي براي توليد رفتار با کيفيت بالا کافي نيستند. ملاک کارايي عمومي بايد مقايسه‌اي بين وضعيت‌هاي دنياي متفاوت (يا دنباله‌ حالات) را بر پايه چگونگي رضايت عامل در صورت حصول هدف بدهد.بنابراين اگر يک وضعيت دنيا به ديگري ترجيح داده مي‌شود، آنگاه آن براي عامل سودمند‌تر خواهد بود

اسلاید 79: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )79عاملهاي هوشمندعاملهاي سودمندعاملمحيطحسگرهاجهان چگونه استمحرکهاسودمنداکنون چه عملي بايد انجام دهمحالتجهان چگونه تکامل مي يابدکار فعاليت چيستاين عامل براي اهداف مشخص، راه هاي مختلفي دارد، که راه حل بهتر براي عامل سودمندتر است.تابع سودمندي، حالت يا دنباله اي از حالتها را به يک عدد حقيقي نگاشت ميکند که درجه رضايت را توصيف مِيکند.وقتي اهداف متضاد باشند، بعضي از آنها برآورده ميشونداگر هيچيک از اهداف به طور قطعي قابل حصول نباشند، احتمال موفقيت با اهميت هدف مقايسه ميشوداگر فعاليت A را انجام دهم چه خواهد شددر چنين حالتي چقدر رضايت دارم

اسلاید 80: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )80سودمندي: تابعي است که يک وضعيت را به عدد حقيقي نگاشت مي‌دهد، که درجه رضايت مربوط را تشريح مي‌کند. مشخصات کامل تابع سودمندي امکان تصميم‌گيري منطقي را براي دو نوع حالتي که هدف مشکل دارد، اجازه مي‌دهد.زماني که اهداف متناقص وجود دارند. زماني که چندين هدف دارند که عامل مي‌تواند آنها را هدف قرار دهد و هيچکدام از آنها با قطعيت قابل حصول نيست.

اسلاید 81: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )81عاملهاي هوشمندعاملهاي يادگيرندهعاملحسگرهامحرکها عنصرِِيادگيرنده مسئول ايجاد بهبودهاعنصر کارايي مسئول انتخاب فعاليتهاي خارجيمنتقد مشخص ميکند که يادگيرنده با توجه به استانداردهاي کارايي چگونه عمل ميکندمولد مسئله مسئول پيشنهاد فعاليتهايي است که منجر به تجربيات آموزنده جديدي ميشودمحيطعنصر کاراييمنتقدعنصر يادگيرندهمولد مسئلهاستاندارد کاراييبازخورداهداف يادگيريتغييراتدانش

اسلاید 82: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )82هوش مصنوعيفصل سومحل مسئله با جستجو

اسلاید 83: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )83هوش مصنوعي Artificial Intelligenceفهرستعاملهاي حل مسئلهمسئلهاندازه گيري کارايي حل مسئلهجستجوي ناآگاهانهاجتناب از حالتهاي تکراريجستجو با اطلاعات ناقص

اسلاید 84: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )84حل مسئله با جستجوعاملهاي حل مسئلهچهار گام اساسي براي حل مسائلفرموله کردن هدف: وضعيتهاي مطلوب نهايي کدامند؟فرموله کردن مسئله: چه فعاليتها و وضعيتهايي براي رسيدن به هدف موجود است؟جستجو: انتخاب بهترين دنباله از فعاليتهايي که منجر به حالاتي با مقدار شناخته شده ميشود.اجرا: وقتي دنباله فعاليت مطلوب پيدا شد، فعاليتهاي پيشنهادي آن ميتواند اجرا شود.

اسلاید 85: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )85يک نوع عامل هدفگرا، عامل حل مسئله ناميده مي‌شود.عامل‌هاي حل مسئله توسط يافتن ترتيب عمليات تصميم مي‌گيرند که چه انجام دهند تا آنها را به حالت‌هاي مطلوب سوق دهد.

اسلاید 86: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )86عامل‌هاي حل مسئله عامل‌هاي هوشمند به طريقي عمل مي‌کنند که محيط مستقيماً به داخل دنباله حالت‌هايي وارد شود که معيار کارآرايي را افزايش مي‌دهند. عمليات به گونه‌اي ساده‌سازي مي‌شوند که عامل قادر باشد تا هدفي را قبول کرده و به آن برسد. الگوريتم جستجو مسئله‌اي را به عنوان ورودي دريافت نموده و راه‌حلي را به صورت دنباله عمليات بر مي‌‌گرداند.

اسلاید 87: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )87چهار نوع اساسي از مسائل وجود دارند: مسائل تک حالته (Single-state) مسائل چند حالته (Multiple-state) مسائل احتمالي (Contingency) مسائل اکتشافي (Exploration)

اسلاید 88: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )88دانش و انواع مسئلهدنياي مکش (جاروبرقي):اگر دنيا حاوي دو محل باشد:هر محل ممکن است که شامل خاک باشد و يا نباشد و عامل ممکن است که در يک محل يا ديگر محل‌ها باشد؛ که داراي هشت حالت متفاوت خواهد بود.هدف تميز کردن تمام خاک‌هاست که در اينجا معادل با مجموعه حالت‌ {8و 7} است.

اسلاید 89: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )89مدل‌هاي مختلف براي مسئله جاروبرقي:- مدل تک حالته:حس‌گرهاي عامل به آن اطلاعات کافي مي‌دهند تا وضعيت دقيق مشخص شود. (دنيا قابل دسترسي است). عامل مي‌تواند محاسبه کند که کدام وضعيت پس از هر دنباله از عمليات قرار خواهد گرفت.

اسلاید 90: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )90- مدل چند حالته:عامل تمام اثرهاي عملياتش را مي‌داند اما دسترسي به حالت دنيا را محدود کرده است.زماني که دنيا تماماً قابل دسترسي نيست عامل بايد در مورد مجموعه حالت‌هايي که ممکن است به آن برسد استدلال کند.

اسلاید 91: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )91- مدل احتمالي:با اين مدل حل مسئله، حس‌گرهايي را در طول فاز اجرايي نياز داريم. عامل اکنون بايد تمام درخت عملياتي را بر خلاف دنباله عملياتي منفرد، محاسبه کند. که به طور کلي هر شاخه درخت، با يک امکان احتمالي که از آن ناشي مي‌شود، بررسي مي‌شود.

اسلاید 92: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )92 مدل اکتشافي: عاملي که هيچ اطلاعاتي در مورد اثرات عملياتش ندارد. در اين حالت، عامل بايد تجربه کند و به تدريج کشف کند که چه عملياتي بايد انجام شود و چه وضعيت‌هايي وجود دارند. اين روش يک نوع جستجو است.اگر عامل نجات يابد، «نقشه‌اي» از محيط را ياد مي‌گيرد که مي‌تواند مسائل بعدي را حل کند.

اسلاید 93: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )93حل مسئله با جستجوجستجو با اطلاعات ناقصمسئله هاي فاقد حسگر: اگر عامل فاقد حسگر باشد، ميتواند در يکي از چند حالت اوليه باشد و هر فعاليت ميتواند آن را به يکي از چند حالت جانشين ببردمسئله هاي اقتضايي: اگر محيط به طور جزئي قابل مشاهده باشد يا اگر فعاليتها قطعي نباشد، ادراکات عامل، پس از هر عمل، اطلاعات جديدي را تهيه ميکنند. هر ادراک ممکن، اقتضايي را تعريف ميکند که بايد براي آن برنامه ريزي شودمسائل خصمانه: اگرعدم قطعيت در اثر فعاليتهاي عامل ديگري بوجود آيد، مسئله را خصمانه گويندمسئله هاي اکتشافي: وقتي حالتها و فعاليتهاي محيط ناشناخته باشند، عامل بايد سعي کند آنها را کشف کند. مسئله هاي اکتشافي را ميتوان شکل نهايي مسئله هاي اقتضايي دانست

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

اسلاید 95: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )95حل مسئله با جستجودنياي جاروبرقي فاقد حسگرعامل بايد راجع به مجموعه هاي حالتي که ميتواند به آنها برسد استدلال کند. اين مجموعه از حالتها را حالت باور گوييم.اگر فضاي حالت فيزيکي داراي s حالت باشد فضاي حالت باور 2^s حالت باور خواهد داشت.

اسلاید 96: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )96براي تعريف يک مسئله موارد زير نياز داريم: وضعيت آغازين (initial state) که عامل خودش از بودن در آن آگاه است. مجموعه‌اي از عمليات ممکن، که براي عامل قابل دسترسي باشد. آزمون هدف (goal test)، که عامل مي‌تواند در يک تعريف وضعيت منفرد آن را تقاضا کند تا تعيين گردد که آن حالت، وضعيت هدف است يا خير. تابع هزينه مسير، تابعي است که براي هر مسير، هزينه‌اي را در نظر مي‌گيرد؛ و با حرف g مشخص مي‌شود.هزينه يک سفر= مجموع هزينه‌هاي عمليات اختصاصي در طول مسير

اسلاید 97: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )97براي حل مسئله چند حالته، فقط به يک اصلاح جزئي نياز داريم:يک مسئله شامل: يک مجموعه حالت اوليه مجموعه‌اي از عملگرهاي ويژه براي هر عمل به گونه‌اي که از هر وضعيت داده شده مجموعه‌اي حالات رسيده شده و يک آزمون هدف و تابع هزينه مسير را معين کند.

اسلاید 98: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )98يک عملگر:توسط اجتماع نتايج اعمال عملگر در هر وضعيت مجموعه، به کار برده مي‌شود.يک مسير: مجموعه حالات را مرتبط مي‌کند.يک راه حل:مسيري است که به مجموعه‌اي از حالات که تمام آنها، وضعيت هدف هستند، سوق مي‌دهند.

اسلاید 99: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )99اندازه‌گيري کارايي حل مسئله:کارايي يک جستجو، حداقل از سه طريق مي‌تواند اندازه‌گيري شود:آيا اين جستجو راه حلي پيدا مي‌کند؟آيا راه حلي مناسبي است؟هزينه جستجو از نظر زماني و حافظه مورد نياز براي يافتن راه حل چيست؟ مجموع هزينه جستجو= هزينه مسير + هزينه جستجوعامل بايد تصميم بگيرد که چه منابعي را فداي جستجو و چه منابعي را صرف اجرا کند.

اسلاید 100: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )100حل مسئله با جستجومثال: نقشه روماني

اسلاید 101: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )101حل مسئله با جستجوصورت مسأله: رفتن از آراد به بخارستفرموله کردن هدف: رسيدن به بخارستفرموله کردن مسئله: وضعيتها: شهرهاي مختلففعاليتها: حرکت بين شهرهاجستجو: دنباله اي از شهرها مثل:آراد، سيبيو، فاگارس، بخارستاين جستجو با توجه به کم هزينه ترين مسير انتخاب ميشودمثال: نقشه روماني

اسلاید 102: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )102حل مسئله با جستجومسئلهحالت اوليه: حالتي که عامل از آن شروع ميکند. در مثال روماني: شهر آراد n(Arad)تابع جانشين: توصيفي از فعاليتهاي ممکن که براي عامل مهيا است. در مثال روماني:Zerind,Sibui,Timisoara} S(Arad)={فضاي حالت: مجموعه اي از حالتها که از حالت اوليه ميتوان به آنها رسيد. در مثال روماني: کليه شهرها که با شروع از آراد ميتوان به آنها رسيدتابع جانشين + حالت اوليه = فضاي حالت

اسلاید 103: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )103حل مسئله با جستجوآزمون هدف: تعيين ميکند که آيا حالت خاصي، حالت هدف است يا خيرهدف صريح: در مثال روماني، رسيدن به بخارستهدف انتزاعي: در مثال شطرنج، رسيدن به حالت کيش و ماتمسير: دنباله اي از حالتها که دنباله اي از فعاليتها را به هم متصل ميکند. در مثال روماني: Arad, Sibiu, Fagaras يک مسير استهزينه مسير: براي هر مسير يک هزينه عددي در نظر ميگيرد. در مثال روماني: طول مسير بين شهرها بر حسب کيلومترراه حل مسئله مسيري از حالت اوليه به حالت هدف است راه حل بهينه کمترين هزينه مسير را دارد

اسلاید 104: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )104حل مسئله با جستجومثال: دنياي جارو برقيحالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.لذا 8 = 2^2* 2حالت در اين جهان وجود داردحالت اوليه: هر حالتي ميتواند به عنوان حالت اوليه طراحي شودتابع جانشين: حالتهاي معتبر از سه عمليات: راست، چپ، مکشآزمون هدف: تميزي تمام مربعهاهزينه مسير: تعداد مراحل در مسير

اسلاید 105: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )105حل مسئله با جستجومثال: دنياي جارو برقيحالتها: دو مکان که هر يک ممکن است کثيف يا تميز باشند.لذا 8 = 2^2* 2حالت در اين جهان وجود داردحالت اوليه: هر حالتي ميتواند به عنوان حالت اوليه طراحي شودتابع جانشين: حالتهاي معتبر از سه عمليات: راست، چپ، مکشآزمون هدف: تميزي تمام مربعهاهزينه مسير: تعداد مراحل در مسير

اسلاید 106: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )106حل مسئله با جستجومثال: معماي8حالتها: مکان هر هشت خانه شماره دار و خانه خالي در يکي از 9 خانهحالت اوليه: هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفتتابع جانشين: حالتهاي معتبر از چهار عمل، انتقال خانه خالي به چپ، راست، بالا يا پايينآزمون هدف: بررسي ميکند که حالتي که اعداد به ترتيب چيده شده اند(طبق شکل روبرو) رخ داده يا نههزينه مسير: برابر با تعداد مراحل در مسير

اسلاید 107: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )107حل مسئله با جستجومثال: معماي8حالتها: مکان هر هشت خانه شماره دار و خانه خالي در يکي از 9 خانهحالت اوليه: هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفتتابع جانشين: حالتهاي معتبر از چهار عمل، انتقال خانه خالي به چپ، راست، بالا يا پايينآزمون هدف: بررسي ميکند که حالتي که اعداد به ترتيب چيده شده اند(طبق شکل روبرو) رخ داده يا نههزينه مسير: برابر با تعداد مراحل در مسير

اسلاید 108: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )108حل مسئله با جستجومثال: مسئله 8 وزيرفرمول بندي افزايشيحالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت استحالت اوليه: هيچ وزيري در صفحه نيستتابع جانشين: وزيري را به خانه خالي اضافه ميکندآزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرنددر اين فرمول بندي بايد 14^10*3 دنباله ممکن بررسي ميشود

اسلاید 109: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )109حل مسئله با جستجومثال: مسئله 8 وزيرفرمول بندي افزايشيحالتها: هر ترتيبي از 0 تا 8 وزير در صفحه، يک حالت استحالت اوليه: هيچ وزيري در صفحه نيستتابع جانشين: وزيري را به خانه خالي اضافه ميکندآزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند

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

اسلاید 111: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )111حل مسئله با جستجومثال: مسئله 8 وزيرفرمول بندي حالت کاملحالتها: چيدمان n وزير (0≤ n≤ 8) ، بطوريکه در هر ستون از n ستون سمت چپ، يک وزير قرار گيرد و هيچ دو وزيري بهم گارد نگيرندحالت اوليه: با 8 وزير در صفحه شروع ميشودتابع جانشين: وزيري را در سمت چپ ترين ستون خالي قرار ميدهد، بطوري که هيچ وزيري آن را گارد ندهدآزمون هدف: 8وزير در صفحه وجود دارند و هيچ کدام به يکديگر گارد نميگيرند

اسلاید 112: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )112حل مسئله با جستجواندازه گيري کارايي حل مسئلهکامل بودن: آيا الگوريتم تضمين ميکند که در صورت وجود راه حل، آن را بيابد؟بهينگي: آيا اين راهبرد، راه حل بهينه اي را ارائه ميکند.پيچيدگي زماني: چقدر طول ميکشد تا راه حل را پيدا کند؟تعداد گره هاي توليد شده در اثناي جستجوپيچيدگي فضا: براي جستجو چقدر حافظه نياز دارد؟حداکثر تعداد گره هاي ذخيره شده در حافظه

اسلاید 113: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )113حل مسئله با جستجواندازه گيري کارايي حل مسئلهکامل بودن: آيا الگوريتم تضمين ميکند که در صورت وجود راه حل، آن را بيابد؟بهينگي: آيا اين راهبرد، راه حل بهينه اي را ارائه ميکند.پيچيدگي زماني: چقدر طول ميکشد تا راه حل را پيدا کند؟تعداد گره هاي توليد شده در اثناي جستجوپيچيدگي فضا: براي جستجو چقدر حافظه نياز دارد؟حداکثر تعداد گره هاي ذخيره شده در حافظه

اسلاید 114: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )114حل مسئله با جستجوجستجوي ناآگاهانهناآگاهي اين است که الگوريتم هيچ اطلاعاتي غير از تعريف مسئله در اختيار ندارداين الگوريتمها فقط ميتواند جانشينهايي را توليد و هدف را از غير هدف تشخيص دهندراهبردهايي که تشخيص ميدهد يک حالت غير هدف نسبت به گره غير هدف ديگر، اميد بخش تر است، جست و جوي آگاهانه يا جست و جوي اکتشافي ناميده ميشود.راهبردهاجست و جوي عرضيجست و جوي عمقيجست و جوي عميق کننده تکراريجست و جوي هزينه يکنواختجست و جوي عمقي محدودجست و جوي دو طرفه

اسلاید 115: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )115حل مسئله با جستجوجستجوي عرضيABCDEFGHIJKLNMOPQ

اسلاید 116: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )116 حل مسئله با جستجوجستجوي عرضيکامل بودن: بلهبهينگي: بله (مشروط)در صورتي بهينه است که هزينه مسير، تابعي غير نزولي از عمق گره باشد.(مثل وقتي که فعاليتها هزينه يکساني دارند)پيچيدگي زماني:پيچيدگي فضا:کامل بودن:بهينگي: بله (مشروط)

اسلاید 117: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )117حل مسئله با جستجوجستجوي هزينه يکنواختABCDEFGHIJKLNMOPQ113اين جستجو گره n را با کمترين هزينه مسير بسط ميدهد

اسلاید 118: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )118حل مسئله با جستجوکامل بودن: بلههزينه هر مرحله بزرگتر يا مساوي يک مقدار ثابت و مثبت ε باشد.(هزينه مسير با حرکت در مسير افزايش مي يابد)بهينگي: بله هزينه هر مرحله بزرگتر يا مساوي ε باشد پيچيدگي زماني:پيچيدگي فضا:جستجوي هزينه يکنواختکامل بودن:بهينگي:

اسلاید 119: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )119حل مسئله با جستجوجستجوي عمقي234567ABCDEFGHIJKLNMOPQ

اسلاید 120: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )120حل مسئله با جستجوکامل بودن: خيراگر زير درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل باشد، جستجو هرگز خاتمه نمي يابد.بهينگي: خير پيچيدگي زماني:پيچيدگي فضا:جستجوي عمقيکامل بودن:بهينگي:

اسلاید 121: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )121حل مسئله با جستجوجستجوي عمقي محدودABCDEFGHIJKLNMOPQمسئله درختهاي نامحدود ميتواند به وسيله جست و جوي عمقي با عمق محدود L بهبود يابد

اسلاید 122: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )122حل مسئله با جستجوجستجوي عمقي محدودکامل بودن: خيراگر L<d و سطحي ترين هدف در خارج از عمق محدود قرار داشته باشد، اينراهبرد کامل نخواهد بود.بهينگي: خير اگر L>d انتخاب شود، اين راهبرد بهينه نخواهد بود.پيچيدگي زماني:پيچيدگي فضا:کامل بودن:بهينگي:

اسلاید 123: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )123حل مسئله با جستجوجستجوي عميق کننده تکراريABCDEFGHIJKLNMOPQ

اسلاید 124: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )124حل مسئله با جستجوجستجوي عميق کننده تکراريABCDEFGHIJKLNMOPQ

اسلاید 125: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )125حل مسئله با جستجوجستجوي عميق کننده تکراريABCDEFGHIJKLNMOPQSR

اسلاید 126: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )126حل مسئله با جستجوجستجوي عميق کننده تکراريکامل بودن: بلهدر صورتي که فاکتور انشعاب محدود باشدبهينگي: بله وقتي که هزينه مسير، تابعي غير نزولي از عمق گره باشدپيچيدگي زماني:پيچيدگي فضا:کامل بودن:بهينگي:

اسلاید 127: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )127حل مسئله با جستجوجستجوي دو طرفهانجام دو جست و جوي همزمان، يکي از حالت اوليه به هدف و ديگري از هدف به حالت اوليه تا زماني که دو جست و جو به هم برسند

اسلاید 128: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )128حل مسئله با جستجوجستجوي دو طرفهکامل بودن: بلهاگر هر دو جستجو، عرضي باشند و هزينه تمام مراحل يکسان باشدبهينگي: بله اگر هر دو جستجو، عرضي باشند و هزينه تمام مراحل يکسان باشدپيچيدگي زماني:پيچيدگي فضا:کامل بودن:بهينگي:

اسلاید 129: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )129حل مسئله با جستجواجتناب از حالتهاي تکراريوجود حالتهاي تکراري در يک مسئله قابل حل، ميتواند آن را به مسئله غير قابل حل تبديل کند

اسلاید 130: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )130اجتناب از حالات تکراري:براي مسائل زيادي، حالات تکراري غيرقابل اجتناب هستند. اين شامل تمام مسائلي مي‌شود که عملگرها قابل وارونه شدن باشند، مانند مسائل مسيريابي و کشيش‌ها و آدمخوارها.

اسلاید 131: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )131سه راه براي حل مشکل حالات تکراري براي مقابله با افزايش مرتبه و سرريزي فشار کار کامپيوتر وجود دارد: به حالتي که هم اکنون از آن آمده‌ايد، برنگرديد. داشتن تابع بسط (يا مجموعه عملگرها) از توليد مابعدهايي که مشابه حالتي هستند که در آنجا نيز والدين اين گره‌ها وجود دارند، جلوگيري مي‌کند. از ايجاد مسيرهاي دوار بپرهيزيد. داشتن تابع بسط (يا مجموعه عملگرها) از توليد مابعدهاي يک گره که مشابه اجداد آن گره است، جلوگيري مي‌کند. حالتي را که قبلاً توليد شده است، مجدداً توليد نکنيد. اين مسئله باعث مي‌شود که هر حالت در حافظه نگهداري شود، پيچيدگي فضايي O(bd) داشته باشد. بهتر است که به O(s) توجه کنيد که s تعداد کل حالات در فضاي حالت ورودي است.

اسلاید 132: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )132Cryptarithmetic :در مسائل کريپتاريتمتيک، حروف به جاي ارقام مي‌نشينند و هدف يافتن جايگزيني از اعداد براي حروف است که مجموع نتيجه از نظر رياضي درست باشد. معمولاً هر حرف بايد به جاي يک رقم مختلف بنشينند.مثال:FORTY+ TEN+ TEN----------SIXTY29786+ 850+ 850----------31486F=2, O=9, R=7, etc.

اسلاید 133: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )133يک فرمول ساده:حالات: يک معماي Cryptarithmetic با چند حروف جايگزين شده توسط ارقام. عملگرها: وقوع يک حروف را با يک رقم جايگزين کنيد که قبلاً در معما ظاهر نشده باشد. آزمون هدف: معما فقط شامل ارقام است و يک مجموع صحيح را بر مي‌گرداند. هزينه مسير: صفر- تمام راه حل‌هاي صحيح است.

اسلاید 134: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )134مي‌خواهيم که از تبديل جايگزيني‌هاي مشابه اجتناب کنيم: قبول يک ترتيب ثابت مانند ترتيب الفبايي. هر کدام که بيشترين محدوديت جايگزيني را دارد، انتخاب کنيم؛ يعني حرفي که کمترين امکان مجاز را دارند، محدوديت‌هاي معما را مي‌دهد.

اسلاید 135: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )135دنياي مکش:مسئله تک حالته: عامل از جاي خودش اطلاع دارد و تمام مکان‌هاي آلوده را مي‌شناسد و دستگاه مکنده ما درست کار مي‌کند.حالات: يکي از 8 حالت نشان داده شده.عملگرها: حرکت به چپ، حرکت به راست، عمل مکش. آزمون هدف: هيچ خاکي در چهار گوش‌ها نباشد. هزينه مسير: هر عمل ارزش 1 دارد.

اسلاید 136: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )136

اسلاید 137: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )137مسئله چند حالته: عامل داراي حسگر نمي‌باشد. مجموعه وضعيت‌ها : زير مجموعه‌اي از حالات.عملگرها: حرکت به چپ، حرکت به راست، عمل مکش. آزمون هدف: تمام حالات در مجموعه حالت‌ها فاقد خاک باشند. هزينه مسير: هر عمل هزينه 1 دارد.

اسلاید 138: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )138مسئله کشيش‌ها و آدمخوارها:سه کشيش و سه آدم خوار در يک طرف رودخانه قرار دارند و هم چنين قايقي که قادر است يک يا دو نفر را حمل کند. راهي را بيابيد که هر نفر به سمت ديگر رودخانه برود، بدون آنکه تعداد کشيش‌ها در يکجا کمتر از آدم خوارها شود.

اسلاید 139: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )139حالات: يک حالت شامل يک دنبالة مرتب شده از عدد است که تعداد کشيش‌ها، تعداد آدمخوارها و محل قايق در ساحلي از رودخانه که از آنجا مسئله شروع شده را نمايش مي‌دهد.عملگرها: از هر حالت، عملگرهاي ممکن يک کشيش، يک آدمخوار، دو کشيش، دو آدمخوار، يا يکي از هر کدام را در قايق جا مي‌دهند. آزمون هدف: رسيدن به حالت(0و 0 و 0).هزينه مسير: تعداد دفعات عبور از رودخانه.

اسلاید 140: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )140مسيريابي:الگوريتم‌هاي مسير يابي کاربردهاي زيادي دراند، مانند مسيريابي در شبکه‌هاي کامپيوتري، سيستم‌هاي خودکار مسافرتي و سيستم‌هاي برنامه‌نويسي مسافرتي هوايي.مسائل دنياي واقعي

اسلاید 141: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )141مسائل فروشنده دوره گرد و تور :مسئله فروشنده دوره گرد مسئله مشهوري است که در آن هر شهر حداقل يکبار بايد ملاقات شود هدف يافتن کوتاهترين مسير است. علاوه بر مکان عامل، هر حالت بايد مجموعه شهرهايي را که عامل ملاقات کرده، نگه دارد. علاوه بر برنامه‌ريزي صفر براي فروشنده دوره‌گرد، اين الگوريتم‌ها براي اعمالي نظير برنامه‌ريزي حرکات مته خوردکار سوراخ‌کننده برد مدار استفاده مي‌شود.

اسلاید 142: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )142طرح VISI :ابزار طراحي کمکي کامپيوتري در هر فازي از پردازش استفاده مي‌شود دو وظيفه بسيار مشکل عبارتند از: Channel routing Cell layoutکه بعد از اينکه ارتباطات و اتصالات مدار کامل شد، اين دو قسمت انجام مي‌شوند.

اسلاید 143: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )143هدف طراحي مداري روي تراشه است که کمترين مساحت و طول اتصالات و بيشترين سرعت را داشته باشد.هدف قرار دادن سلول‌ها روي تراشه به گونه‌اي است که آنها روي هم قرار نگيرند و بنابراين فضايي نيز براي سيم‌هاي ارتباطي وجود دارد که بايد بين سلول‌ها قرار گيرند.کانال‌يابي، مسير ويژه‌اي را براي هر سيم که از فواصل بين سلول‌ها استفاده مي‌کند، پيدا مي‌کند.

اسلاید 144: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )144هدايت ربات: يک ربات مي‌تواند در يک فضاي پيوسته با يک مجموعه نامحدودي از حالات و عمليات ممکن حرکت کند. ربات‌هاي واقعي بايد قابليت تصحيح اشتباهات را در خواندن حسگرها و کنترل موتور داشته باشند.

اسلاید 145: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )145خط توليد خودکار:در مسائل سرهم‌بندي، مشکل يافتن قانوني است که تکه‌هاي چند شيئي را جمع کند. اگر ترتيب نادرست انتخاب شود، راهي نيست که بتوان قسمت‌هاي بعدي را بدون از نو انجام دادن قسمت‌هاي قبلي، اضافه کرد.کنترل يک مرحله در دنباله، يک مسئله جستجوي پيچيدة هندسي است که ارتباط نزديکي با هدايت ربات دارد. از اين رو توليد مابعدهاي مجاز گران‌ترين قسمت دنباله سرهم‌بندي است و استفاده از الگوريتم‌هاي آگاهانه براي کاهش جستجو، ضروري است.

اسلاید 146: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )146هوش مصنوعيفصل چهارمجست و جوي آگاهانه و اکتشاف

اسلاید 147: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )147هوش مصنوعي Artificial Intelligenceفهرستمتدهاي جست و جوي آگاهانهيادگيري براي جست و جوي بهترجست و جوي محلي و بهينه سازيجست و جوي محلي در فضاهاي پيوستهعاملهاي جست و جوي Online

اسلاید 148: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )148جست و جوي آگاهانه و اکتشافمتدهاي جستجوي آگاهانهبهترين جستجوحريصانهA*IDA*RBFSMA* و SMA*جستجوي محلي و بهينه سازيتپه نورديشبيه سازي حرارتپرتو محليالگوريتمهاي ژنتيک

اسلاید 149: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )149جستجوي بهترين:اين استراتژي به اين صورت بيان مي‌شود که در يک درخت، زماني که گره‌ها مرتب مي‌شوند، گره‌اي که بهترين ارزيابي را داشته باشد، قبل از ديگر گره‌ها بسط داده مي‌شود.هدف: يافتن راه‌حل‌هاي کم‌هزينه است، اين الگوريتم‌ها عموماً از تعدادي معيار تخمين براي هزينه راه‌حل‌ها استفاده مي‌‌کنند و سعي بر حداقل کردن آنها دارند.

اسلاید 150: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )150حداقل هزينه تخمين زده شده براي رسيدن به هدف: جستجوي حريصانهيکي از ساده‌ترين استراتژي‌هاي جستجوي بهترين، به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف است. بدين صورت که حالت گره‌اي که به حالت هدف نزديک‌تر است، ابتدا بسط داده مي‌شود.تابع کشف‌کننده: هزينه رسيدن به هدف از يک حالت ويژه مي‌تواند تخمين زده شود اما دقيقاً تعيين نمي‌شود. تابعي که چنين هزينه‌هايي را محاسبه مي‌کند تابع کشف‌کننده h ناميده مي‌شود.جستجوي حريصانه: جستجوي بهترين که h را به منظور انتخاب گره بعدي براي بسط استفاده مي‌کند، جستجوي حريصانه (greedy search) ناميده مي‌شود.

اسلاید 151: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )151ويژگي‌هاي جستجوي حريصانه: جستجوي حريصانه از لحاظ دنبال کردن يک مسير ويژه در تمام طول راه به طرف هدف، مانند جستجوي عمقي است، اما زماني که به بن‌بست مي‌رسد، برمي‌گردد. اين جستجو بهينه نيست و ناکامل است. پيچيدگي زماني در بدترين حالت براي جستجوي حريصانه O(bm)، که m حداکثر عمق فضاي جستجو است. جستجوي حريصانه تمام گره‌ها را در حافظه نگه مي‌دارد، بنابراين پيچيدگي فضاي آن مشابه پيچيدگي زماني آن است. ميزان کاهش پيچيدگي به مسئله و کيفيت تابع h بستگي دارد.

اسلاید 152: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )152جست و جوي آگاهانه و اکتشافتعاريفتابع هزينه مسير، 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)

اسلاید 153: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )153جست و جوي آگاهانه و اکتشافABCDEFGHIKMLNO3PQJWVXYZRSTU1121332323231112321113231253013231221121021312332جستجوي حريصانه

اسلاید 154: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )154جست و جوي آگاهانه و اکتشاف1ABCDEFGNO3X112111131253031322345جستجوي حريصانه

اسلاید 155: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )155جست و جوي آگاهانه و اکتشافجستجوي حريصانهAFGHIMLNOPQWVXYZRSTU1332323111232111323BC2114DE1151KJ33013231221121021312333

اسلاید 156: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )156جست و جوي آگاهانه و اکتشافجستجوي حريصانه2ABC2114DE1151KJ330113

اسلاید 157: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )157جست و جوي آگاهانه و اکتشافجستجوي حريصانهکامل بودن: خيراما اگر h = h* آنگاه جستجو کامل ميشودبهينگي: خيراما اگر h = h* آنگاه جستجو کامل ميشودپيچيدگي زماني:اما اگر h = h* آنگاهپيچيدگي فضا:اما اگر h = h* آنگاهکامل بودن:بهينگي:

اسلاید 158: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )158حداقل‌سازي مجموع هزينه مسير: جستجوي A*جستجو با هزينه يکسان، هزينه مسير، g(n) را نيز حداقل مي‌کند.با ترکيب دو تابع ارزيابي داريم:f(n) = g(n) + h(n):g(n) هزينه مسير از گره آغازين به گره n را به ما مي‌دهد.h(n): هزينه تخمين زده شده از ارزانترين مسير از n به هدف استو ما داريم:هزينه تخمين زده شده ارزانترين راه حل از طريق n = f(n)

اسلاید 159: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )159جست و جوي آگاهانه و اکتشافجستجوي 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

اسلاید 160: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )160جست و جوي آگاهانه و اکتشافجستجوي A*132A/5B/4C/42165X/014N/1O/31384F/3G/21154

اسلاید 161: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )161جست و جوي آگاهانه و اکتشافجستجوي 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

اسلاید 162: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )162جستجوي A*جست و جوي آگاهانه و اکتشافA/521345B/1C/42135D/5E/11184K/0J/13367X/014N/1O/31384F/3G/21154

اسلاید 163: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )163جستجوي 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

اسلاید 164: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )164جستجوي A*جست و جوي آگاهانه و اکتشافA/5213B/1C/921310D/5E/11184K/0J/13361

اسلاید 165: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )165جستجوي A*جست و جوي آگاهانه و اکتشافکامل بودن: بلهبهينگي: بلهپيچيدگي زماني:اما اگر h = h* آنگاهپيچيدگي فضا:اما اگر h = h* آنگاه

اسلاید 166: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )166جست و جوي آگاهانه و اکتشافABCDEFG1H1111111211001ABCDEFG1H1111113421001h ≤ h*h ≤ h*/جستجوي A*

اسلاید 167: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )167جست و جوي آگاهانه و اکتشافجستجوي A*1234ABCDEFG1H1111111211001ABCDEFG1H1111113421001123456h ≤ h*h ≤ h*/

اسلاید 168: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )168جست و جوي آگاهانه و اکتشاف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 ميباشد

اسلاید 169: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )169جست و جوي آگاهانه و اکتشافجستجوي 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

اسلاید 170: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )170جست و جوي آگاهانه و اکتشافمثال ديگر از جستجوي A*f(n)=g(n) + h(n)

اسلاید 171: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )171جست و جوي آگاهانه و اکتشافجستجوي A* در نقشه رومانيجستجوي Bucharest با شروع از Aradf(Arad) = g(Arad)+h(Arad)=0+366=366

اسلاید 172: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )172جست و جوي آگاهانه و اکتشافجستجوي 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 است

اسلاید 173: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )173جست و جوي آگاهانه و اکتشافجستجوي 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 است

اسلاید 174: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )174جست و جوي آگاهانه و اکتشافجستجوي 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 است

اسلاید 175: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )175جست و جوي آگاهانه و اکتشافجستجوي A* در نقشه رومانيََ Fagaras را باز کرده و f(n) را براي هر يک از زيربرگها محاسبه ميکنيم:f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450بهترين انتخاب شهر Pitesti !!! است

اسلاید 176: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )176جست و جوي آگاهانه و اکتشافجستجوي A* در نقشه رومانيََ Pitesti را باز کرده و f(n) را براي هر يک از زيربرگها محاسبه ميکنيم:f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418بهترين انتخاب شهر Bucharest !!! است

اسلاید 177: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )177جست و جوي آگاهانه و اکتشافجستجوي A* در نقشه روماني

اسلاید 178: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )178کشف‌کنندگي قابل قبول:تابع hاي را که هزينه‌اي بيش از تخمين براي رسيدن به هدف نداشته باشد، يک کشف‌کنندگي قابل قبول (admissible heuristic) گويند.جستجوي A*:جستجوي بهترين که f به عنوان تابع ارزياب و يک تابع h قابل قبول استفاده مي‌کند، به عنوان جستجوي A* شناخته مي‌شود.

اسلاید 179: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )179رفتار جستجوي A*نگاهي گذرا به اثبات کامل و بهينه بودن A*:مشاهده مقدماتي:تقريباً تمام کشف‌کنندگي‌هاي مجاز داراي اين ويژگي هستند که در طول هر مسيري از ريشه، هزينه f هرگز کاهش پيدا نمي‌کند.اين خاصيت براي کشف‌کنندگي، خاصيت يکنوايي (monotonicity) گفته مي‌شود.اگر يکنوا نباشد، با ايجاد يک اصلاح جزئي آن را يکنوا مي‌کنيم.

اسلاید 180: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )180بنابراين هر گره جديدي که توليد مي‌شود، بايد کنترل کنيم که آيا هزينة f اين گره از هزينه f پدرش کمتر است يا خير. اگر کمتر باشد، هزينة f پدر به جاي فرزند مي‌نشيند:بنابراين:f هميشه در طول هر مسيري از ريشه غيرکاهشي خواهد بود، مشروط بر اينکه h امکان‌پذير باشد.

اسلاید 181: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )181h*(n) : هزينه واقعي رسيدن از n به هدف است.در استفاده عملي، خطاها با هزينه مسير متناسب هستند، و سرانجام رشد نمايي هر کامپيوتر را تسخير مي‌کند. البته، استفاده از يک کشف‌کنندگي خوب هنوز باعث صرفه‌جويي زيادي نسبت به جستجوي ناآگاهانه مي‌شود.A* معمولاً قبل از اينکه دچار کمبود زمان شود، دچار کمبود فضا مي‌شود. زيرا اين جستجو تمام گره‌هاي توليد شده را در حافظه ذخيره مي‌کند.

اسلاید 182: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )182جست و جوي آگاهانه و اکتشافجستجوي اکتشافي با حافظه محدود IDA*ساده ترين راه براي کاهش حافظه مورد نياز A* استفاده از عميق کننده تکرار در زمينه جست و جوي اکتشافي است.الگوريتم عميق کننده تکرار A* IDA* در جستجوي IDA* مقدار برش مورد استفاده، عمق نيست بلکه هزينه f(g+h) است.IDA* براي اغلب مسئله هاي با هزينه هاي مرحله اي، مناسب است و از سربار ناشي از نگهداري صف مرتبي از گره ها اجتناب ميکند

اسلاید 183: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )183بهترين جستجوي بازگشتي RBFSجست و جوي آگاهانه و اکتشافساختار آن شبيه جست و جوي عمقي بازگشتي است، اما به جاي اينکه دائما به طرف پايين مسير حرکت کند، مقدار f مربوط به بهترين مسير از هر جد گره فعلي را نگهداري ميکند، اگر گره فعلي از اين حد تجاوز کند، بازگشتي به عقب برميگردد تا مسير ديگري را انتخاب کند.اين جستجو اگر تابع اکتشافي قابل قبولي داشته باشد، بهينه است.پيچيدگي فضايي آن O(bd) استتعيين پيچيدگي زماني آن به دقت تابع اکتشافي و ميزان تغيير بهترين مسير در اثر بسط گره ها بستگي دارد.

اسلاید 184: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )184جست و جوي آگاهانه و اکتشافبهترين جستجوي بازگشتي RBFSRBFS تا حدي از IDA* کارآمدتر است، اما گره هاي زيادي توليد ميکند. IDA* و RBFS در معرض افزايش تواني پيچيدگي قرار دارند که در جست و جوي گرافها مرسوم است، زيرا نميتوانند حالتهاي تکراري را در غير از مسير فعلي بررسي کنند. لذا، ممکن است يک حالت را چندين بار بررسي کنند. IDA* و RBFS از فضاي اندکي استفاده ميکنند که به آنها آسيب ميرساند. IDA* بين هر تکرار فقط يک عدد را نگهداري ميکند که فعلي هزينه f است. RBFS اطلاعات بيشتري در حافظه نگهداري ميکند

اسلاید 185: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )185جست و جوي آگاهانه و اکتشافيادگيري براي جست و جوي بهتر روشهاي جست و جوي قبلي، از روشهاي ثابت استفاده ميکردند.عامل با استفاده از فضاي حالت فراسطحي ميتواند ياد بگيرد که بهتر جست و جو کندهر حالت در فضاي حالت فرا سطحي، حالت(محاسباتي) داخليِ برنامه اي را تسخير ميکند که فضاي حالت سطح شيء، مثل روماني را جست و جو ميکندالگوريتم يادگيري فراسطحي ميتواند چيزهايي را از تجربيات بياموزد تا زيردرختهاي غير قابل قبول را کاوش نکند.هدف يادگيري، کمينه کردن کل هزينه، حل مسئله است

اسلاید 186: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )186جست و جوي آگاهانه و اکتشافتوابع اکتشافيمثال براي معماي8ميانگِين هزينه حل تقريبا 22 مرحله و فاکتور انشعاب در حدود 3 است.جست و جوي جامع تا عمق 22 : با انتخاب يک تابع اکتشافي مناسب ميتوان مراحل جستجو را کاهش داد

اسلاید 187: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )187جست و جوي آگاهانه و اکتشافدو روش اکتشافي متداول براي معماي8تعداد کاشيها در مکانهاي نادرستدر حالت شروع اکتشاف قابل قبولي است، زيرا هر کاشي که در جاي نامناسبي قرار دارد، حداقل يکبار بايد جابجا شود

اسلاید 188: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )188جست و جوي آگاهانه و اکتشافدو روش اکتشافي متداول براي معماي8مجموعه فواصل کاشيها از موقعيتهاي هدف آنهادر حالت شروعچون کاشيها نميتوانند در امتداد قطر جا به جا شوند, فاصله اي که محاسبه ميکنيم مجموع فواصل افقي و عمودي است. اين فاصله را فاصله بلوک شهر يا فاصله مانهاتان مينامند.

اسلاید 189: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )189جست و جوي آگاهانه و اکتشافدو روش اکتشافي متداول براي معماي8مجموعه فواصل کاشيها از موقعيتهاي هدف آنها قابل قبول است، زيرا هر جابجايي که ميتواند انجام گيرد، به اندازه يک مرحله به هدف نزديک ميشود.هيچ کدام از اين برآوردها، هزينه واقعي راه حل نيستهزينه واقعي 36 است

اسلاید 190: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )190جست و جوي آگاهانه و اکتشافاثر دقت اکتشاف بر کاراييفاکتور انشعاب مؤثر b*اگر تعداد گره هايي که براي يک مسئله خاص توسط A* توليد ميشود برابر با N و عمق راه حل برابر با d باشد، آن گاه b* فاکتور انشعابي است که درخت يکنواختي به عمق d بايد داشته باشد تا حاوي N+1 گره باشدفاکتور انشعاب مؤثر معمولاً براي مسئله هاي سخت ثابت استاندازه گيريهاي تجربي b* بر روي مجموعه کوچکي از مسئله ها ميتواند راهنماي خوبي براي مفيد بودن اکتشاف باشدمقدار b* در اکتشافي با طراحي خوب، نزديک 1 است

اسلاید 191: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )191جست و جوي آگاهانه و اکتشافاثر دقت اکتشاف بر کاراييهزينه جست و جوفاکتور انشعاب مؤثرميانگين گره هاي بسط يافته در جستجويIDS و A* و فاکتور انشعاب مؤثر با استفاده ازh1 و h2ITERSTIVE DEEPING SEARCH

اسلاید 192: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )192جست و جوي آگاهانه و اکتشافاثر دقت اکتشاف بر کارايياگر براي هر گره n داشته باشيم: h2(n) >= h1(n) h2 بر h1غالب استغالب بودن مستقيما به کارايي ترجمه ميشودتعداد گره هايي که با بکارگيري h2 بسط داده ميشود، هرگز بيش از بکارگيري h1 نيستهميشه بهتر است از تابع اکتشافي با مقادير بزرگ استفاده کرد، به شرطي که زمان محاسبه اکتشاف، خيلي بزرگ نباشد

اسلاید 193: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )193جست و جوي آگاهانه و اکتشافالگوريتم هاي جست و جوي محلي و بهينه سازيالگوريتم هاي قبلي، فضاي جست و جو را به طور سيستماتيک بررسي ميکنندتا رسيدن به هدف يک يا چند مسير نگهداري ميشوندمسير رسيدن به هدف، راه حل مسئله را تشکيل ميدهددر الگوريتم هاي محلي مسير رسيدن به هدف مهم نيستمثال: مسئله 8 وزيردو امتياز عمده جست و جوهاي محلياستفاده از حافظه کمکيارائه راه حلهاي منطقي در فضاهاي بزرگ و نامتناهياين الگوريتمها براي حل مسائل بهينه سازي نيز مفيدنديافتن بهترين حالت بر اساس تابع هدف

اسلاید 194: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )194جست و جوي آگاهانه و اکتشافالگوريتم هاي جست و جوي محلي و بهينه سازي

اسلاید 195: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )195جست و جوي تپه نوردي hill climbing searchجست و جوي آگاهانه و اکتشافحلقه اي که در جهت افزايش مقدار حرکت ميکند(بطرف بالاي تپه)رسيدن به بلندترين قله در همسايگي حالت فعلي، شرط خاتمه است.ساختمان داده گره فعلي، فقط حالت و مقدار تابع هدف را نگه ميداردجست و جوي محلي حريصانه نيز نام داردبدون فکر قبلي حالت همسايه خوبي را انتخاب ميکندتپه نوردي به دلايل زير ميتواند متوقف شود:بيشينه محليبرآمدگي هافلات

اسلاید 196: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )196جست و جوي آگاهانه و اکتشافانواع تپه نوردي:تپه نوردي غيرقطعي، تپه نوردي اولين انتخاب، تپه نوردي شروع مجدد تصادفيمثال: مسئله 8 وزيرمسئله 8 وزير با استفاده از فرمولبندي حالت کاملدر هر حالت 8 وزير در صفحه قرار دارندتابع جانشين: انتقال يک وزير به مربع ديگر در همان ستونتابع اکتشاف: جفت وزيرهايي که نسبت به هم گارد دارندجست و جوي تپه نوردي

اسلاید 197: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )197جست و جوي آگاهانه و اکتشافمثال جست و جوي تپه نورديالف- حالت با هزينه h=17 که مقدار h را براي هر جانشين نشان ميدهدب- کمينه محلي در فضاي حالت 8 وزير؛ h=1الفب

اسلاید 198: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )198جست و جوي آگاهانه و اکتشافجست و جوي شبيه سازي حرارتSimulated annealingتپه نوردي مرکب با حرکت تصادفيشبيه سازي حرارت: حرارت با درجه بالا و به تدريج سرد کردنمقايسه با حرکت توپتوپ در فرود از تپه به عميق ترين شکاف ميرودبا تکان دادن سطح توپ از بيشينه محلي خارج ميشودبا تکان شديد شروع(دماي زياد)بتدريج تکان کاهش(به دماي پايين تر)با کاهش زمانبندي دما به تدريج، الگوريتم يک بهينه عمومي را مي يابدگير افتادن در ماکزيمم محلی : حرکت به چند گام قبل برای فرار از ماکزيمم محلی

اسلاید 199: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )199جست و جوي آگاهانه و اکتشافجست و جوي پرتو محليبه جاي يک حالت، k حالت را نگهداري ميکندحالت اوليه: k حالت تصادفيگام بعد: جانشين همه k حالت توليد ميشوداگر يکي از جانشين ها هدف بود، تمام ميشودوگر نه بهترين جانشين را انتخاب کرده، تکرار ميکندتفاوت عمده با جستجوي شروع مجدد تصادفيدر جست و جوي شروع مجدد تصادفي، هر فرايند مستقل از بقيه اجرا ميشوددر جست و جوي پرتو محلي، اطلاعات مفيدي بين k فرايند موازي مبادله ميشودجست و جوي پرتو غيرقطعيبه جاي انتخاب بهترين k از جانشينها، k جانشين تصادفي را بطوريکه احتمال انتخاب يکي تابعي صعودي از مقدارش باشد، انتخاب ميکند

اسلاید 200: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )200جست و جوي آگاهانه و اکتشافالگوريتم هاي ژنتيکشکلي از جست و جوي پرتو غير قطعي که حالتهاي جانشين از طريق ترکيب دو حالت والد توليد ميشود

اسلاید 201: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )201الگوريتم هاي ژنتيکجست و جوي آگاهانه و اکتشافجهت اوليهتابع برازشانتخابتقاطعجهش

اسلاید 202: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )202هوش مصنوعيفصل پنجممسائل ارضاي محدوديت

اسلاید 203: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )203هوش مصنوعي Artificial Intelligenceفهرستارضاي محدوديت چيست؟جست و جوي عقبگرد براي CSPبررسي پيشروپخش محدوديت

اسلاید 204: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )204مسائل ارضاي محدوديت ارضاي محدوديت (CSP) چيست؟مجموعه متناهي از متغيرها؛ X1, X2, …, Xn مجموعه متناهي از محدوديتها؛ C1, C2, …, Cmدامنه هاي ناتهي براي هر يک از متغيرها؛DX1,DX2,…,DXn هر محدوديت Ci زيرمجموعه اي از متغيرها و ترکيبهاي ممکني از مقادير براي آن زيرمجموعه هاهر حالت با انتساب مقاديري به چند يا تمام متغيرها تعريف ميشودانتسابي که هيچ محدوديتي را نقض نکند، انتساب سازگار نام داردانتساب کامل آن است که هر متغيري در آن باشد راه حل CSP يک انتساب کامل است اگر تمام محدوديتها را برآورده کندبعضي از CSPها به راه حلهايي نياز دارند که تابع هدف را بيشينه کنند

اسلاید 205: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )205مسائل ارضاي محدوديتمثال CSP: رنگ آميزي نقشهمتغيرها: WA, NT, Q, NSW, V, SA, Tدامنه: {آبي، سبز، قرمز} = Diمحدوديتها: دو منطقه مجاور، همرنگ نيستندمثال: WA ≠ NT يعني (WA,NT) عضو{(قرمز,سبز),(قرمز,آبي),(سبز,قرمز)، (سبز,آبي),(آبي,قرمز),(آبي,سبز)}

اسلاید 206: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )206مسائل ارضاي محدوديتراه حل انتساب مقاديري است که محدوديتها را ارضا کند

اسلاید 207: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )207مسائل ارضاي محدوديتگراف محدوديتدر گراف محدوديت:گره ها: متغيرهايالها: محدوديتهاگراف براي ساده تر کردن جست و جو بکار ميرود

اسلاید 208: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )208مسائل ارضاي محدوديتمثال CSP: رمزنگاريمتغيرها: F,T,U,W,R,O,X1,X2,X3 دامنه:{9و8و7و6و5و4و3و2و1و0}محدوديتها: F,T,U,R,O,W مخالفند - O+O=R+10.X1 - ...

اسلاید 209: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )209مسائل ارضاي محدوديتنمايش حالتها در CSP از الگوي استانداردي پيروي ميکندبراي CSP ميتوان فرمول بندي افزايشي ارائه کرد:حالت اوليه: انتساب خالي{} که در آن، هيچ متغيري مقدار نداردتابع جانشين: انتساب يک مقدار به هر متغير فاقد مقدار، به شرطي که با متغيرهايي که قبلا مقدار گرفتند، متضاد نباشندآزمون هدف: انتساب فعلي کامل استهزينه مسير: هزينه ثابت براي هر مرحله

اسلاید 210: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )210مسائل ارضاي محدوديتجست و جوي عقبگرد براي CSPجست و جوي عمقيانتخاب مقادير يک متغير در هر زمان و عقبگرد در صورت عدم وجود مقداري معتبر براي انتساب به متغيريک الگوريتم ناآگاهانه استبراي مسئله هاي بزرگ کارآمد نيست

اسلاید 211: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )211مسائل ارضاي محدوديتمثال جست و جوي عقبگرد براي CSP

اسلاید 212: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )212مسائل ارضاي محدوديتمثال جست و جوي عقبگرد براي CSP

اسلاید 213: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )213مسائل ارضاي محدوديتمثال جست و جوي عقبگرد براي CSP

اسلاید 214: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )214مسائل ارضاي محدوديتمثال جست و جوي عقبگرد براي CSP

اسلاید 215: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )215مسائل ارضاي محدوديتمقادير باقيمانده کمينه(MRV)انتخاب متغيري با کمترين مقادير معتبرمتغيري انتخاب ميشود که به احتمال زياد، بزودي با شکست مواجه شده و درخت جست و جو را هرس ميکند

اسلاید 216: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )216اکتشاف درجه ايمسائل ارضاي محدوديتسعي ميکند فاکتور انشعاب را در انتخاب آينده کم کندمتغيري انتخاب ميکند که در بزرگترين محدوديتهاي مربوط به متغيرهاي بدون انتساب قرار دارد

اسلاید 217: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )217اکتشاف مقداري باکمترين محدوديتمسائل ارضاي محدوديتاين روش مقداري را ترجيح ميدهد که در گراف محدوديت، متغيرهاي همسايه به ندرت آن را انتخاب ميکنندسعي بر ايجاد بيشترين قابليت انعطاف براي انتساب بعدي متغيرها

اسلاید 218: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )218مسائل ارضاي محدوديتبررسي پيشرووقتي انتساب به X صورت ميگيرد، فرايند بررسي پيشرو، متغيرهاي بدون انتساب مثل Y را در نظر ميگيرد که از طريق يک محدوديت به X متصل است و هر مقداري را که با مقدار انتخاب شده براي X برابر است، از دامنه Y حذف ميکند

اسلاید 219: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )219مسائل ارضاي محدوديتبررسي پيشرو

اسلاید 220: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )220مسائل ارضاي محدوديتبررسي پيشرو

اسلاید 221: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )221مسائل ارضاي محدوديتبررسي پيشرو

اسلاید 222: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22213243241X1{1,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 223: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22313243241X1{1,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 224: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22413243241X1{1,2,3,4}X3{ ,2, ,4}X4{ ,2,3, }X2{ , ,3,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 225: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22513243241X1{1,2,3,4}X3{ ,2, ,4}X4{ ,2,3, }X2{ , ,3,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 226: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22613243241X1{1,2,3,4}X3{ , , , }X4{ ,2,3, }X2{ , ,3,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 227: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22713243241X1{ ,2,3,4}X3{1,2,3,4}X4{1,2,3,4}X2{1,2,3,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 228: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22813243241X1{ ,2,3,4}X3{1, ,3, }X4{1, ,3,4}X2{ , , ,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 229: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )22913243241X1{ ,2,3,4}X3{1, ,3, }X4{1, ,3,4}X2{ , , ,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 230: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )23013243241X1{ ,2,3,4}X3{1, , , }X4{1, ,3, }X2{ , , ,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 231: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )23113243241X1{ ,2,3,4}X3{1, , , }X4{1, ,3, }X2{ , , ,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 232: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )23213243241X1{ ,2,3,4}X3{1, , , }X4{ , ,3, }X2{ , , ,4}مسائل ارضاي محدوديتمثال: مسئله 4-وزير

اسلاید 233: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )23313243241X1{ ,2,3,4}X3{1, , , }X4{ , ,3, }X2{ , , ,4}مثال: مسئله 4-وزيرمسائل ارضاي محدوديت

اسلاید 234: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )234مسائل ارضاي محدوديتپخش محدوديتپخش الزام محدوديتهاي يک متغير به متغيرهاي ديگرمثال: پخش محدوديتهاي WA و Q به NT و SA

اسلاید 235: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )235مسائل ارضاي محدوديتسازگاري يالروش سريعي براي پخش محدود و قويتر از بررسي پيشرو يال؛ يال جهت دار در گراف محدوديتبررسي سازگاري ياليک مرحله پيش پردازش، قبل از شروع جستجويک مرحله پخشي پس از هر انتساب در حين جستجو

اسلاید 236: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )236مسائل ارضاي محدوديتمثال: سازگاري يالSA  NSW سازگار است اگر SA=blue and NSW=red

اسلاید 237: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )237مسائل ارضاي محدوديتمثال: سازگاري يالNSW  SA سازگار است اگر SA=blue and NSW=redNSW=blue and SA=??? يال ميتواند سازگار شود با حذف blue از NSW

اسلاید 238: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )238مسائل ارضاي محدوديتمثال: سازگاري يال يال ميتواند سازگار شود با حذف blue از NSW حذف red از V

اسلاید 239: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )239مسائل ارضاي محدوديتمثال: سازگاري يال يال ميتواند سازگار شود با حذف blue از NSW حذف red از V تکرار تا هيچ ناسازگاري باقي نماند

اسلاید 240: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )240مسائل ارضاي محدوديتسازگاري Kسازگاري يال تمام ناسازگاريهاي ممکن را مشخص نميکندبا روش سازگاريK، شکلهاي قويتري از پخش را ميتوان تعريف کرددر صورتي CSP سازگاريK است، که براي هر k-1 متغير و براي هر انتساب سازگار با آن متغيرها، يک مقدار سازگار، هميشه بتواند به متغير kام نسبت داده شود

اسلاید 241: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )241مسائل ارضاي محدوديتسازگاري Kبطور مثال:سازگاري1: هر متغير با خودش سازگار است(سازگاري گره)سازگاري2: مشابه سازگاري يال سازگاريk: بسط هر جفت از متغيرهاي همجوار به سومين متغير همسايه(سازگاري مسير) گراف در صورتي قويا سازگارK است که:سازگارk باشدهمچنين سازگارk-1 و سازگارk-2 و... سازگار 1 باشددر اين صورت، مسئله را بدون عقبگرد ميتوان حل کردپيچيدگي زماني آن O(nd) است

اسلاید 242: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )242مسائل ارضاي محدوديتجست و جوي محلي در مسائل ارضاي محدوديتبسياري از CSPها را بطور کارآمد حل ميکنندحالت اوليه، مقداري را به هر متغير نسبت ميدهدتابع جانشين، تغيير مقدار يک متغير در هر زمانانتخاب مقدار جديد براي يک متغيرانتخاب مقداري که کمترين برخورد را با متغيرهاي ديگر ايجاد کند(اکتشاف برخورد کم) زمان اجراي برخورد کم مستقل از اندازه مسئله استبرخورد کم، براي مسئله هاي سخت نيز کار ميکندجست و جوي محلي ميتواند در صورت تغيير مسئله، تنظيمات Online را انجام دهد

اسلاید 243: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )243مسائل ارضاي محدوديتمثالراه حل دو مرحله اي براي مسئله 8وزير با استفاده از کمترين برخورددر هر مرحله، يک وزير براي انتساب مجدد در ستون خودش انتخاب ميگرددتعداد برخوردها در هر مربع نشان داده شده استالگوريتم وزير را به مربعي با کمترين برخورد انتقال ميدهد، بطوريکه گره ها را بطور تصادفي ميشکند

اسلاید 244: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )244هوش مصنوعيفصل ششمجستجوي خصمانه

اسلاید 245: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )245هوش مصنوعي Artificial Intelligenceفهرستبازيها چيستند و چرا مطالعه ميشوند؟انواع بازيهاالگوريتم minimaxبازيهاي چند نفرههرس آلفا-بتابازيهاي قطعي با اطلاعات ناقصبازيهايي که حاوي عنصر شانس هستند

اسلاید 246: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )246جستجوي خصمانهبازي ها چيستند و چرا مطالعه ميشوند؟بازيها حالتي از محيطهاي چند عاملي هستندهر عامل نياز به در نظر گرفتن ساير عاملها و چگونگي تأثير آنها داردتمايز بين محيطهاي چند عامل رقابتي و همکارمحيطهاي رقابتي، که در آنها اهداف عاملها با يکديگر برخورد دارند، منجر به مسئله هاي خصمانه ميشود که به عنوان بازي شناخته ميشوندچرا مطالعه ميشوند؟قابليتهاي هوشمندي انسانها را به کار ميگيرندماهيت انتزاعي بازي هاحالت بازي را به راحتي ميتوان نمايش داد و عاملها معمولا به مجموعه کوچکي از فعاليتها محدود هستند که نتايج آنها با قوانين دقيقي تعريف شده اند

اسلاید 247: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )247جستجوي خصمانهانواع بازي هااطلاعات کاملاطلاعات ناقصقطعيتصادفيشطرنجريورسيتخته نردپوکر

اسلاید 248: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )248جستجوي خصمانهيک نمونه بازي بازي دو نفره: Min و Maxاول Max حرکت ميکند و سپس به نوبت بازي ميکنند تا بازي تمام شوددر پايان بازي، برنده جايزه و بازنده جريمه ميشودبازي به عنوان يک جستجو:حالت اوليه: موقعيت صفحه و شناسه هاي قابل حرکتتابع جانشين:ليستي از (حالت,حرکت) که معرف يک حرکت معتبر استآزمون هدف:پايان بازي چه موقع است؟(حالتهاي پايانه)تابع سودمندي: براي هر حالت پايانه يک مقدار عددي را ارائه ميکند. مثلا برنده(1+) و بازنده(1-)حالت اوليه و حرکات معتبر براي هر بازيکن، درخت بازي را براي آن بازي ايجاد ميکند

اسلاید 249: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )249جستجوي خصمانهيک نمونه بازي الگوريتم؛بازيکن: انتخاب بهترين حالتحريف: انتخاب بهترين موقعيت براي خودش يا بدترين وضعيت براي بازيکنبازيکن: ماکزيمم حالتحريف: مينيمم حالت

اسلاید 250: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )250جستجوي خصمانهالگوريتم minimax

اسلاید 251: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )251جستجوي خصمانهيک نمونه بازي

اسلاید 252: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )252جستجوي خصمانهيک نمونه بازي

اسلاید 253: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )253جستجوي خصمانهيک نمونه بازي

اسلاید 254: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )254جستجوي خصمانهيک نمونه بازي

اسلاید 255: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )255جستجوي خصمانهيک نمونه بازي

اسلاید 256: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )256جستجوي خصمانهالگوريتم minimaxکامل بودن: بله (اگر درخت محدود باشد)بهينگي: بلهپيچيدگي زماني:پيچيدگي فضا:

اسلاید 257: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )257جستجوي خصمانهبازيهاي چند نفرهتخصيص يک بردار به هر گره، به جاي يک مقداربازيهاي چند نفره معولاً شامل اتحاد رسمي يا غير رسمي بين بازيکنان استاتحاد با پيشروي بازي ايجاد و از بين ميرودبازيکنان بطور خودکار همکاري ميکنند، تا به هدف مطلوب انحصاري برسند

اسلاید 258: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )258جستجوي خصمانههرس آلفا-بتادر الگوريتم MaxMin:تعداد حالتهاي بازي که بايد بررسي شوند، بر حسب تعداد حرکتها، تواني استراه حل: محاسبه تصميم الگوريتم، بدون ديدن همه گره ها امکانپذير استهرس آلفا-بتا:انشعابهايي که در تصميم نهايي تأثير ندارند را حذف ميکندآلفا: مقدار بهترين انتخاب در هر نقطه انتخاب در مسير Max تاکنونبتا: مقدار بهترين انتخاب در هر نقطه انتخاب در مسير Min تاکنونتعداد گره هايي که بايد بررسي شوند به تقليل ميابدفاکتور انشعاب مؤثر به جاي b برابر با جذرb خواهد بودپيش بيني آن نسبت به minimax دو برابر است

اسلاید 259: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )259جستجوي خصمانههرس آلفا-بتاگره n که هر جاي درخت ميتواند باشد، بررسي ميشوداگر بازيکن انتخاب بهتري داشته باشددر گره والد nيا هر انتخاب بهتري تا کنونn هيچوقت در بازي واقعي قابل دسترس نخواهد بوددر نتيجه n هرس ميشود

اسلاید 260: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )260جستجوي خصمانهمثال: هرس آلفا-بتا[-∞, +∞][-∞,+∞]محدوده مقادير ممکن

اسلاید 261: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )261جستجوي خصمانهمثال: هرس آلفا-بتا[-∞,3][-∞,+∞]

اسلاید 262: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )262جستجوي خصمانهمثال: هرس آلفا-بتا[-∞,3][-∞,+∞]

اسلاید 263: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )263جستجوي خصمانه[3,+∞][3,3]

اسلاید 264: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )264جستجوي خصمانهمثال: هرس آلفا-بتا[-∞,2][3,+∞][3,3]اين گره برايMax مناسب نيست

اسلاید 265: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )265جستجوي خصمانهمثال: هرس آلفا-بتا[-∞,2][3,14][3,3][-∞,14],

اسلاید 266: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )266جستجوي خصمانهمثال: هرس آلفا-بتا[−∞,2][3,5][3,3][-∞,5],

اسلاید 267: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )267جستجوي خصمانهمثال: هرس آلفا-بتا[2,2][−∞,2][3,3][3,3]

اسلاید 268: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )268جستجوي خصمانهمثال: هرس آلفا-بتا[2,2][-∞,2][3,3][3,3]

اسلاید 269: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )269جستجوي خصمانهبازيهاي قطعي با اطلاعات ناقصمعايب الگوريتم هاي پيشينالگوريتم minimax کل فضاي جست و جوي بازي را توليد ميکندالگوريتم آلفا-بتا با وجود هرس درخت، اما کل مسير حالتهاي پايانه، حداقل براي بخشي از فضاي حالت، بايد جست و جو شوداين عمق عملي نيست، زيرا حرکات بايد در زماني معقول انجام شودشانون(1950)براي کمتر شدن زمان جست و جو و اعمال تابع ارزيابي اکتشافي به حالتهاي جستجو، بهتر است از گره هاي غير پايانه به گره هاي پايانه پرداخته شود

اسلاید 270: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )270جستجوي خصمانهبازيهاي قطعي با اطلاعات ناقصدر شانون, minimax و آلفا-بتا به دو روش بطور متناوب عمل ميکنندجايگزيني تابع سودمندي با تابع ارزيابي اکتشافي بنام EVALتخميني از سودمندي موقعيت ارائه ميکندجايگزين تست پايانه با تست توقفتصميم ميگيرد EVAL چه موقع اعمال شود

اسلاید 271: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )271جستجوي خصمانهتابع ارزيابي اکتشافي EVALتابع ارزيابي، ارائه تخميني از سودمندي مورد انتظار بازي از يک موقعيت خاصتوابع اکتشافي، تخميني از فاصله تا هدف را بر ميگرداندنداغلب توابع ارزيابي، خواص گوناگوني از حالتها را محاسبه ميکنندخواص روي هم رفته، کلاسهاي هم ارزي يا دسته هاي مختلفي از حالتها را تعريف ميکنندحالتهاي هر دسته، براي تمام خواص مقدار يکساني دارندهر دسته حاوي چند حالت است کهموجب برنده شدنموجب رسم شدنمنجر به باختنتابع ارزيابي نميداند کدام حالت منجر به چه چيزي ميشود، اما ميتواند مقداري برگرداند که تناسب حالتها را با هر نتيجه نشان دهد

اسلاید 272: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )272جستجوي خصمانهEval(s) = w1 f1(s) + w2 f2(s) + … + wnfn(s)مثال: تابع EVALاغلب توابع ارزيابي, مقدار عددي جداگانه اي براي هر خاصيت محاسبه، سپس آنها را ترکيب ميکنند تا مقدار کل بدست آيدمثال در تابع بازي شطرنج: تعداد هر نوع قطعه در صفحه مقادير آن قطعات(1 براي پياده، 3 براي اسب يا فيل،5 براي رخ و ...)

اسلاید 273: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )273جستجوي خصمانهمثال: تابع EVALب) سفيد حرکت ميکندالف) سفيد حرکت ميکندالف) سياه، مزيت اسب و دو پياده دارد و بازي را ميبردب) پس از اينکه سفيد، وزير را در اختيار ميگيرد، سياه ميبازدارزيابي تابع EVAL از مقدار پيروزي در دو موقعيت کاملا متفاوت

اسلاید 274: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )274جستجوي خصمانهاثر افقوقتي بوجود مي آيد که برنامه با اثري از رقيب مواجه شود که منجر به خرابي جدي گشته و اجتناب پذير استمثال: شکل مقابل؛سياه در اصل جلوست، اما اگر سفيد پياده اش را از سطر هفتم به هشتم ببرد، پياده به وزير تبديل ميشود و موقعيت برد براي سفيد بوجود مي آيد

اسلاید 275: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )275جستجوي خصمانهبازيهايي که حاوي عنصر شانس هستندشانسشانسپايانه

اسلاید 276: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )276هوش مصنوعيفصل هفتمعامل هاي منطقي

اسلاید 277: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )277هوش مصنوعي Artificial Intelligenceفهرستعاملهاي مبتني بر دانشمنطقمنطق گزاره ايالگوهاي استدلال در منطق گزاره ايالگوريتم resolutionزنجير پيشرو و عقبگرد

اسلاید 278: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )278عاملهاي منطقيعاملهاي مبتني بر دانشمؤلفه اصلي عامل مبتني بر دانش، پايگاه دانش آن استپايگاه دانش: مجموعه اي از جملاتجمله: زبان نمايش دانش و بيان ادعاهايي در مورد جهانبراي اضافه کردن جملات به پايگاه دانش و درخواست دانسته هاTELL و ASKهر دو ممکن است شامل استنتاج باشندپيروي:انجام فرايند استنتاج تحت مقررات خاصبخش استنتاجپايگاه دانشمحدوده اطلاعات خاصمحدوده اطلاعات خاصمحدوده الگورِيتمهاي مستقلtellask

اسلاید 279: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )279عاملهاي منطقيعاملهاي مبتني بر دانش عامل مبتني بر دانش بايد بتواند:نمايش حالات و فعاليتهاترکيب ادراکات جديدبروز کردن تصور داخلي خود از جهاناستنباط خصوصيات مخفي جهاناستنتاج فعاليتهاي مناسب عامل پايگاه دانش خيلي شبيه به عاملهايي با حالت دروني استعاملها در دو سطح متفاوت تعريف ميشوند:سطح دانش: عامل چه چيزي ميداند و اهداف آن کدامند؟سطح پياده سازي: ساختمان داده اطلاعات پايگاه دانش و چگونگي دستکاري آنها

اسلاید 280: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )280عاملهاي منطقيجهان WUMPUSمعيار کارايي:1000+ انتخاب طلا، 1000- افتادن در گودال يا خورده شدن، 1- هر مرحله، 10- براي استفاده از تيرمحيط:بوي تعفن در مربعهاي همجوار WUMPUSنسيم در مربعهاي همجوار گودالدرخشش در مربع حاوي طلاکشته شدن WUMPUS با شليک در صورت مقابلهتير فقط مستقيم عمل ميکندبرداشتن و انداختن طلاحسگرها:بو تعفن، نسيم، تابش، ضربه، جيغ زدنمحرکها:گردش به چپ، گردش به راست، جلو رفتن، برداشتن، انداختن، شليک کردن

اسلاید 281: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )281عاملهاي منطقيتوصيف جهان WUMPUSقابل مشاهده کامل: خير, فقط ادراک محليقطعي: بله، نتيجه دقيقا مشخص استرويدادي: خير، ترتيبي از فعاليتهاستايستا: بله, WUMPUS و گودالها حرکت ندارندگسسته: بلهتک عامله: بله، WUMPUS در اصل يک خصوصيت طبيعي است

اسلاید 282: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )282عاملهاي منطقيکاوش در جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 283: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )283عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 284: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )284عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 285: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )285عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 286: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )286عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 287: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )287عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 288: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )288عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 289: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )289عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = W

اسلاید 290: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )290عاملهاي منطقيمنطقيک زبان رسمي:ترکيب(نحو): چه کلمه بندي صحيح است.(خوش فرم)معناشناسي: يک کلمه بندي صحيح چه معنايي دارددر منطق، معناي زبان، درستي هر جمله را در برابر هر جهان ممکن تعريف ميکندمثال، در زبان رياضياتX+2 >= y يک جمله اما x2+y جمله نيستX+2 >= y در جهان درست است اگر x=7 و y =1 X+2 >= y در جهان غلط است اگر x=0 و y =6

اسلاید 291: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )291عاملهاي منطقياستلزاماستلزام منطقي بين جملات اين است که جمله اي بطور منطقي از جمله ديگر پيروي ميکندa ╞ b جمله a استلزام جمله b استجمله a جمله b را ايجاد ميکنداگر و فقط اگر، در هر مدلي که a درست است، b نيز درست استاگر a درست باشد، b نيز درست استدرستي b در درستي a نهفته است مثال: جمله x+y=4 مستلزم جمله 4=x+y است

اسلاید 292: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )292عاملهاي منطقيمدلهاي Wumpus

اسلاید 293: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )293عاملهاي منطقيمدلهاي WumpusKB = قوانين دنياي Wumpus+مشاهدات

اسلاید 294: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )294عاملهاي منطقيمدلهاي WumpusKB = wumpusدنياي + مشاهداتα1 = [1,2] امن است, KB ╞ α1

اسلاید 295: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )295عاملهاي منطقيمدلهاي WumpusKB = wumpusدنياي + مشاهدات

اسلاید 296: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )296عاملهاي منطقيمدلهاي WumpusKB = wumpusدنياي + مشاهداتα2 = [2,2] امن است, KB ╞ α2

اسلاید 297: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )297عاملهاي منطقيمنطق گزاره اينحو منطق گزاره اي، جملات مجاز را تعريف ميکندجملات اتميک(عناصر غير قابل تعميم) تشکيل شده از يک نماد گزارههر يک از اين نمادها به گزاره اي درست يا نادرست اختصاص داردنمادها از حروف بزرگ مثل P,Q,R استفاده ميکنندجملات پيچيده با استفاده از رابطهاي منطقي، از جملات ساده تر ساخته ميشوند┐ (not) جمله اي مثل ┐W1,3 نقيض W1,3 استليترال يک جمله اتميک(ليترال مثبت)، يا يک جمله اتميک منفي(ليترال منفي) است^ (and) مثل P1,3 ^ W1,3 ترکيب عطفي نام دارد.هر بخش آن يک عطف ناميده ميشودν (or) مثل W2,2 ν (P3,1 ^ W1,3) ترکيب فصلي مربوط به فصل هاي W2,2 و P3,1 ^ W1,3=> (استلزام): W2,2 ┐ ν (P3,1 ^ W1,3) استلزام يا شرطي ناميده ميشود. مقدمه يا مقدم آن P3,1 ^ W1,3 و نتيجه يا تالي آن W2,2 ┐ است جمله W2,2  W1,3 دو شرطي نام دارد

اسلاید 298: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )298عاملهاي منطقيمنطق گزاره اي

اسلاید 299: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )299جدول درستي پنج رابطه منطقيعاملهاي منطقي

اسلاید 300: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )300منطق گزاره اي در دنياي Wumpusعاملهاي منطقيدر B1,1 نسيمي وجود دارد B1,1  (P1,2 ν P2,1)در [1,1] گودالي وجود ندارد R1: ┐P1,1

اسلاید 301: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )301عاملهاي منطقيالگوهاي استدلال در منطق گزاره ايقوانين استنتاج: الگوهايي استاندارد که زنجيره اي از نتايج را براي رسيدن به هدف ايجاد ميکندقياس استثنايي: با استفاده از ترکيب عطفي، ميتوان هر عطف را استنتاج کرد(يعني هر وقت جمله اي به شکل a=>b داده شود، جمله b را ميتوان استنتاج کرد.)ميتوان از(WumpusAhead ^ WumpusAlive)و(WumpusAhead ^ WumpusAlive) => ShootShoot را استنتاج کرد

اسلاید 302: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )302عاملهاي منطقيحذف and: هر عطف را ميتوان از ترکيب عطفي استنتاج کردمثال: WumpusAlive را ميتوان از جمله زير استناج کرد(WumpusAhead ^ WumpusAlive)خاصيت يکنواختيمجموعه اي از جملات استلزامي که فقط ميتواند در صورت اضافه شدن اطلاعات به پايگاه دانش رشد کند. براي جملات a و b داريم:

اسلاید 303: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )303عاملهاي منطقيقانون resolutionقانون resolution واحد، يک عبارت و يک ليترال را گرفته، عبارت ديگري توليد ميکندقانون resulotion واحد ميتواند به قانون resulotion کامل تعميم داد:

اسلاید 304: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )304عاملهاي منطقيالگوريتم resolutionشکل نرمال عطفي(CNF): جمله اي که بصورت ترکيب عطفي از ترکيبات فصلي ليترالها بيان ميشود.در هر عبارت موجود در جمله k-CNF دقيقا k ليترال وجود داردالگوريتم resolution:براي اينکه نشان دهيمKB|=a , مشخص ميکنيم (KB ^ ┐a) ارضا کننده نيست ابتدا (KB ^ ┐a) را به CNF تبديل ميکنيمسپس قانون resulotion به عبارات کوچک حاصل اعمال ميشودهر جفتي که شامل ليترالهاي مکمل باشد، resulotion ميشود تا عبارت جديدي ايجاد گردداگر اين عبارت قبلا در مجموعه نباشد، به آن اضافه ميشودفرايند تا محقق شدن يکي از شروط زير ادامه مي يابد:هيچ عبارت ديگري وجود نداشته باشد که بتواند اضافه شود. در اين مورد، b استلزام a نيستکاربرد قانون resolution، عبارت تهي را بدست ميدهد که در اين مورد، b استلزام a است

اسلاید 305: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )305عاملهاي منطقيمثال:الگوريتم resolutionKB = (B1,1  (P1,2 P2,1))  B1,1 α = P1,2

اسلاید 306: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )306عاملهاي منطقيزنجير پيشرو و عقبگردعبارات هورن: ترکيب فصلي ليترالهايي است که فقط يکي از آنها مثبت استهر عبارت هورن را ميتوان به صورت يک استلزام نوشت که مقدمه آن ترکيب عطفي ليترالهاي مثبت و تالي آن يک ليترال مثبت استاين نوع عبارات هورن که فقط يک ليترال مثبت دارند، عبارات معين ناميده ميشوندليترال مثبت را رأس و ليترالهاي منفي را بدنه عبارت گويندعبارت معيني که فاقد ليترالهاي منفي باشد، گزاره اي بنام حقيقت نام داردعبارات معين اساس برنامه نويسي منطقي را ميسازداستنتاج با عبارات هورن، از طريق الگوريتم هاي زنجير پيشرو و زنجير عقبگرد انجام ميگيرد

اسلاید 307: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )307عاملهاي منطقيزنجير پيشروالگوريتم زنجير پيشرو تعيين ميکند آيا نماد گزاره اي q(تقاضا)، توسط پايگاه دانش عبارات هورن ايجاب ميشود يا خير

اسلاید 308: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )308عاملهاي منطقيزنجير پيشرو

اسلاید 309: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )309عاملهاي منطقيزنجير پيشرو

اسلاید 310: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )310عاملهاي منطقيزنجير پيشرو

اسلاید 311: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )311عاملهاي منطقيزنجير پيشرو

اسلاید 312: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )312عاملهاي منطقيزنجير پيشرو

اسلاید 313: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )313عاملهاي منطقيزنجير پيشرو

اسلاید 314: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )314عاملهاي منطقيزنجير پيشرو

اسلاید 315: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )315عاملهاي منطقيزنجير پيشرو

اسلاید 316: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )316عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 317: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )317عاملهاي منطقيالگوريتم عقبگرد کاملتغييرات عمده: خاتمه زودرس، اکتشاف نماد محض، اکتشاف عبارت واحد

اسلاید 318: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )318عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 319: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )319عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 320: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )320عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 321: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )321عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 322: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )322عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 323: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )323عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 324: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )324عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 325: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )325عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 326: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )326عاملهاي منطقيالگوريتم عقبگرد کامل

اسلاید 327: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )327هوش مصنوعيفصل هشتممنطق رتبه اول

اسلاید 328: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )328هوش مصنوعي Artificial Intelligenceفهرستمروري بر منطق گزاره ايمنطق رتبه اولانواع منطقنحو و معناي منطق رتبه اولمهندسي دانش

اسلاید 329: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )329منطق رتبه اولمروري بر منطق گزاره ايويژگيهاماهيت اعلانيدانش و استنتاج متمايزند و استنتاج کاملاً مستقل از دامنه استقدرت بيان کافي براي اداره کردن اطلاعات جزئيبا استفاده از ترکيب فصلي و نقيضقابليت ترکيبمعناي جمله، تابعي از معناي بخشهاي آن معنا، مستقل از متن استبر خلاف زبانهاي طبيعي که، معناي جملات وابسته به متن استمعايبفاقد قدرت بياني براي تشريح دقيق محيطي با اشياي مختلفبر خلاف زبانهاي طبيعي

اسلاید 330: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )330منطق رتبه اولمنطق رتبه اولاساس منطق گزاره اي را پذيرفته و بر اساس آن يک منطق بياني ميسازيماز ايده هاي نمايشي زبان طبيعي استفاده کرده، از عيوب آن اجتناب ميکنيمزبانهاي طبيعي از جهان طبقه بندي زير را دارنداشياء: افراد، خانه، اعداد، رنگها، بازيهاي فوتبال، آتش و ...رابطه ها: رابطه هاي يکاني يا خواص مثل قرمز، گرد، اول و ... رابطه هاي چندتايي مثل برادر بودن، بزرگتر بودن، بخشي از، مالکيت و ...توابع: پدر بودن، بهترين دوست، يکي بيشتر از و ...منطق رتبه اول توسط اشيا و رابطه ها ساخته ميشوداشياء: افراد، خانه، اعداد، رنگها، بازيهاي فوتبال، آتش و ...رابطه ها: رابطه هاي يکاني يا خواص مثل قرمز، گرد، اول و ... رابطه هاي چندتايي مثل برادر بودن، بزرگتر بودن، بخشي از، مالکيت و ...توابع: پدر بودن، بهترين دوست، يکي بيشتر از و ...

اسلاید 331: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )331منطق رتبه اولانواع منطق

اسلاید 332: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )332منطق رتبه اولنحو و معناي منطق رتبه اولنمادهاي ثابت؛ اشيا را نشان ميدهد. مثال: علي، 2، رضا، ...نمادهاي محمول؛ رابطه ها را نشان ميدهد. مثال:برادر بودن، بزرگتر بودن ازنمادهاي تابع؛ توابع را نشان ميدهند. مثال: تابع پاي چپ(LeftLeg)متغيرها: x , y , a ,bروابط منطقي: , , , , تساوي: =سورها: , 

اسلاید 333: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )333منطق رتبه اولجملات اتميک هر ترم يک عبارت منطقي است که به شيئ اشاره ميکندنمادهاي ثابت ترم هستندهميشه استفاده از نماد متمايز براي نامگذاري شيء آسان نيستپاي چپ پاي پادشاه John LeftLeg(John)جملات اتميک: ترکيب ترمهاي اشياء و محولهاي روابطمثال: Married(Father(Richard),Mother(John)) پدر ريچارد با مادر جان ازدواج کرده است جملات اتميک= محمول(nترم1، ترم2، ... ، ترم) يا ترم1=ترم2 . ترم= تابع(nترم1، ترم2، ... ، ترم) يا ثابت يا متغير .

اسلاید 334: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )334منطق رتبه اولجملات پيچيدهبا ترکيب جملات اتميک و روابط منطقي ميتوان جملات پيچيده تري ساخت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)

اسلاید 335: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )335منطق رتبه اولمثالمدلي با پنج شيء، دو رابطه دودويي، سه رابطه يکاني و يک تا يکاني به نام پاي چپ

اسلاید 336: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )336منطق رتبه اولسورها کمک ميکنند تا به جاي شمارش اشيا از طريق نام آنها، خواص کلکسيون اشيا را بيان کردسور عمومي؛  “براي همه”سور وجودي؛  “ وجود دارد حداقل...”

اسلاید 337: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )337منطق رتبه اولسور عمومي<متغيرها> <جمله>x P که در آن P يک عبارت منطقي است، بيان ميکند که P براي هر شيء x درست استمثال: x King(x)  Person(x)

اسلاید 338: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )338منطق رتبه اولسور وجودي <متغيرها> <جمله> x P که در آن P يک عبارت منطقي است، بيان ميکند که P حداقل براي يک شيء x درست استمثال:  x Crown(x)  OnHead(x , John)

اسلاید 339: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )339منطق رتبه اولخصوصيات سورها  رابط طبيعي براي کار با  و  رابط طبيعي براي کار با  ميباشداستفاده از  بعنوان رابط اصلي با  منجر به حکم قوي ميشوداستفاده از  با  منجر به حکم ضعيفي ميشودx y برابر است با y x و x y برابر است با y x x y برابر نيست با y xx y Loves(x,y)حداقل يک نفر وجود دارد که همه چيز در جهان را دوست داردy x Loves(x,y)همه در دنيا حداقل يک نفر را دوست دارند

اسلاید 340: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )340منطق رتبه اولخصوصيات سورها “هر کسي بستني را دوست دارد” به معناي اين است که “هيچ کس وجود ندارد که بستني را دوست نداشته باشد”x Likes(x , IceCream) هم ارز x Likes(x , IceCream)x P هم ارز x Px P هم ارز x P x P هم ارز x Px P هم ارز x P

اسلاید 341: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )341منطق رتبه اولتساوي با استفاده از = دو ترم به يک شيء اشاره ميکنندبراي تعيين درستي جمله تساوي بايد ديد که آيا ارجاع ها به دو ترم، اشياي يکساني اند يا خيرمثال: ريچارد حداقل دو برادر داردx,y Brother(x,Richard) ^ Brother(y,Richard) ^ (x=y)

اسلاید 342: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )342منطق رتبه اولادعاها و تقاضاهاجملات از طريق TELL به پايگاه دانش اضافه ميشونداين جملات را ادعا گويندTELL (KB , King(John))TELL (KB , x King(x) => Person(x))با استفاده از ASK تقاضاهايي را از پليگاه دانش انجام ميدهيماين پرسشها، تقاضا يا هدف نام داردASK (KB , Person(John))ASK(KB , x Person(x)) ليست جانشيني يا انقيادليستي از جانشينيها در صورت وجود بيش از يک پاسخ

اسلاید 343: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )343منطق رتبه اولدامنه خويشاونديمادر هر فرد والد مؤنث آن فرد است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)

اسلاید 344: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )344منطق رتبه اولاعداد و مجموعه ها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))]s1,s2 s1  s2  (x x  s1  x  s2)s1,s2 (s1 = s2)  (s1  s2  s2  s1)x,s1,s2 x  (s1  s2)  (x  s1  x  s2)x,s1,s2 x  (s1  s2)  (x  s1  x  s2)

اسلاید 345: www.myazdanpanah.mihanblog.comهوش مصنوعی راسل - نورویک( 1 - 2 - 3 - 4 )345منطق رتبه اولمهندسي دانشفرايند کلي ساخت پايگاه دانش که شامل مراحل ذيل ميباشد:مشخص کردن کارمونتاژ دانش مربوطهتصميم گيري در مورد واژه نامه محمولها، توابع و وراثتکدگزاري دانش کلي در مورد دامنهکد گزاري توصيف نمونه مسئله خاصاِعمال تقاضاها به رويه استنتاج و دريافت پاسخاشکال زدايي پايگاه دانش