هوش مصنوعی
بهترين جستجوی بازگشتي RBFS

هوش مصنوعی

1. هوش مصنوعی

‫هوش مصنوعی‬
‫نام مرجع ‪:‬‬
‫‪ ‬‬
‫‪Artificial Intelligence A Modern‬‬
‫‪Approach‬‬
‫نویسنده ‪:‬‬
‫استوارت راسل‪ ،‬پیتر نورویگ‬
‫‪ ‬‬
‫‪ ‬‬
‫‪1‬‬
‫ك تاب دروس تخصصي هوش مصنوعي از سري ك تاب هاي راهيان ارشد‪ ،‬انتشارات ازاده‬
‫هوش مصنوعي ‪ ،‬نوشته بن كوپين ‪ ،‬مترجم داورپناه و ميرزاي ي‬

2.

‫هوش مصنوعي‬
‫فصل اول‬
‫مقدمه‬
‫‪2‬‬

3.

‫هوش مصنوعي‬
‫‪Artificial Intelligence‬‬
‫فهرست‬
‫‪ ‬هوش مصنوعي چيست؟‬
‫‪ ‬مباني هوش مصنوعي‬
‫‪ ‬تاريخچه هوش مصنوعي‬

4.

‫مقدمه‬
‫هوش مصنوعي چيست؟‬
‫‪4‬‬
‫عاقالنه فکر کردن‬
‫مانند انسان فکر کردن‬
‫عاقالنه عمل کردن‬
‫مانند انسان عمل کردن‬

5.

‫مقدمه‬
‫مانند انسان عمل کردن‬
‫‪ ‬هنر ساخت ماشينهاي ي که کارهاي ي را انجام ميدهند که ان کارها‬
‫‪Acting humanly‬‬
‫توسط انسان با فکر کردن انجام ميشوند‪.‬‬
‫ا‬
‫‪ ‬مطالعه براي ساخت کامپيوترها براي انجام کارهاي ي که فعال انسان‬
‫انها را بهتر انجام ميدهد‪.‬‬
‫‪5‬‬

6.

‫مقدمه‬
‫(مانند انسان عمل کردن)‬
‫تست تورينگ‬
‫‪B‬‬
‫‪A‬‬
‫‪6‬‬

7.

‫مقدمه‬
‫مانند انسان فکر کردن‬
‫‪Thinking humanly‬‬
‫‪ ‬تالش جديد و هيجان انگيز براي ساخت ماشين هاي ي متفکر و‬
‫با حس کامل‬
‫‪ ‬خودکارسازي فعاليت هاي مرتبط با تفکر انسان‪ ،‬فعاليتهاي ي مثل‬
‫تصميم گيري‪ ،‬حل مسئله‪ ،‬يادگيري‬
‫‪7‬‬

8.

‫مقدمه‬
‫عاقالنه فکر کردن‬
‫‪Think rationally‬‬
‫‪ ‬مطالعه تواناي ي هاي ذهني از طريق مدل هاي محاسباتي‬
‫(منطق گراي ي)‬
‫‪ ‬مطالعه محاسباتي که منجر به درک و استدالل مي شود‪.‬‬
‫‪8‬‬

9.

‫مقدمه‬
‫عاقالنه عمل کردن‬
‫‪Act rationally‬‬
‫طوري عمل کند که بهترين نتيجه را ارائه دهد‬
‫‪ ‬هوش محاسباتي‪ ،‬مطالعه طراحي عامل هاي هوشمند است‬
‫‪9‬‬

10.

‫مقدمه‬
‫مباني هوش مصنوعي‬
‫فلسفه‪ :‬منطق‪ ،‬استدالل‪ ،‬ناشي‬
‫شدن تفکر از مغز فيزيکي‪ ،‬مباني‬
‫يادگيري‪ ،‬زبان و عقالنيت‬
‫زبان شناسي‪ :‬علم‬
‫ارائه‪ ،‬گرامر‬
‫‪10‬‬
‫روان شناسي‪ :‬تطبيق‪ ،‬اثر طبيعي‬
‫ادراک و تاثير ان بر محيط‬
‫رياضيات‪ :‬نمايش رسمي الگوريتمها‪،‬‬
‫محاسبات‪ ،‬تصميم پذيري و تصميم‬
‫ناپذيري‪ ،‬احتمال‬

11.

‫مقدمه‬
‫مباني هوش مصنوعي‬
‫نظريه کنترل و سيبرنتيک‪:‬‬
‫تحت‬
‫کنترل در اوردن محصوالت مصنوعي‪ ،‬ثبات و پايداري‪،‬‬
‫طراحي عامل بهينه‬
‫اقتصاد‪:‬‬
‫نظريه بازي‬
‫‪11‬‬
‫نظريه تصميمهاي عقالي ي‪،‬‬
‫علوم عصبي‪:‬‬
‫نحوه پردازش‬
‫اطالعات توسط مغز‬
‫مهندسي کامپيوتر‪:‬‬
‫کامپيوترهاي سريع‬
‫ساخت‬

12.

‫مقدمه‬
‫تاريخچه هوش مصنوعي‬
‫‪ ،1943 ‬مک کولوچ و والتر پيتز‪ :‬ارايه مدل نرون مصنوعي بيتي( دو حالته) قابل يادگيري به منظور محاسبه هر‬
‫تابع قابل محاسبه‪.‬‬
‫‪ ،1950 ‬الن تورينگ اولين بار ديد کاملي از هوش مصنوعي را تحت عنوان “ محاسبات ماشيني و هوشمند” ارايه‬
‫نمود‪.‬‬
‫‪ ،1951 ‬هينسکي و ادموندز اولين کامپيوتر شبکه عصبي را طراحی کردند‪.‬‬
‫‪ ،1952 ‬ارتور سامويل‪ :‬برنامه اي ساخت که ياد ميگرفت بهتر از نويسنده اش بازي کند؛ در نتيجه اين تصور را که‬
‫“کامپيوتر فقط کاري را انجام ميدهد که به ان گ فته شود” نقض کرد‪.‬‬
‫‪12‬‬

13.

‫مقدمه‬
‫(تاريخچه هوش مصنوعي)‬
‫‪،1956 ‬نشست کارگروهي دورتموند‪ :‬انتخاب نام هوش مصنوعي‬
‫‪ ،1959 ‬هربرت جلونتر‪ :‬برنامه(‪ )GTP‬را ساخت که قضايا را با اصل موضوعات مشخص ثابت مي کرد‪.‬‬
‫‪ ،1958 ‬جان مک کارتي‪ :‬تعريف زبان ليسپ که بهترين زبان هوش مصنوعي شد‪.‬‬
‫‪ ،1973-1958 ‬جيمز اسالگل‪ :‬برنامه حل مسايل انتگرالگيري فرم بسته‬
‫‪ ‬تام ايوانز‪ :‬برنامه حل مشابهت هاي هندسي‬
‫‪ ‬دانيل بابروز‪ :‬برنامه حل مسايل جبري‬
‫‪ ‬ديويد هافمن‪ :‬پروژه محدوده بيناي ي روبات در جهان بلوکها‬
‫‪ ‬ديويد والتز‪ :‬سيستم بيناي ي و انتشار محدود‬
‫‪13‬‬
‫‪ ‬پاتريک ونيستون‪ :‬نظريه يادگيري‬

14.

‫مقدمه‬
‫(تاريخچه هوش مصنوعي)‬
‫(‪ )1966-1973‬کند شدن مسير تحقيقات هوش مصنوعی‬
‫‪ ‬پيچيده شدن الگوريتم برنامه های جديد‬
‫‪ ‬برنامه ترجمه متون‬
‫‪ ‬انجام ناپذيری بسياری از مسائلی که سعی در حل انها بود‬
‫‪ ‬عدم موفقيت اثبات قضايا با مفروضات بيشتر‬
‫‪ ‬بکارگيری بعضی محدوديتها روی ساختارهای اساسی‬
‫‪ ‬محدوديت نمايش پرسپترون دو ورودی‬
‫‪14‬‬

15.

‫مقدمه‬
‫(تاريخچه هوش مصنوعي)‬
‫(‪ )1979 -1969‬سيستم های مبتنی بر دانش‬
‫‪ ‬جست و جوی همه منظوره که سعی بر يادگيری داشت تا پيمودن راه حل کامل‬
‫‪ ‬مثل برنامه ‪ ،DENDRAL‬بوچانان و همکارانش در سال ‪1969‬‬
‫• مزيت برنامه ‪ DENDRAL‬اين بود که اولين سيستم پاداش غنی بود‬
‫‪ ‬متدولوژی جديد سيستم خبره‬
‫‪ ‬مثل سيستم ‪ MYCIN‬که برای تشخيص عفونتهای خونی طراحی شد‬
‫• استفاده از فاک تورهای قطعيت‬
‫‪ ‬افزايش تقاضا برای ِشمای نمايش دانش‬
‫‪ ‬استفاده از منطق در پرولوگ‪ ،‬استفاده از ايده مينسکی يعنی قابها و ‪...‬‬
‫‪15‬‬

16.

‫مقدمه‬
‫(تاريخچه هوش مصنوعي)‬
‫‪ 1980‬تا کنون‪ :‬تبديل هوش مصنوعی به يک صنعت‬
‫‪ 1986‬تاکنون‪ :‬برگشت به شبکه های عصبی‬
‫‪ 1987‬تاکنون‪ :‬هوش مصنوعی به علم تبديل ميشود‬
‫‪ 1995‬تاکنون‪ :‬ظهور عاملهای هوشمند‬
‫‪16‬‬

17.

‫هوش مصنوعي‬
‫فصل دوم‬
‫عاملهاي هوشمند‬
‫‪17‬‬

18.

‫هوش مصنوعي‬
‫‪Artificial Intelligence‬‬
‫فهرست‬
‫‪ ‬عامل‬
‫‪ ‬خواص محيطهای وظيفه‬
‫‪ ‬برنامه های عامل‬
‫‪18‬‬

19.

‫عاملهای هوشمند‬
‫عامل‪:‬‬
‫به هر چيزي اطالق ميشود‪ ،‬که قادر به درک محيط پيرامون خود از طريق حسگرها(‪ )sensor‬و اثرگذاري‬
‫بر روي محيط از طريق اثرکنندهها (‪ )effector‬باشد‪.‬‬
‫عامل نرمافزاري‪:‬‬
‫عامل نرمافزاري رشتههاي بيتي را به عنوان درک محيط و عمل‪ ،‬کدگذاري ميکند‪.‬‬

20.

‫عاملهای هوشمند‬
‫عوامل انساني‬
‫‪.1‬‬
‫حس کردن‪ :‬گوش‪ ،‬چشم‪ ،‬ديگر ارگانها‬
‫‪.2‬‬
‫اثرگذاري‪ :‬دست‪ ،‬پا‪ ،‬بيني‪ ،‬اندامهاي ديگر‬
‫عوامل روباتيک‬
‫‪.1‬‬
‫حس کردن‪ :‬دوربين‪ ،‬يابندههاي مادون قرمز‬
‫‪.2‬‬
‫اثرگذاري‪ :‬موتور‬

21.

‫عاملهای هوشمند‬
‫‪ ‬دنباله ادراک‬
‫سابقه کامل هر چيزی است که عامل تاکنون درک کرده است‪.‬‬
‫‪ ‬تابع عامل‬
‫رفتار عامل توسط تابع عامل توصيف ميشود که هر دنباله ادراک را به يک فعاليت نقش ميکند‪.‬‬
‫‪f : P* A‬‬
‫فعاليت‬
‫‪21‬‬
‫دنباله ادراک ‪ :‬تابع عامل‬

22.

‫عاملهای هوشمند‬
‫‪ ‬عامل‬
‫ادراک ها‬
‫محيط‬
‫?‬
‫فعاليت ها‬
‫‪22‬‬
‫حسگرها‬
‫محرکها‬
‫عامل‬

23.

‫عاملهای هوشمند‬
‫عاملها چگونه بايد عمل کنند؟‬
‫عامل منطقي‪ :‬چيزي است که کار درست انجام ميدهد‪.‬‬
‫عمل درست‪ :‬ان است که باعث موفقترين عامل گردد‪.‬‬
‫کاراي ي‪ :‬چگونگي موفقيت يک عامل را تعيين ميکند‪.‬‬

24.

‫عاملهای هوشمند‬
‫ان چه در هر زماني منطقي است به چهار چيز وابسته است‪:‬‬
‫‪ ‬معيار کاراي ي که درجه موفقيت را تعيين ميکند‪.‬‬
‫‪ ‬هر چيزي که تا کنون عامل‪ ،‬ادراک نموده است‪ .‬ما اين تاريخچه کامل ادراکي را دنباله ادراکي ميناميم‪.‬‬
‫‪ ‬انچه که عامل درباره محيط خود ميداند‪.‬‬
‫‪ ‬اعمالي که عامل ميتواند صورت دهد‪.‬‬

25.

‫عاملهای هوشمند‬
‫رفتار عامل وابسته به دنباله ادراکي تا حال است‪.‬‬
‫عامل را بايد بهعنوان ابزاري براي تحليل سيستمها قلمداد کرد؛‬
‫نه شخصيتي مطلق که جهان را به دو بخش عامل و غيرعاملها تقسيم ميکند‪.‬‬

26.

‫عاملهای هوشمند‬
‫خودمختاري‪:‬‬
‫اگر رفتار عامل هاي تنها مبتني بر دانش دروني باشد و هيچ توجهي به ادراك خود نكند‪ ،‬انگاه عامل فاقد خود‬
‫مختاري خواهد بود‪ .‬زيرا همواره به يك صورت عمل خواهد كرد‪.‬‬
‫عامل هوشمند خود مختار بايد قادر باشد كه در دامنه وسيعي از محيط ها موفقيت اميز عمل كند و خود را با‬
‫ان منطبق سازد‪.‬‬
‫سيستم به وسعتي خود مختار است که رفتار ان بر اساس تجربه خودش تعيين ميکند‪ .‬زماني که عامل فاقد‬
‫تجربه و يا کم تجربه است‪ً ،‬‬
‫مسلما تصادفي عمل خواهد کرد‪ ،‬مگر انکه طرح کمکهاي ي به ان داده باشد‪.‬‬

27.

‫محيط عاملهای هوشمند‬
‫ارتباط بين عامل و محيط‪ :‬اعمال بوسيله عامل بر محيط انجام ميشود‪ ،‬که خود ادراک عامل را مهيا ميسازد‪.‬‬
‫خواص محيط‪:‬‬
‫‪ ‬قابل دسترسي در مقابل غير دسترسي (رويت پذير و نيمه رويت پذير)‬
‫‪ ‬قطعي در برابر غير قطعي(اتفاقي)‬
‫‪ ‬اپيزوديک در مقابل غيراپيزوديک (مرحله اي در مقابل ترتيبي‪ -‬دوره اي در مقابل غير دوره اي – واقعه اي در مقابل‬
‫غير واقعه اي )‬
‫‪ ‬ايستا در مقابل پويا‬
‫‪ ‬گسسته در مقابل پيوسته‬
‫‪ ‬تك عاملي در مقابل چند عاملي‬
‫•چند عاملي رقابتي درمقابل چندعاملي همياری‬

28.

‫محيط عاملهای هوشمند‬
‫‪ ‬قابل دسترسي در مقابل غيرقابل دسترسي‬
‫محيط قابل دسترسي‪ :‬محيطي که عامل ان توسط ابزار حسکنندهاش امکان دسترسي به وضعيت کامل محيط را‬
‫داشته باشد‪.‬‬
‫محيط قابل دسترسي راحت است‪ ،‬زيرا عامل نيازمند دستکاري هيچ وضعيت داخلي براي حفظ دنيا را نخواهد‬
‫داشت‪.‬‬

29.

‫محيط عاملهای هوشمند‬
‫‪ ‬قطعي در مقابل غير قطعي‬
‫محيط قطعي‪ :‬محيطي است که دقيقا بدانيم در وضعيت كنوني دنيا عامل چه عملي را انتخاب مي كند و انجام مي‬
‫دهد‪ ،‬وضعيت بعدي دنيا چه خواهد بود‪.‬‬
‫هر چه محيط پيچيده تر باشد احتمال اين كه غيرقطعي باشد بيشتر خواهد بود‪.‬‬
‫بهتر است به قطعي يا غير قطعي بودن محيط از ديدگاه عامل نگاه کنيم‪.‬‬

30.

‫محيط عاملهای هوشمند‬
‫‪ ‬اپيزوديک در مقابل غير اپيزوديک‬
‫‪ ‬درمحيط اپيزوديک (‪ ،)episodic‬تجربه عامل به مرحله هاي ي تقسيم ميگردد‪.‬‬
‫‪ ‬هر مرحله شامل درک و عمل عامل است‪.‬‬
‫‪ ‬کيفيت اعمال ان تنها به خود مرحله وابسته است‪ .‬و به مرحله هاي قبلي بستگي ندارد‪.‬‬
‫‪ ‬محيطهاي مرحله اي بسيار سادهترند زيرا عامل نبايد به جلوتر فکر کند‪.‬‬
‫مثال‪ :‬راننده تاكسي و شطرنج‪ :‬ترتيبي‬
‫تشخيص قطعات معيوب‪ :‬مرحله اي‬

31.

‫محيط عاملهای هوشمند‬
‫‪ ‬ايستا در مقابل پويا‬
‫محيط پويا‪ :‬محيطي که در حين سنجيدن عامل تغيير ميکند‪.‬‬
‫محيط نيمهپويا‪ :‬محيطي که با گذر زمان تغيير نميکند اما امتياز کاراي ي تغيير ميکند‪.‬‬
‫(شطرنج ساعتي‪ :‬انجام عمل عامل به زمان وابسته است اما محيط تغيير نمي كند‪).‬‬
‫محيطهاي ايستا براي کار ساده هستند زيرا عامل نياز به نگاهکردن به دنيا در حين تصميمگيري عملي نداشته و‬
‫همچنين در مورد گذر زمان نيز نگران نميباشد‪.‬‬

32.

‫محيط عاملهای هوشمند‬
‫‪ ‬گسسته در مقابل پيوسته‬
‫محيط گسسته‪ :‬اگر تعداد محدود و مجزا از ادراک و اعمال بوضوح تعريف شده باشد‪.‬‬
‫ بازي شطرنج گسسته است‪.‬‬‫ رانندگي تاکسي پيوسته است‪.‬‬‫سختترين حالت در بين حاالت موجود براي محيط‪:‬‬
‫غير قابل دسترسي‪ ،‬غير اپيزوديک‪ ،‬پويا و پيوسته‬

33.

‫محيط عاملهای هوشمند‬
‫مثالهاي ي از انواع محيط و ويژگيهاي انها‬
‫محيط‬
‫قابل دسترسي‬
‫قطعي‬
‫اپيزوديک‬
‫ايستا‬
‫گسسته‬
‫شطرنج به همراه ساعت‬
‫‪YES‬‬
‫‪YES‬‬
‫‪NO‬‬
‫‪Semi‬‬
‫‪YES‬‬
‫شطرنج بدون ساعت‬
‫‪YES‬‬
‫‪YES‬‬
‫‪NO‬‬
‫‪YES‬‬
‫‪YES‬‬
‫پوکر‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪YES‬‬
‫‪YES‬‬
‫تخته نرد‬
‫‪YES‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪YES‬‬
‫‪YES‬‬
‫راندن تاکسي‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫سيستم تشخيص پزشکي‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫سيستم تحليل تصوير‬
‫‪YES‬‬
‫‪YES‬‬
‫‪YES‬‬
‫‪Semi‬‬
‫‪NO‬‬
‫ربات جابجا کننده اشياء‬
‫‪NO‬‬
‫‪NO‬‬
‫‪YES‬‬
‫‪NO‬‬
‫‪NO‬‬
‫کنترلکننده پااليشگاه‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫اموزشدهنده انگليسي با ارتباط متقابل‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪NO‬‬
‫‪YES‬‬

34.

‫عاملهای هوشمند‬
‫ساختار عاملها‬
‫برنامه ‪ +‬معماری = عامل‬
‫کار هوش مصنوعی طراحی برنامه عامل است که تابع عامل را پياده سازی ميکند‬
‫اين طراحي شامل تابعي است که نگاشت عامل از ادراک به عمليات را پياده سازي ميکند‪.‬‬
‫معماري‪ :‬فرض ميکنيم برنامه عامل بر روي نوعي ابزار محاسبهگر اجرا ميگردد که ان را معماري ميناميم‪.‬‬
‫برنامه عامل‪ ،‬بايد توسط معماري قابل پذيرش و اجرا باشد‪.‬‬

35.

‫عاملهای هوشمند‬
‫برنامه های عامل‬
‫‪ ‬عاملهای واکنشی ساده‬
‫‪ ‬عاملهای واکنشی مدل گرا‬
‫‪ ‬عاملهای هدف گرا‬
‫‪ ‬عاملهای سودمند‬
‫‪ ‬عاملهای يادگيرنده‬
‫‪36‬‬

36.

‫عاملهای هوشمند‬
‫عاملهای واکنشی ساده‬
‫‪ ‬اين عاملها فعاليت را بر اساس درک فعلی‬
‫و بدون در نظر گرفتن سابقه ادراک‪ ،‬انتخاب‬
‫ميکند‬
‫‪ ‬داراي يك مجموعه از قوانين شرط‪ -‬عمل‬
‫‪38‬‬
‫عامل‬
‫جهان چگونه است‬
‫محيط‬
‫‪ ‬به خاطر حذف سابقه ادراک برنامه عامل‬
‫در مقايسه با جدول ان بسيار کوچک است‬
‫حسگرها‬
‫اکنون چه عملی بايد انجام‬
‫دهم‬
‫محرکها‬
‫قانون‬
‫شرط عمل‬

37.

‫عاملهای هوشمند‬
‫مثالي از عامل واکنشی ساده در دنيای جاروبرقي‬
‫‪ ‬تصميم گيری ان بر اساس مک ان فعل ی‬
‫و ک ثيف بودن ان مکان صورت ميگيرد‬
‫‪ ‬در برنام ه عام ل در مقايس ه ب ا ج دول‬
‫ان‪ ،‬تع داد حالته ای ممک ن از ‪ 4‬ب ه ‪4‬‬
‫کاهش مي يابد‬
‫‪ ‬انتخ اب فعالي ت ب ر اس اس موقعي ت)]‪function REFLEX-VACUUM-AGENT ([location, status‬‬
‫‪return an action‬‬
‫شرطي‪:‬‬
‫‪if status == Dirty then return Suck‬‬
‫‪If dirty then suck‬‬
‫‪else if location == A then return Right‬‬
‫‪else if location == B then return Left‬‬
‫‪39‬‬

38.

‫عاملهای هوشمند‬
‫عاملهای واکنشي مدل گرا‬
‫حسگرها‬
‫‪ ‬عام ل بخش ي از دني اي ي را ک ه فع ا‬
‫ميبيند رديابی ميکند‬
‫جهان چگونه است‬
‫‪ ‬عامل بايد حال ت داخل ي را ذخي ره کن د‬
‫که به سابقه ادراک بستگي دارد‬
‫‪ ‬در هر وضعيت‪ ,‬عامل ميتواند توصيف‬
‫جديدی از جهان را کسب کند‬
‫‪40‬‬
‫محيط‬
‫‪ ‬اس تفاده از دان ش “چگ ونگی عملک رد‬
‫جهان” که مدل نام دارد‬
‫حالت‬
‫جهان چگونه تکامل‬
‫می يابد‬
‫کار فعاليت چيست‬
‫اکنون چه عملی بايد انجام‬
‫دهم‬
‫محرکها‬
‫قانون‬
‫شرط عمل‬
‫عامل‬

39.

‫عاملهای هوشمند‬
‫عاملهای هدف گرا‬
‫حسگرها‬
‫‪ ‬اين عامل عاوه بر توص يف حال ت فعل ی‪ ،‬ب رای‬
‫انتخ اب موقعي ت مطل وب نيازمن د اطاع ات ه دف‬
‫نيز ميباشد‬
‫‪ ‬اي ن ن وم تص ميم گي ری هم واره اين ده را در نظ ر‬
‫دارد و با قوانين شرط عمل تفاوت دارد‬
‫‪ ‬اي ن ن وم عام ل ک اراي ي چن دانی ن دارد‪ ،‬ام ا‬
‫قابليت انعطاف بيشتری دارد‬
‫‪41‬‬
‫جهان چگونه است‬
‫محيط‬
‫‪ ‬جس ت و ج و و برنام ه ري زی‪ ،‬دنبال ه ای از‬
‫فعاليتها را برای رسيدن عامل به هدف‪ ،‬پيدا ميکند‬
‫حالت‬
‫جهان چگونه تکامل‬
‫می يابد‬
‫اگر فعاليت ‪ A‬را انجام‬
‫دهم چه خواهد شد‬
‫اکنون چه عملی بايد انجام‬
‫دهم‬
‫محرکها‬
‫کار فعاليت چيست‬
‫اهداف‬
‫عامل‬

40.

‫عاملهای هوشمند‬
‫عاملهای سودمند‬
‫حسگرها‬
‫‪ ‬اي ن عام ل ب راي اه داف مش خص‪ ،‬راه ه ای‬
‫مختلف ی دارد‪ ،‬ک ه راه ح ل بهت ر ب رای عام ل‬
‫سودمندتر است‪.‬‬
‫جهان چگونه است‬
‫محيط‬
‫‪ ‬ت ابع س ودمندی‪ ،‬حال ت ي ا دنبال ه ای از حالته ا‬
‫را ب ه ي ک ع دد حقيق ی نگاش ت ميکن د ک ه درج ه‬
‫رضايت را توصيف ِميکند‪.‬‬
‫جهان چگونه تکامل‬
‫می يابد‬
‫اگر فعاليت ‪ A‬را انجام‬
‫دهم چه خواهد شد‬
‫‪ ‬وقت ی اه داف متض اد باش ند‪ ،‬بعض ی از انه ا‬
‫براورده ميشوند‬
‫در چنين حالتی چقدر‬
‫رضايت دارم‬
‫‪ ‬اگ ر هيچي ک از اه داف ب ه ط ور قطع ی قاب ل‬
‫حصول نباشند‪ ،‬احتمال موفقي ت ب ا اهمي ت ه دف‬
‫مقايسه ميشود‬
‫اکنون چه عملی بايد انجام‬
‫دهم‬
‫‪42‬‬
‫حالت‬
‫محرکها‬
‫کار فعاليت چيست‬
‫سودمند‬
‫عامل‬

41.

‫عاملهای هوشمند‬
‫عاملهای يادگيرنده‬
‫استاندارد کاراي ي‬
‫عنصرِِيادگيرنده مسئول ايجاد بهبودها‬
‫‪ِ ‬‬
‫حسگرها‬
‫تغييرات‬
‫عنصر کاراي ي‬
‫عنصر يادگيرنده‬
‫دانش‬
‫اهداف‬
‫يادگيری‬
‫‪ ‬مولد مسئله مس ئول پيش نهاد فعاليته اي ي اس ت‬
‫که منجر به تجربيات اموزنده جديدی ميشود‬
‫محيط‬
‫‪ ‬منتقد مشخص ميکن د ک ه يادگيرن ده ب ا توج ه ب ه‬
‫استانداردهای کاراي ي چگونه عمل ميکند‬
‫بازخورد‬
‫‪ ‬عنص ر ک اراي ي مس ئول انتخ اب فعاليته ای‬
‫خارجی‬
‫منتقد‬
‫مولد مسئله‬
‫‪43‬‬
‫محرکها‬
‫عامل‬

42.

‫عاملهای هوشمند‬
‫تفاوت عاملهاي واکنشي و هدفگرا‪:‬‬
‫در طراحي عاملهاي واکنشي طراح براي حاالت متفاوت عملي درست را پيش محاسبه ميکند‪ .‬در عاملهاي‬
‫هدفگرا‪ ،‬عامل ميتواند دانش خود را در مورد چگونگي واکنش بهنگام سازد‪.‬‬

43.

‫عاملهای هوشمند‬
‫‪ .1‬براي عامل واکنشي ما مجبور به دوباره نويسي تعداد زيادي قوانين شرط –عمل خواهيم بود‪.‬‬
‫‪ .2‬عامل هدفگرا نسبت به رسيدن به مقاصد متفاوت انعطاف پذير است‪.‬‬
‫‪ .3‬بسادگي با تعيين يک هدف تازه‪ ،‬ميتوانيم عامل هدفگرا را به رفتار تازه برسانيم‪.‬‬

44.

‫هوش مصنوعي‬
‫فصل سوم‬
‫حل مسئله با جستجو‬
‫‪46‬‬

45.

‫هوش مصنوعي‬
‫فهرست‬
‫‪47‬‬
‫‪Artificial Intelligence‬‬
‫‪ ‬عاملهای حل مسئله‬
‫‪ ‬مسئله‬
‫‪ ‬اندازه گيری کاراي ي حل مسئله‬
‫‪ ‬جستجوی نااگاهانه‬
‫‪ ‬اجتناب از حالتهای تکراری‬
‫‪ ‬جستجو با اطالعات ناقص‬

46.

‫حل مسئله با جستجو‬
‫يک نوم عامل هدفگرا‪ ،‬عامل حل مسئله ناميده ميشود‪.‬‬
‫عاملهاي حل مسئله توسط يافتن ترتيب عمليات تصميم ميگيرند که چه انجام دهند تا انها را به حالتهاي‬
‫مطلوب سوق دهد‪.‬‬

47.

‫حل مسئله با جستجو‬
‫عاملهاي حل مسئله‬
‫ً‬
‫مستقيما به داخل دنباله حالتهاي ي وارد شود که معيار‬
‫‪ ‬عاملهاي هوشمند به طريقي عمل ميکنند که محيط‬
‫کاراراي ي را افزايش ميدهند‪.‬‬
‫‪ ‬عمليات به گونهاي سادهسازي ميشوند که عامل قادر باشد تا هدفي را قبول کرده و به ان برسد‪.‬‬
‫‪ ‬الگوريتم جستجو مسئلهاي را به عنوان ورودي دريافت نموده و راهحلي را به صورت دنباله عمليات بر‬
‫ميگرداند‪.‬‬

48.

‫حل مسئله با جستجو‬
‫فاز اجراي ي‪ :‬مرحلهاي است که در ان زمان‪ ،‬راهحلي پيدا ميشود و عمليات پيشنهادي ميتوانند انجام شوند‪.‬‬
‫به طور ساده براي طرح يک عامل مراحل «فرمولهسازي‪ ،‬جستجو‪ ،‬اجرا» را در نظر ميگيريم‪.‬‬

49.

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

50.

‫حل مسئله با جستجو‬
‫پس از فرمولهسازي يک هدف و يک مسئله براي حل عامل‪،‬‬
‫‪ .1‬رويه جستجوي ي را براي حل ان مسئله فراخواني ميکند‪.‬‬
‫‪ .2‬از راه حل براي راهنماي ي عملياتش استفاده ميکند و هرانچه که راه حل پيشنهاد ميکند را‬
‫انجام ميدهد‪.‬‬
‫‪ .3‬ان مرحله را از دنباله حذف ميکند‪.‬‬
‫‪ .4‬زماني که راهحل اجرا شد‪ ،‬عامل هدف جديدي را پيدا ميکند‪.‬‬

51.

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

52.

‫حل مسئله با جستجو‬
‫براي تعريف يک مسئله موارد زير نياز داريم‪:‬‬
‫‪ ‬وضعيت اغازين (‪ )initial state‬که عامل خودش از بودن در ان اگاه است‪.‬‬
‫‪ ‬مجموعهاي از عمليات ممکن‪ ،‬که براي عامل قابل دسترسي باشد‪.‬‬
‫‪ ‬ازمون هدف (‪ ،)goal test‬که عامل ميتواند در يک تعريف وضعيت منفرد ان را تقاضا کند تا تعيين‬
‫گردد که ان حالت‪ ،‬وضعيت هدف است يا خير‪.‬‬
‫‪ ‬تابع هزينه مسير‪ ،‬تابعي است که براي هر مسير‪ ،‬هزينهاي را در نظر ميگيرد؛ و با حرف ‪ c‬مشخص ميشود‪.‬‬
‫هزينه يک سفر= مجموع هزينههاي عمليات اختصاصي در طول مسير‬

53.

‫حل مسئله با جستجو‬
‫براي حل مسئله چند حالته‪ ،‬فقط به يک اصاح جزئي نياز داريم‪:‬‬
‫يک مسئله شامل‪:‬‬
‫‪ ‬يک مجموعه حالت اوليه‬
‫‪ ‬مجموعهاي از عملگرهاي ويژه براي هر عمل به گونهاي که از هر وضعيت داده شده مجموعهاي حاالت رسيده‬
‫شده و يک ازمون هدف و تابع هزينه مسير را معين کند‪.‬‬

54.

‫حل مسئله با جستجو‬
‫يک عملگر‪:‬‬
‫توسط اجتمام نتايج اعمال عملگر در هر وضعيت مجموعه‪ ،‬به کار برده ميشود‪.‬‬
‫يک مسير‪:‬‬
‫مجموعه حاالت را مرتبط ميکند‪.‬‬
‫يک راه حل‪:‬‬
‫مسيري است که به مجموعهاي از حاالت که تمام انها‪ ،‬وضعيت هدف هستند‪ ،‬سوق ميدهند‪.‬‬

55.

‫حل مسئله با جستجو‬
‫اندازهگيري کاراي ي حل مسئله‪:‬‬
‫کاراي ي يک جستجو‪ ،‬حداقل از سه طريق ميتواند اندازهگيري شود‪:‬‬
‫‪ .1‬ايا اين جستجو راه حلي پيدا ميکند؟‬
‫‪ .2‬ايا راه حلي مناسبي است؟‬
‫‪ .3‬هزينه جستجو از نظر زماني و حافظه مورد نياز براي يافتن راه حل چيست؟‬
‫مجموع هزينه جستجو= هزينه مسير ‪ +‬هزينه جستجو‬
‫عامل بايد تصميم بگيرد که چه منابعي را فداي جستجو و چه منابعي را صرف اجرا کند‪.‬‬

56.

‫حل مسئله با جستجو‬
‫انتخاب حاالت و عمليات‬
‫هنر واقعي حل مسئله‪ ،‬تصميمگيري در مورد اين است که چه چيزهاي ي در تعريف حاالت و عملگرها بايد به حساب‬
‫اورده شوند و چه چيزهاي ي بايد کنار گذاشته شوند‪.‬‬

57.

‫حل مسئله با جستجو‬
‫انتزاع‪:‬‬
‫فرايند حذف جزئيات از يک بارنماي ي انتزام (‪ )abstraction‬ناميده ميشود‪.‬‬
‫‪ ‬همانگونه که تعريف را خاصه ميکنيم ميبايست عمليات را نيز خاصه نمائيم‪.‬‬
‫‪ ‬انتزام به اين دليل مفيد است‪ ،‬که انجام هر کدام از عمليات اسانتر از مسئله اصلي است‪.‬‬
‫‪ ‬انتخاب يک انتزام خوب از اين رو شامل حذف تا حد ممکن ميشود تا زماني که عمليات خاصه شده براي انجام‬
‫اسان باشند‪.‬‬

58.

‫حل مسئله با جستجو‬
‫مثال‪ :‬نقشه رومانی‬
‫‪61‬‬

59.

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

60.

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

61.

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

62.

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

63.

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

64.

‫معماي ‪:8‬‬
‫حل مسئله با جستجو‬
‫مثال‪ :‬معمای‪8‬‬
‫معماي ‪ 8‬نمونهاي است شامل يک صفحة ‪ 3*3‬با ‪ 8‬مربع شماره دار‬
‫در يک صفحه خالي‪.‬‬
‫هر مربع که مجاور خانه خالي است‪ .‬ميتواند به درون ان خانه برود‪.‬‬
‫هدف رسيدن به ساختاري است که در سمت راست شکل نشان داده‬
‫شده است‪ .‬نک ته مهم اين است که بجاي اينکه بگوييم «مربع شماره‬
‫‪ 4‬را به داخل فضاي خالي حرکت بده» بهتر است بگوييم «فضاي‬
‫خالي جايش را با مربع سمت چپش عوض کند‪».‬‬
‫‪67‬‬

65.

‫حل مسئله با جستجو‬
‫مثال‪ :‬معمای‪8‬‬
‫حالتها‪ :‬توصيف وضعيت مکان هر ‪ 8‬مربع را در يکي از ‪9‬خانة صفحه‬
‫مشخص ميکند‪ .‬براي کاراي ي بيشتر‪ ،‬بهتر است که فضاهاي خالي نيز ذکر‬
‫شود‪.‬‬
‫عملگرها‪ :‬فضاي خالي به چ‪ ،،‬راست‪ ،‬باال و پائين حرکت کند‪.‬‬
‫ازمون هدف‪ :‬وضعيت با ساختار هدف مطابقت ميکند‪.‬‬
‫هزينه مسير‪ :‬هر قدم ارزش ‪ 1‬دارد‪ ،‬بنابراين هزينه مسير همان طول مسير‬
‫است‪.‬‬
‫‪68‬‬

66.

‫حل مسئله با جستجو‬
‫مثال‪ :‬مسئله ‪ 8‬وزير‬
‫هدف از مسئله ‪ 8‬وزير‪ ،‬قرار دادن ‪ 8‬وزير بر روي صفحه‬
‫شطرنج به صورتي است که هيچ وزيري نتواند به ديگري حمله‬
‫کند‪.‬‬
‫دو نوم بيان رياضي اصلي وجود دارد بيان افزايشي که با‬
‫جايگزيني وزيرها‪ ،‬به صورت يکي يکي کار ميکند و ديگري‬
‫بيان وضعيت کامل که با تمام ‪ 8‬وزير روي صفحه شروم‬
‫ميکند و انها را حرکت ميدهد‪.‬‬
‫در اين فرمول ما ‪ 64‬امکان داريم‪.‬‬
‫‪69‬‬

67.

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

68.

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

69.

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

70.

‫مسائل دنياي واقعي‬
‫مسيريابي‪:‬‬
‫الگوريتمهاي مسير يابي کاربردهاي زيادي دراند‪ ،‬مانند مسيريابي در شبکههاي کامپيوتري‪ ،‬سيستمهاي خودکار‬
‫مسافرتي و سيستمهاي برنامهنويسي مسافرتي هواي ي‪.‬‬

71.

‫مسائل دنياي واقعي‬
‫مسائل فروشنده دوره گرد و تور ‪:‬‬
‫مسئله فروشنده دوره گرد مسئله مشهوري است که در ان هر شهر حداقل يکبار بايد ماقات شود هدف يافتن‬
‫کوتاهترين مسير است‪.‬‬
‫عاوه بر مکان عامل‪ ،‬هر حالت بايد مجموعه شهرهاي ي را که عامل ماقات کرده‪ ،‬نگه دارد‪.‬‬
‫عاوه بر برنامهريزي صفر براي فروشنده دورهگرد‪ ،‬اين الگوريتمها براي اعمالي نظير برنامهريزي حرکات مته‬
‫خوردکار سوراخکننده برد مدار استفاده ميشود‪.‬‬

72.

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

73.

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

74.

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

75.

‫حل مسئله با جستجو‬
‫جستجوی عرضی‬
‫در اين استراتژي که بسيار سيستماتيک است‪ ،‬ابتدا گره ريشه‪ ،‬و سپس تمام گرههاي ديگر گسترش داده‬
‫ميشوند‪.‬‬
‫به عبارت کليتر‪ ،‬تمام گرههاي عميق ‪ ،d‬قبل از گرههاي عميق ‪ d+1‬گسترش داده ميشوند‪.‬‬
‫مزايا‪:‬جستجوي سطحي‪ ،‬کامل و بهينه ميباشد زيرا هزينه مسير‪ ،‬يک تابع کاهشنيابنده از عمق گره است‪.‬‬
‫معايب‪:‬مرتبه زماني )‪ O(bd+1‬مي باشد که نماي ي است‪.‬‬
‫نياز به حافظه زياد‪.‬‬

76.

‫حل مسئله با جستجو‬
‫جستجوی عرضی‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪79‬‬
‫‪B‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

77.

‫حل مسئله با جستجو‬
‫جستجوی عرضی‬
‫کامل بودن‪ :‬بله‬
‫بهينگی‪ :‬بله (مشروط)‬
‫بله (مشروط)‬
‫در صورتی بهينه است که هزينه مسير‪ ،‬تابعی غير نزولی از عمق گره باشد‪(.‬مثل وقتي که‬
‫فعاليتها هزينه يکسانی دارند)‬
‫پيچيدگي زماني‪:‬‬
‫پيچيدگی فضا‪:‬‬
‫‪80‬‬
‫‪d 1‬‬
‫) ‪O(b‬‬
‫)‬
‫‪d 1‬‬
‫‪O(b‬‬

78.

‫حل مسئله با جستجو‬
‫جستجوی هزينه يکنواخت‬
‫در اين روش گره اي بسط داده مي شود كه هزينه رسيدن به ان حداقل بوده است‪.‬‬
‫در اين استراتژي‪ ،‬در شرايط عمومي‪ ،‬اولين راه حل‪ ،‬ارزانترين راه نيز هست‪.‬‬
‫اگر هزينه مسير توسط تابع )‪ g(n‬اندازهگيري شود‪ ،‬در اين صورت جستجوي سطحي همان جستجوي با هزينه‬
‫يکسان است با‪:‬‬
‫)‪g(n)=DEPTH(n‬‬

79.

‫حل مسئله با جستجو‬
‫جستجوی هزينه يکنواخت‬
‫اين جستجو گره ‪ n‬را با کمترين هزينه مسير بسط ميدهد‬
‫‪A‬‬
‫‪3‬‬
‫‪1‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪B‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪82‬‬
‫‪1‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

80.

‫حل مسئله با جستجو‬
‫جستجوی هزينه يکنواخت‬
‫کامل بودن‪ :‬بله‬
‫هزينه هر مرحله بزرگ تر يا مساوی يک مقدار ثابت و مثبت ‪ε‬‬
‫در مسير افزايش مي يابد)‬
‫باشد‪(.‬هزينه مسير با حرکت‬
‫بهينگی‪ :‬بله‬
‫هزينه هر مرحله بزرگ تر يا مساوی ‪ ε‬باشد‬
‫پيچيدگي زماني‪:‬‬
‫پيچيدگی فضا‪:‬‬
‫‪83‬‬
‫)‬
‫)‬
‫] ‪[C*/ ‬‬
‫‪O(b‬‬
‫] ‪[C*/ ‬‬
‫‪O(b‬‬

81.

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

82.

‫حل مسئله با جستجو‬
‫جستجوی عمقی‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪B‬‬
‫‪H‬‬
‫‪6‬‬
‫‪G‬‬
‫‪2‬‬
‫‪E‬‬
‫‪F‬‬
‫‪3‬‬
‫‪7‬‬
‫‪Q‬‬
‫‪P‬‬
‫‪O‬‬
‫‪N‬‬
‫‪M‬‬
‫‪L‬‬
‫‪K‬‬
‫‪5‬‬
‫‪85‬‬
‫‪J‬‬
‫‪4‬‬

83.

‫حل مسئله با جستجو‬
‫جستجوی عمقی‬
‫بودن‪ :‬خير‬
‫بودن‪:‬‬
‫کاملکامل‬
‫اگر زير درخت چ‪ ،‬عمق نامحدود داشت و فاقد هر گونه راه حل باشد‪ ،‬جستجو هرگز خاتمه‬
‫نمي يابد‪.‬‬
‫خير‬
‫بهينگی‪:‬‬
‫بهينگي‪:‬‬
‫‪m‬‬
‫پيچيدگي زماني‪:‬‬
‫) ‪O(b‬‬
‫پيچيدگی فضا‪:‬‬
‫)‪O(bm‬‬
‫‪86‬‬

84.

‫حل مسئله با جستجو‬
‫جستجوی عمقی محدود‬
‫اين استراتژي‪ ،‬براي رهاي ي از دامي که جستجوي عمقي در ان گرفتار ميشد‪ ،‬از يک برش استفاده ميکند‪.‬جستجوي‬
‫عمقي محدود شده کامل است اما بهينه نيست‪.‬‬
‫زمان و پيچيدگي فضاي جستجوي عمقي محدودشده‪ ،‬مشابه جستجوي عمقي است‪ .‬اين جستجو پيچيدگي زماني‬
‫)‪ O(bL‬و فضاي )‪ O(bL‬را خواهد داشت‪ ،‬که ‪ L‬محدودة عمق است‪.‬‬
‫در يک درخت جستجوي نماي ي‪ً ،‬‬
‫تقريبا تمام گرهها در سطح پائين هستند‪ ،‬بنابراين موردي ندارد که سطوح‬
‫باالي ي چندين مرتبه بسط داده شوند‪ .‬تعداد بسطها در يک جستجوي عمقي محدود شده با عمق ‪ d‬و فاک تور‬
‫انشعاب ‪ b‬به قرار زير است‪:‬‬
‫‪1+b+b^2+…+b^(d-2)+b^(d-1)+b^d‬‬

85.

‫حل مسئله با جستجو‬
‫جستجوی عمقی محدود‬
‫مسئله درختهای نامحدود ميتواند به وسيله جست و جوی عمقي با عمق محدود ‪ L‬بهبود يابد‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪88‬‬
‫‪B‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

86.

‫حل مسئله با جستجو‬
‫جستجوی عمقی محدود‬
‫بودن‪ :‬خير‬
‫بودن‪:‬‬
‫کاملکامل‬
‫اگر ‪ L<d‬و سطحی ترين هدف در خارج از عمق محدود قرار داشته باشد‪ ،‬اين‬
‫راهبرد کامل نخواهد بود‪.‬‬
‫خير‬
‫بهينگی‪:‬‬
‫بهينگي‪:‬‬
‫اگر ‪ L<d‬انتخاب شود‪ ،‬اين راهبرد بهينه نخواهد بود‪.‬‬
‫‪L‬‬
‫پيچيدگي زماني‪:‬‬
‫) ‪O(b‬‬
‫پيچيدگی فضا‪:‬‬
‫)‪O(bL‬‬
‫‪89‬‬

87.

‫حل مسئله با جستجو‬
‫جستجوی عميق کننده تکراري‬
‫قسمت دشوار جستجوي عمقي محدود شده‪ ،‬انتخاب يک محدودة خوب است‪.‬‬
‫اگر محدودة عمق بهتري را پيدا کنيم‪ ،‬اين محدوده‪ ،‬ما را به سوي جستجوي کاراتري سوق ميدهد‪ .‬اما براي بيشتر مسائل‪ ،‬محدودة‬
‫عمقي مناسب را تا زماني که مسئله حل نشده است‪ ،‬نميشناسيم‪.‬‬
‫جستجوي عميقکنندة تکراري استراتژي است که نظريه انتخاب بهترين محدودة عمقي‪ ،‬توسط امتحان تمام محدودة مسيرهاي ممکن را‬
‫ياداوري ميکند‪.‬‬
‫مزايا‪:‬‬
‫ترکيبي از مزاياي جستجوي سطحي و عمقي را دارد‪.‬‬
‫اين جستجو مانند جستجوي سطحي کامل و بهينه است‪ ،‬اما فقط مزيت درخواست حافظه اندک را از جستجوي عمقي دارد‪.‬‬
‫مرتبه بسط حاالت مشابه جستجوي سطحي است‪ ،‬به جز اينکه بعضي حاالت چند بار بسط داده ميشوند‪.‬‬

88.

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

89.

‫حل مسئله با جستجو‬
‫جستجوی عميق کننده تکراري‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪92‬‬
‫‪B‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

90.

‫حل مسئله با جستجو‬
‫جستجوی عميق کننده تکراري‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪93‬‬
‫‪B‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

91.

‫حل مسئله با جستجو‬
‫جستجوی عميق کننده تکراري‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪S‬‬
‫‪94‬‬
‫‪B‬‬
‫‪H‬‬
‫‪R‬‬
‫‪Q‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

92.

‫حل مسئله با جستجو‬
‫جستجوی عميق کننده تکراري‬
‫بودن‪ :‬بله‬
‫بودن‪:‬‬
‫کاملکامل‬
‫در صورتی که فاک تور انشعاب محدود باشد‬
‫بهينگی‪:‬‬
‫بهينگيبله‪:‬‬
‫وقتی که هزينه مسير‪ ،‬تابعی غير نزولی از عمق گره باشد‬
‫‪d‬‬
‫پيچيدگي زماني‪:‬‬
‫) ‪O(b‬‬
‫پيچيدگی فضا‪:‬‬
‫)‪O(bd‬‬
‫‪95‬‬

93.

‫حل مسئله با جستجو‬
‫نك ته ‪ :‬پيچيدگي زماني اين جستجو هنوز )‪ O(bd/2‬است‪ ،‬اگر ازمون اشتراك بوسيله الگوريتم‬
‫هاي ‪ hash‬با )‪ O(1‬باشد‪.‬‬
‫در صورتي كه ازمون اشتراك )‪ O(n‬باشد ‪ ،‬پيچيدگي زماني )‪ O(bd‬خواهد بود‪ ،‬زيرا به ازاي‬
‫تعداد گره هاي هر سطح كه ‪ bn‬مي باشد‪ ،‬بايد ازمون اشتراك صورت گيرد‪.‬‬

94.

‫حل مسئله با جستجو‬
‫جستجوی دو طرفه‬
‫انجام دو جست و جوی همزمان‪ ،‬يکي از حالت اوليه به هدف و ديگری از هدف به حالت اوليه تا زمانی که دو‬
‫جست و جو به هم برسند‬
‫‪97‬‬

95.

‫حل مسئله با جستجو‬
‫جستجوی دو طرفه‬
‫بودن‪ :‬بله‬
‫بودن‪:‬‬
‫کاملکامل‬
‫اگر هر دو جستجو‪ ،‬عرضی باشند و هزينه تمام مراحل يکسان باشد‬
‫بهينگی‪:‬‬
‫بهينگيبله‪:‬‬
‫اگر هر دو جستجو‪ ،‬عرضی باشند و هزينه تمام مراحل يکسان باشد‬
‫پيچيدگي زماني‪:‬‬
‫پيچيدگی فضا‪:‬‬
‫‪98‬‬
‫‪d/2‬‬
‫) ‪O(b‬‬
‫‪d/2‬‬
‫) ‪O(b‬‬

96.

‫حل مسئله با جستجو‬
:‫مقايسه استراتژيهاي جستجو‬
.‫ محدوديت عمق است‬l ،‫ ماکزيمم عمق درخت جستجو‬m ،‫ عمل پاسخ‬d ،‫ فاک تور انشعاب‬b .‫ارزيابي استراتژيهاي جستجو‬
Criterion
BreadthFirst
UniformCost
DepthFirst
DepthLimited
Iterative
Deepening
Bidirectional (if
applicable)
Time
bd
bd
bm
bl
bd
bd/2
Space
bd
bd
bm
bl
bd
bd/2
Optimal?
Yes
Yes
No
No
Yes
Yes
Complete
Yes
Yes
No
Yes, if
Yes
Yes
l d

97.

‫حل مسئله با جستجو‬
‫اجتناب از حالتهای تکراری‬
‫وجود حالتهای تکراری در يک مسئله قابل حل‪ ،‬ميتواند ان را به مسئله غير قابل حل تبديل کند‬
‫‪100‬‬

98.

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

99.

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

100.

‫حل مسئله با جستجو‬
‫دنيای جاروبرقی فاقد‬
‫حسگر‬
‫‪ ‬عام ل باي د راج ع ب ه مجموع ه ه اي ح التی‬
‫ک ه ميتوان د ب ه انه ا برس د اس تدالل کن د‪ .‬اي ن‬
‫مجموعه از حالتها را حالت باور گوييم‪.‬‬
‫‪ ‬اگ ر فض ای حال ت فيزيک ي دارای ‪ s‬حال ت‬
‫باش د فض ای حال ت ب اور ‪ 2^s‬حال ت ب اور‬
‫خواهد داشت‪.‬‬
‫‪103‬‬

101.

‫هوش مصنوعي‬
‫فصل چهارم‬
‫جست و جوی اگاهانه و اک تشاف‬
‫‪104‬‬

102.

‫هوش مصنوعي‬
‫فهرست‬
‫‪Artificial Intelligence‬‬
‫‪ ‬متدهای جست و جوی اگاهانه‬
‫‪ ‬يادگيری برای جست و جوی بهتر‬
‫‪ ‬جست و جوی محلی و بهينه سازی‬
‫‪ ‬جست و جوی محلی در فضاهای پيوسته‬
‫‪ ‬عاملهای جست و جوی ‪Online‬‬
‫‪105‬‬

103.

‫جست و جوی اگاهانه و اک تشاف‬
‫متدهای جستجوی اگاهانه‬
‫‪ ‬بهترين جستجو‬
‫‪ ‬حريصانه‬
‫‪A* ‬‬
‫‪IDA* ‬‬
‫‪RBFS ‬‬
‫‪ MA* ‬و*‪SMA‬‬
‫‪106‬‬
‫‪ ‬جستجوی محلی‬
‫‪ ‬تپه نوردی‬
‫‪ ‬شبيه سازی حرارت‬
‫‪ ‬پرتو محلی‬
‫‪ ‬الگوريتمهای ژنتيک‬
‫و بهينه سازی‬

104.

‫جستجوي بهترين‪:‬‬
‫اين استراتژي به اين صورت بيان ميشود که در يک درخت‪ ،‬زماني که گرهها مرتب ميشوند‪ ،‬گرهاي که بهترين‬
‫ارزيابي را داشته باشد‪ ،‬قبل از ديگر گرهها بسط داده ميشود‪.‬‬
‫هدف‪ :‬يافتن راهحلهاي کمهزينه است‪ ،‬اين الگوريتمها ً‬
‫عموما از تعدادي معيار تخمين براي هزينه راهحلها‬
‫استفاده ميکنند و سعي بر حداقل کردن انها دارند‪.‬‬

105.

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

106.

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

107.

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

108.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی حريصانه‬
‫‪A‬‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪B‬‬
‫‪C‬‬
‫‪1‬‬
‫‪1‬‬
‫‪2‬‬
‫‪G‬‬
‫‪3‬‬
‫‪3‬‬
‫‪3‬‬
‫‪Z‬‬
‫‪111‬‬
‫‪1‬‬
‫‪3‬‬
‫‪F‬‬
‫‪1‬‬
‫‪1‬‬
‫‪O‬‬
‫‪2‬‬
‫‪Y‬‬
‫‪2‬‬
‫‪2‬‬
‫‪N‬‬
‫‪2‬‬
‫‪1‬‬
‫‪M‬‬
‫‪L 3‬‬
‫‪K‬‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪V‬‬
‫‪U‬‬
‫‪1‬‬
‫‪X‬‬
‫‪0‬‬
‫‪W‬‬
‫‪1‬‬
‫‪2‬‬
‫‪5‬‬
‫‪E‬‬
‫‪2‬‬
‫‪1‬‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪1‬‬
‫‪D‬‬
‫‪3‬‬
‫‪1‬‬
‫‪I 3‬‬
‫‪3‬‬
‫‪2‬‬
‫‪3‬‬
‫‪2‬‬
‫‪T‬‬
‫‪S‬‬
‫‪2‬‬
‫‪R‬‬
‫‪2‬‬
‫‪Q‬‬
‫‪1‬‬
‫‪J‬‬
‫‪0‬‬
‫‪1‬‬
‫‪3‬‬
‫‪1‬‬
‫‪H‬‬
‫‪2‬‬
‫‪3‬‬
‫‪P‬‬
‫‪3‬‬

109.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی حريصانه‬
‫‪A‬‬
‫‪2‬‬
‫‪ 2‬‬
‫‪3‬‬
‫‪1‬‬
‫‪C‬‬
‫‪1‬‬
‫‪1‬‬
‫‪23‬‬
‫‪ ‬‬
‫‪3‬‬
‫‪O‬‬
‫‪F‬‬
‫‪1‬‬
‫‪1‬‬
‫‪4‬‬
‫‪ ‬‬
‫‪N‬‬
‫‪5‬‬
‫‪ ‬‬
‫‪112‬‬
‫‪3‬‬
‫‪G‬‬
‫‪3‬‬
‫‪B‬‬
‫‪1‬‬
‫‪X‬‬
‫‪0‬‬
‫‪2‬‬
‫‪3‬‬
‫‪1‬‬
‫‪ ‬‬
‫‪1‬‬
‫‪1‬‬
‫‪5‬‬
‫‪E‬‬
‫‪D‬‬

110.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی حريصانه‬
‫‪A‬‬
‫‪1‬‬
‫‪4‬‬
‫‪2‬‬
‫‪B‬‬
‫‪C‬‬
‫‪1‬‬
‫‪1‬‬
‫‪3‬‬
‫‪G‬‬
‫‪3‬‬
‫‪3‬‬
‫‪3‬‬
‫‪Z‬‬
‫‪113‬‬
‫‪1‬‬
‫‪3‬‬
‫‪F‬‬
‫‪1‬‬
‫‪1‬‬
‫‪O‬‬
‫‪2‬‬
‫‪Y‬‬
‫‪2‬‬
‫‪2‬‬
‫‪N‬‬
‫‪2‬‬
‫‪1‬‬
‫‪M‬‬
‫‪L 3‬‬
‫‪K‬‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪V‬‬
‫‪U‬‬
‫‪1‬‬
‫‪X‬‬
‫‪0‬‬
‫‪W‬‬
‫‪1‬‬
‫‪2‬‬
‫‪5‬‬
‫‪E‬‬
‫‪3‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪D‬‬
‫‪3‬‬
‫‪1‬‬
‫‪I 3‬‬
‫‪3‬‬
‫‪2‬‬
‫‪3‬‬
‫‪2‬‬
‫‪T‬‬
‫‪S‬‬
‫‪2‬‬
‫‪R‬‬
‫‪2‬‬
‫‪Q‬‬
‫‪1‬‬
‫‪J‬‬
‫‪0‬‬
‫‪1‬‬
‫‪3‬‬
‫‪1‬‬
‫‪H‬‬
‫‪2‬‬
‫‪3‬‬
‫‪P‬‬
‫‪3‬‬

111.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی حريصانه‬
‫‪A‬‬
‫‪1‬‬
‫‪4‬‬
‫‪2‬‬
‫‪1‬‬
‫‪ 1 B‬‬
‫‪C‬‬
‫‪2‬‬
‫‪ ‬‬
‫‪3‬‬
‫‪ ‬‬
‫‪0‬‬
‫‪114‬‬
‫‪1‬‬
‫‪1‬‬
‫‪3‬‬
‫‪K‬‬
‫‪1‬‬
‫‪5‬‬
‫‪D‬‬
‫‪E‬‬
‫‪3‬‬
‫‪J‬‬
‫‪1‬‬

112.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی حريصانه‬
‫‪ ‬کامل بودن‪ :‬خير‬
‫‪ ‬اما اگر *‪ h = h‬انگاه جستجو کامل ميشود‬
‫‪ ‬بهينگی‪ :‬خير‬
‫‪ ‬اما اگر *‪ h = h‬انگاه جستجو کامل ميشود‬
‫‪ ‬پيچيدگي زماني‪:‬‬
‫) ‪O(b m‬‬
‫‪ ‬اما اگر *‪ h = h‬انگاه‬
‫) ‪O(bd‬‬
‫) ‪O(b m‬‬
‫‪ ‬پيچيدگی فضا‪:‬‬
‫) ‪O(bd‬‬
‫‪ ‬اما اگر *‪ h = h‬انگاه‬
‫‪115‬‬

113.

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

114.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪A‬‬
‫‪A/5‬‬
‫‪1‬‬
‫‪51‬‬
‫‪ ‬‬
‫‪6‬‬
‫‪C/4‬‬
‫‪ ‬‬
‫‪8‬‬
‫‪3‬‬
‫‪G/2‬‬
‫‪1‬‬
‫‪ N/1 4‬‬
‫‪1‬‬
‫‪X/0‬‬
‫‪117‬‬
‫‪5‬‬
‫‪F/3‬‬
‫‪3‬‬
‫‪O/3‬‬
‫‪B/4‬‬
‫‪1‬‬
‫‪1‬‬
‫‪42‬‬
‫‪2‬‬
‫‪4‬‬

115.

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

116.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪A‬‬
‫‪A/5‬‬
‫‪1‬‬
‫‪53‬‬
‫‪ ‬‬
‫‪ ‬‬
‫‪8‬‬
‫‪3‬‬
‫‪1‬‬
‫‪5‬‬
‫‪F/3‬‬
‫‪G/2‬‬
‫‪1‬‬
‫‪2‬‬
‫‪4‬‬
‫‪ ‬‬
‫‪3‬‬
‫‪O/3‬‬
‫‪ N/1 4‬‬
‫‪X/0‬‬
‫‪4‬‬
‫‪1‬‬
‫‪1‬‬
‫‪8‬‬
‫‪D/5‬‬
‫‪E/1‬‬
‫‪3‬‬
‫‪5‬‬
‫‪1‬‬
‫‪119‬‬
‫‪ 3B/1‬‬
‫‪C/4‬‬
‫‪1‬‬
‫‪44‬‬
‫‪2‬‬
‫‪1‬‬
‫‪K/0 6‬‬
‫‪J/1‬‬
‫‪7‬‬

117.

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

118.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪A‬‬
‫‪A/5‬‬
‫‪1‬‬
‫‪10‬‬
‫‪2‬‬
‫‪ B/1‬‬
‫‪3‬‬
‫‪C/9‬‬
‫‪2‬‬
‫‪4‬‬
‫‪ ‬‬
‫‪3‬‬
‫‪ ‬‬
‫‪K/0‬‬
‫‪6‬‬
‫‪121‬‬
‫‪1‬‬
‫‪1‬‬
‫‪8‬‬
‫‪E/1‬‬
‫‪3‬‬
‫‪1‬‬
‫‪D/5‬‬
‫‪3‬‬
‫‪J/1‬‬
‫‪7‬‬

119.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪A‬‬
‫‪ ‬کامل بودن‪ :‬بله‬
‫‪ ‬بهينگی‪ :‬بله‬
‫‪ ‬پيچيدگي زماني‪:‬‬
‫‪ ‬پيچيدگی فضا‪:‬‬
‫‪122‬‬
‫) ‪O(b m‬‬
‫) ‪O(b m‬‬

120.

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

121.

‫بنابراين هر گره جديدي که توليد ميشود‪ ،‬بايد کنترل کنيم که ايا هزينة ‪ f‬اين گره از هزينه ‪ f‬پدرش کمتر است يا‬
‫خير‪ .‬اگر کمتر باشد‪ ،‬هزينة ‪ f‬پدر به جاي فرزند مينشيند‪:‬‬
‫بنابراين‪:‬‬
‫‪ f‬هميشه در طول هر مسيري از ريشه غيرکاهشي خواهد بود‪ ،‬مشروط بر اينکه ‪ h‬امکانپذير باشد‪.‬‬

122.

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

123.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪A‬‬
‫‪A‬‬
‫‪1‬‬
‫‪C 4‬‬
‫‪1‬‬
‫‪0‬‬
‫‪A‬‬
‫‪1‬‬
‫‪1‬‬
‫‪3 B‬‬
‫‪1‬‬
‫‪C 2‬‬
‫‪1‬‬
‫‪1 B‬‬
‫‪1‬‬
‫‪E 1‬‬
‫‪2 D‬‬
‫‪E 1‬‬
‫‪1 D‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪G‬‬
‫‪1 F‬‬
‫‪0‬‬
‫‪G‬‬
‫‪1‬‬
‫‪h126‬‬
‫*‪≤/ h‬‬
‫‪1‬‬
‫‪1 F‬‬
‫‪1‬‬
‫‪0 H‬‬
‫‪0 H‬‬
‫*‪h ≤ h‬‬

124.

‫جست و جوی اگاهانه و اک تشاف‬
A* ‫جستجوی‬
A
1
1
1
2
1
3
1
B
1
D
1
F
A
1
3
3
C 2
5
E
6
1
2
2
1
1
G
1
3
0
1
1
1
B
1
D
1
F
h ≤ h*
C 4
1
E 1
1
G
0
1
4
0 H
0 H
1
h127
≤/ h*

125.

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

126.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪ A‬و اجتناب از گره های تکراری‬
‫‪A/100‬‬
‫‪8‬‬
‫‪ ‬‬
‫‪3‬‬
‫‪ ‬‬
‫‪100 D/90‬‬
‫‪105 C/95‬‬
‫‪B/80 90‬‬
‫‪I/87 107‬‬
‫‪T/60 80‬‬
‫‪ ‬‬
‫‪F/78 98‬‬
‫‪G/90 110‬‬
‫‪5‬‬
‫‪P/79‬‬
‫‪O/78‬‬
‫‪109‬‬
‫‪108‬‬
‫‪88 X/58‬‬
‫‪ ‬‬
‫‪N/72 102‬‬
‫‪82 W/52‬‬
‫‪6‬‬
‫‪ ‬‬
‫‪T/60 100‬‬
‫‪9‬‬
‫‪Z/50 90‬‬
‫‪ ‬‬
‫‪87 Y/47‬‬
‫‪S/70 110‬‬
‫‪7‬‬
‫‪129‬‬
‫‪ ‬‬
‫‪2‬‬
‫‪4‬‬
‫‪ ‬‬
‫‪95 M/75‬‬
‫‪1‬‬
‫‪R/20‬‬
‫‪Q/0‬‬
‫‪70‬‬
‫‪50‬‬
‫‪10‬‬
‫‪ ‬‬
‫‪X/58 108‬‬
‫‪Z/50 110‬‬
‫‪ ‬‬
‫‪102 W/52‬‬
‫‪107 Y/47‬‬
‫‪ ‬‬
‫‪M/75 105‬‬
‫‪106 E/86‬‬

127.

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

128.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪ A‬در نقشه رومانی‬
‫جستجوی ‪ Bucharest‬با شروع از ‪Arad‬‬
‫‪f(Arad) = g(Arad)+h(Arad)=0+366=366‬‬
‫‪131‬‬

129.

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

130.

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

131.

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

132.

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

133.

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

134.

‫جست و جوی اگاهانه و اک تشاف‬
‫جستجوی *‪ A‬در نقشه رومانی‬
‫‪137‬‬

135.

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

136.

‫بنابراين هر گره جديدي که توليد ميشود‪ ،‬بايد کنترل کنيم که ايا هزينة ‪ f‬اين گره از هزينه ‪ f‬پدرش کمتر است يا‬
‫خير‪ .‬اگر کمتر باشد‪ ،‬هزينة ‪ f‬پدر به جاي فرزند مينشيند‪:‬‬
‫بنابراين‪:‬‬
‫*‪ A‬بهينه و كامل است اگر‬
‫*‪h ≤ h‬‬

137.

‫نك ته ‪ :1‬اگر خطاي تابع هيوريستيك كمتر از لگاريتم هزينه مسير واقعي باشد يعني‬
‫))‪| h(n)-h*(n) |≤ O(log h*(n‬‬
‫انگاه تعداد گره هاي ي كه در كانتور هدف قرار مي گيرند ‪ ،‬نسبت به طول راه حل مرتبه نماي ي نخواهند داشت‪.‬‬
‫ً‬
‫معموال قبل از اينکه دچار کمبود زمان شود‪ ،‬دچار کمبود فضا ميشود‪ .‬زيرا اين جستجو تمام‬
‫نك ته ‪A* :2‬‬
‫گرههاي توليد شده را در حافظه ذخيره ميکند‪.‬به همين دليل در بسياري از مسايل بزرگ ‪ ،‬عملي نيست‪.‬‬

138.

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

139.

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

140.

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

141.

‫بهترين جستجوی بازگشتي ‪RBFS‬‬

142.

‫جست و جوی اگاهانه و اک تشاف‬
‫بهترين جستجوی بازگشتي در نقشه رومانی‬
‫‪145‬‬

143.

‫جست و جوی اگاهانه و اک تشاف‬
‫بهترين جستجوی بازگشتي در نقشه رومانی‬
‫‪146‬‬

144. بهترين جستجوی بازگشتي RBFS

‫جست و جوی اگاهانه و اک تشاف‬
‫بهترين جستجوی بازگشتي در نقشه رومانی‬
‫‪147‬‬

145.

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

146.

‫جست و جوی اگاهانه و اک تشاف‬
‫توابع اک تشافی‬
‫‪ ‬مثال برای معمای‪8‬‬
‫‪149‬‬
‫‪ ‬ميان ِگين هزينه حل تقريبا ‪ 22‬مرحله و فاک تور انشعاب در حدود ‪ 3‬است‪.‬‬
‫‪ ‬جست و جوی جامع تا عمق ‪: 22‬‬
‫‪322 3.1 1010‬‬
‫‪ ‬با انتخاب يک تابع اک تشافی مناسب ميتوان مراحل جستجو را کاهش داد‬

147.

‫جست و جوی اگاهانه و اک تشاف‬
‫دو روش اک تشافي متداول برای معمای‪8‬‬
‫تعداد کاشيها در مکانهای نادرست‬
‫در حالت شروع‬
‫‪h1 ‬‬
‫‪h1 8‬‬
‫‪h1‬اک تش اف قاب ل قب ولی اس ت‪ ،‬زي را ه ر کاش ي ک ه در‬
‫ج ای نامناس بی ق رار دارد‪ ،‬ح داقل يکب ار باي د جابج ا‬
‫شود‬
‫‪150‬‬

148.

‫جست و جوی اگاهانه و اک تشاف‬
‫دو روش اک تشافي متداول برای معمای‪8‬‬
‫مجموعه فواصل کاشيها از موقعيتهای هدف انها‬
‫در حالت شروع‬
‫‪h2 ‬‬
‫‪h2 3 1 2 2 2 3 3 2 18‬‬
‫چون کاشيها نميتوانند در امتداد قطر جا به جا ش وند‪ ,‬فاص له ای ک ه‬
‫محاسبه ميکنيم مجموم فواصل افقی و عمودی اس ت‪ .‬اي ن فاص له را‬
‫فاصله بلوک شهر مينامند‪.‬‬
‫‪151‬‬

149.

‫جست و جوی اگاهانه و اک تشاف‬
‫دو روش اک تشافي متداول برای معمای‪8‬‬
‫مجموعه فواصل کاشيها از موقعيتهای هدف انها‬
‫‪h2 ‬‬
‫‪h2‬قابل قب ول اس ت‪ ،‬زي را ه ر جابج اي ي ک ه ميتوان د انج ام گي رد‪ ،‬ب ه‬
‫اندازه يک مرحله به هدف نزديک ميشود‪.‬‬
‫هيچ کدام از اين براوردها‪ ،‬هزينه واقعی راه حل نيست‬
‫هزينه واقعي ‪ 36‬است‬
‫‪152‬‬

150.

‫جست و جوی اگاهانه و اک تشاف‬
‫اثر دقت اک تشاف بر کاراي ي‬
‫‪ ‬فاک تور انشعاب مؤثر *‪b‬‬
‫‪ ‬اگر تعداد گره هاي ي که برای يک مسئله خاص توسط *‪ A‬توليد ميشود برابر با ‪ N‬و عمق راه حل برابر ب ا ‪ d‬باش د‪ ،‬ان گ اه‬
‫*‪ b‬فاک تور انشعابی است که درخت يکنواختی به عمق ‪ d‬بايد داشته باشد تا حاوی ‪ N+1‬گره باشد‬
‫)*‪N 1 1 b* (b‬‬
‫‪ ‬‬
‫‪... ‬‬
‫)*‪(b‬‬
‫ً‬
‫‪ ‬فاک تور انشعاب مؤثر معموال برای مسئله های سخت ثابت است‬
‫‪d‬‬
‫‪2‬‬
‫‪ ‬اندازه گيريهای تجربي *‪ b‬بر روی مجموعه کوچکي از مسئله ها ميتواند راهنمای خوبي برای مفيد بودن اک تشاف باشد‬
‫‪ ‬مقدار *‪ b‬در اک تشافي با طراحي خوب‪ ،‬نزديک ‪ 1‬است‬
‫‪153‬‬
‫‪ ‬‬

151.

‫جست و جوی اگاهانه و اک تشاف‬
‫اثر دقت اک تشاف بر کاراي ي‬
‫فاک تور انشعاب مؤثر‬
‫هزينه جست و جو‬
‫‪154‬‬
‫ميانگين گره های بسط يافته در جستجوی‪ IDS‬و *‪ A‬و فاک تور انشعاب مؤثر با استفاده از‪ h1‬و ‪h2‬‬

152.

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

153.

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

154.

‫جست و جوی اگاهانه و اک تشاف‬
‫الگوريتم های جست و جوی محلی و بهينه سازی‬
‫‪157‬‬

155.

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

156.

‫اين سياست ساده‪ ،‬سه زيان عمده دارد‪:‬‬
‫‪ :Local Maxima ‬يک ماکزيمم محلي‪ ،‬برخاف ماکزيمم عمومي‪ ،‬قلهاي است که پائينتر از بلندترين قله‬
‫درفضاي حالت است‪ .‬زماني که روي ماکزيمم محلي هستيم‪ ،‬الگوريتم توقف خواهد نمود‪ .‬اگرچه راه حل نيز ممکن است دور‬
‫از انتظار باشد‪.‬‬
‫‪ :Plateaux ‬يک فات محوطهاي از فضاي حالت است که تابع ارزياب يکنواخت باشد‪ .‬جستجو يک قدم تصادفي‬
‫را برخواهد داشت‪.‬‬
‫‪ :Ridges ‬نوک کوه‪ ،‬داراي لبههاي سراشيب است‪ .‬بنابراين جستجو به باالي نوک کوه به اساني ميرسد‪ ،‬اما بعد با‬
‫ً‬
‫مستقيما به سمت باالي نوک کوه حرکت کنند‪ .‬جستجو‬
‫مايمت به سمت قله ميرود‪ .‬مگر اينکه عملگرهاي ي موجود باشند که‬
‫ممکن است از لبهاي به لبه ديگر نوسان داشته باشد و پيشرفت کمي را حاصل شود‪.‬‬

157.

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

158.

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

159.

160.

161.

162.

163.

164.

‫هوش مصنوعي‬
‫فصل ششم‬
‫جستجوی خصمانه‬
‫‪167‬‬

165.

‫هوش مصنوعي‬
‫فهرست‬
‫‪168‬‬
‫‪Artificial Intelligence‬‬
‫‪ ‬بازيها چيستند و چرا مطالعه ميشوند؟‬
‫‪ ‬انواع بازيها‬
‫‪ ‬الگوريتم ‪minimax‬‬
‫‪ ‬بازيهای چند نفره‬
‫‪ ‬هرس الفا‪-‬بتا‬
‫‪ ‬بازيهای قطعی با اطالعات ناقص‬
‫‪ ‬بازيهاي ي که حاوی عنصر شانس هستند‬

166.

‫جستجوی خصمانه‬
‫مثال‪ :‬هرس الفا‪-‬بتا‬
‫]∞‪[3,+‬‬
‫این گره برای ‪ Max‬مناسب نیست‬
‫]‪[-∞,2‬‬
‫‪169‬‬
‫]‪[3,3‬‬

167.

‫جستجوی خصمانه‬
‫اثر افق‬
‫‪ ‬وقت ی بوج ود م ي اي د ک ه برنام ه ب ا اث ری از رقي ب‬
‫مواجه شود که منجر به خرابی جدی گش ته و اجتن اب‬
‫پذير است‬
‫‪ ‬مثال‪ :‬شکل مقابل؛‬
‫س ياه در اص ل جلوس ت‪ ،‬ام ا اگ ر س فيد پي اده اش را از‬
‫سطر هفتم به هشتم ببرد‪ ،‬پي اده ب ه وزي ر تب ديل ميش ود‬
‫و موقعيت برد برای سفيد بوجود مي ايد‬
‫‪170‬‬

168.

‫هوش مصنوعي‬
‫فصل هفتم‬
‫عامل های منطقی‬
‫‪171‬‬

169.

‫هوش مصنوعي‬
‫فهرست‬
‫‪Artificial Intelligence‬‬
‫‪ ‬عاملهای مبتنی بر دانش‬
‫‪ ‬منطق‬
‫‪ ‬منطق گزاره ای‬
‫‪ ‬الگوهای استدالل در منطق گزاره ای‬
‫‪ ‬الگوريتم ‪resolution‬‬
‫‪ ‬زنجير پيشرو و عقبگرد‬
‫‪172‬‬

170.

‫عاملهای منطقی‬
‫عاملهای مبتنی بر دانش‬
‫‪ ‬مؤلفه اصلي عامل مبتنی بر دانش‪ ،‬پايگاه دانش ان است‬
‫‪ ‬پايگاه دانش‪ :‬مجموعه ای از جمات‬
‫‪ ‬جمله‪ :‬زبان نمايش دانش و بيان ادعاهاي ي در مورد جهان‬
‫محدوده الگو ِريتمهای مستقل‬
‫خاص‬
‫اطالعات‬
‫محدوده‬
‫خاص‬
‫اطالعات‬
‫محدوده‬
‫‪ ‬برای اضافه کردن جمات به پايگاه دانش و درخواست دانسته ها‬
‫‪TELL ‬و ‪ASK‬‬
‫‪ ‬هر دو ممکن است شامل استنتاج باشند‬
‫‪173‬وی‪:‬انجام فرايند استنتاج تحت مقررات خاص‬
‫‪ ‬پير‬
‫‪ask‬‬
‫بخش استنتاج‬
‫پايگاه دانش‬
‫‪tell‬‬

171.

‫عاملهای منطقی‬
‫عاملهای مبتنی بر دانش‬
‫‪ ‬عامل مبتنی بر دانش بايد بتواند‪:‬‬
‫‪ ‬نمايش حاالت و فعاليتها‬
‫‪ ‬ترکيب ادراکات جديد‬
‫‪ ‬بروز کردن تصور داخلی خود از جهان‬
‫‪ ‬استنباط خصوصيات مخفی جهان‬
‫‪ ‬استنتاج فعاليتهای مناسب‬
‫‪ ‬عامل پايگاه دانش خيلی شبيه به عاملهاي ي با حالت درونی است‬
‫‪ ‬عاملها در دو سطح متفاوت تعريف ميشوند‪:‬‬
‫‪ ‬سطح دانش‪ :‬عامل چه چيزی ميداند و اهداف ان کدامند؟‬
‫‪ ‬سطح پياده سازی‪ :‬ساختمان داده اطاعات پايگاه دانش و چگونگی دستکاری انها‬
‫‪174‬‬

172.

‫عاملهای منطقی‬
‫‪ ‬معيار کاراي ي‪:‬‬
‫جهان ‪WUMPUS‬‬
‫‪ +1000 ‬انتخاب طا‪ -1000 ،‬افتادن در گودال يا خورده شدن‪ -1 ،‬هر‬
‫مرحله‪ -10 ،‬برای استفاده از تير‬
‫‪ ‬محيط‪:‬‬
‫‪ ‬بوی تعفن در مربعهای همجوار ‪WUMPUS‬‬
‫‪ ‬نسيم در مربعهای همجوار گودال‬
‫‪ ‬درخشش در مربع حاوی طا‬
‫‪ ‬کشته شدن ‪ WUMPUS‬با شليک در صورت مقابله‬
‫‪ ‬تير فقط مستقيم عمل ميکند‬
‫‪ ‬برداشتن و انداختن طا‬
‫‪ ‬حسگرها‪:‬‬
‫‪ ‬بو تعفن‪ ،‬نسيم‪ ،‬تابش‪ ،‬ضربه‪ ،‬جيغ زدن‬
‫‪ ‬محرکها‪:‬‬
‫‪ ‬گردش به چ‪ ،،‬گردش به راست‪ ،‬جلو رفتن‪ ،‬برداشتن‪ ،‬انداختن‪ ،‬شليک‬
‫‪175‬‬
‫کردن‬

173.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫قابل مشاهده کامل‪ :‬خير‪ ,‬فقط ادراک محلي‬
‫قطعی‪ :‬بله‪ ،‬نتيجه دقيقا مشخص است‬
‫رويدادی‪ :‬خير‪ ،‬ترتيبي از فعاليتهاست‬
‫ايستا‪ :‬بله‪ WUMPUS ,‬و گودالها حرکت ندارند‬
‫گسسته‪ :‬بله‬
‫تک عامله‪ :‬بله‪ WUMPUS ،‬در اصل يک خصوصيت طبيعي است‬
‫‪176‬‬

174.

‫عاملهای منطقی‬
‫کاوش در جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪177‬‬

175.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪178‬‬

176.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪179‬‬

177.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪180‬‬

178.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪181‬‬

179.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪182‬‬

180.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪183‬‬

181.

‫عاملهای منطقی‬
‫توصيف جهان ‪WUMPUS‬‬
‫عامل = ‪A‬‬
‫نسيم = ‪B‬‬
‫درخشش‪،‬طال = ‪G‬‬
‫مربع امن = ‪OK‬‬
‫گودال = ‪P‬‬
‫تعفن = ‪S‬‬
‫مالقات شده = ‪V‬‬
‫‪W = Wumpus‬‬
‫‪184‬‬

182.

‫عاملهای منطقی‬
‫منطق‬
‫‪ ‬يک زبان رسمي‪:‬‬
‫‪ ‬ترکيب(نحو)‪ :‬چه کلمه بندی صحيح است‪(.‬خوش فرم)‬
‫‪ ‬معناشناسی‪ :‬يک کلمه بندی صحيح چه معناي ي دارد‬
‫‪ ‬در منطق‪ ،‬معنای زبان‪ ،‬درستی هر جمله را در برابر هر جهان ممکن تعريف ميکند‬
‫‪ ‬مثال‪ ،‬در زبان رياضيات‬
‫‪ X+2 >= y ‬يک جمله اما ‪ x2+y‬جمله نيست‬
‫‪ X+2 >= y ‬در جهان درست است اگر ‪ x=7‬و ‪y =1‬‬
‫‪ X+2 >= y ‬در جهان غلط است اگر ‪ x=0‬و ‪y =6‬‬
‫‪185‬‬

183.

‫عاملهای منطقی‬
‫استلزام‬
‫‪ ‬استلزام منطقي بين جمات اين است که جمله ای بطور منطقي از جمله ديگر پيروی ميکند‬
‫‪a╞b‬‬
‫‪ ‬جمله ‪ a‬استلزام جمله ‪ b‬است‬
‫‪ ‬جمله ‪ a‬جمله ‪ b‬را ايجاد ميکند‬
‫‪ ‬اگر و فقط اگر‪ ،‬در هر مدلي که ‪ a‬درست است‪ b ،‬نيز درست است‬
‫‪ ‬اگر ‪ a‬درست باشد‪ b ،‬نيز درست است‬
‫‪ ‬درستی ‪ b‬در درستي ‪ a‬نهفته است‬
‫‪ ‬مثال‪ :‬جمله ‪ x+y=4‬مستلزم جمله ‪ 4=x+y‬است‬
‫‪186‬‬

184.

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

185.

‫عاملهای منطقی‬
‫منطق گزاره ای‬
‫‪188‬‬

186.

‫عاملهای منطقی‬
‫جدول درستی پنج رابطه منطقی‬
P
Q
┐P
P ^ Q P ν Q P=>Q P Q
F
F
T
F
F
T
T
F
T
T
F
T
T
F
T
F
F
F
T
F
F
T
T
F
T
T
T
T
189

187.

‫عاملهای منطقی‬
‫منطق گزاره ای در دنيای ‪Wumpus‬‬
‫در ‪ B1,1‬نسيمي وجود دارد‬
‫)‪B1,1 (P1,2 ν P2,1‬‬
‫در ]‪ [1,1‬گودالی وجود ندارد‬
‫‪R1: ┐P1,1‬‬
‫‪190‬‬

188.

‫عاملهای منطقی‬
‫الگوهای استدالل در منطق گزاره ای‬
‫‪ ‬قوانين استنتاج‪ :‬الگوهاي ي استاندارد که زنجيره ای از نتايج را برای رسيدن به هدف ايجاد ميکند‬
‫‪ ‬قياس استثناي ي‪ :‬با استفاده از ترکيب عطفی‪ ،‬ميتوان هر عطف را استنتاج کرد(يعنی هر وقت جمله ای به شکل‬
‫‪ a=>b‬داده شود‪ ،‬جمله ‪ b‬را ميتوان استنتاج کرد‪).‬‬
‫‪ ‬ميتوان از‬
‫)‪(WumpusAhead ^ WumpusAlive‬‬
‫و‬
‫‪(WumpusAhead ^ WumpusAlive) => Shoot‬‬
‫‪ Shoot‬را استنتاج کرد‬
‫‪191‬‬
‫‪ , ‬‬
‫‪ ‬‬

189.

‫عاملهای منطقی‬
‫‪ ‬حذف ‪ :and‬هر عطف را ميتوان از ترکيب عطفی استنتاج کرد‬
‫مثال‪ WumpusAlive :‬را ميتوان از جمله زير استناج کرد‬
‫)‪(WumpusAhead ^ WumpusAlive‬‬
‫خاصيت يکنواختی‬
‫‪ ‬‬
‫‪ ‬‬
‫مجموعه ای از جمات استلزامی که فقط ميتواند در صورت اضافه شدن اطاعات به پايگاه دانش رشد کند‪.‬‬
‫برای جمات ‪ a‬و ‪ b‬داريم‪:‬‬
‫‪192‬‬
‫‪KB | KB | ‬‬

190.

‫هوش مصنوعي‬
‫فصل هشتم‬
‫منطق رتبه اول‬
‫‪193‬‬

191.

‫هوش مصنوعي‬
‫‪Artificial Intelligence‬‬
‫فهرست‬
‫‪ ‬مروری بر منطق گزاره ای‬
‫‪ ‬منطق رتبه اول‬
‫‪ ‬انواع منطق‬
‫‪ ‬نحو و معنای منطق رتبه اول‬
‫‪ ‬مهندسی دانش‬
‫‪194‬‬

192.

‫منطق رتبه اول‬
‫مروری بر منطق گزاره ای‬
‫‪ ‬ويژگيها‬
‫‪ ‬ماهيت اعانی‬
‫‪ ‬دانش و استنتاج متمايزند و استنتاج ً‬
‫کاما مستقل از دامنه است‬
‫‪ ‬قدرت بيان کافی برای اداره کردن اطاعات جزئي‬
‫‪ ‬با استفاده از ترکيب فصلی و نقيض‬
‫‪ ‬قابليت ترکيب‬
‫‪ ‬معنای جمله‪ ،‬تابعي از معنای بخشهای ان‬
‫‪ ‬معنا‪ ،‬مستقل از متن است‬
‫‪ ‬بر خاف زبانهای طبيعي که‪ ،‬معنای جمات وابسته به متن است‬
‫‪ ‬معايب‬
‫‪ ‬فاقد قدرت بياني برای تشريح دقيق محيطی با اشياي مختلف‬
‫‪195‬‬
‫‪ ‬بر خاف زبانهای طبيعی‬

193.

‫منطق رتبه اول‬
‫منطق رتبه اول‬
‫‪ ‬اساس منطق گزاره ای را پذيرفته و بر اساس ان يک منطق بيانی ميسازيم‬
‫‪ ‬از ايده های نمايشي زبان طبيعي استفاده کرده‪ ،‬از عيوب ان اجتناب ميکنيم‬
‫‪ ‬زبانهای طبيعی از جهان طبقه بندی زير را دارند‬
‫نگها‪،‬اتش و‬
‫فوتبال‪،‬‬
‫بازيهای‬
‫اعداد‪،‬ر راد‪،‬نگها‪،‬‬
‫بازيهای‪...‬فوتبال‪ ،‬اتش و ‪...‬‬
‫اعداد‪ ،‬ر‬
‫خانه‪،‬‬
‫خانه‪،‬اشياء‪ :‬اف‬
‫اشياء‪ :‬افراد‪ ،‬‬
‫رابطه ها‪ :‬رابطه ها‪:‬‬
‫مثلو ‪...‬‬
‫خواصاول‬
‫قرمز‪ ،‬گرد‪،‬‬
‫هایمثل‬
‫خواص‬
‫قرمز‪ ،‬گرد‪ ،‬اول و ‪...‬‬
‫يکاني يا‬
‫رابطه های يکاني‪ ‬يارابطه‬
‫مالکيت و ‪...‬‬
‫بودن‪،‬‬
‫بودن‪،‬ي بزرگ‬
‫مثل بر‬
‫رابطه های چندتاي‬
‫بخشی از‪ ،‬مالکيت و ‪...‬‬
‫از‪ ،‬بودن‪،‬‬
‫بخشیرگ تر‬
‫بودن‪ ،‬بز‬
‫مثل بتررادر‬
‫هایادرچندتاي‬
‫‪ ‬ريابطه‬
‫بيشتر از و‬
‫بودن‪،‬يکي‬
‫دوست‪،‬‬
‫توابع‪ :‬پدر بودن‪،‬‬
‫دوست‪ ...،‬يکي بيشتر از و ‪...‬‬
‫بهترين‬
‫بهترينپدر‬
‫‪ ‬توابع‪:‬‬
‫‪ ‬منطق رتبه اول توسط اشيا و رابطه ها ساخته ميشود‬
‫‪196‬‬

194.

‫منطق رتبه اول‬
‫انوام منطق‬
‫هستی شناسی‬
‫حقيقت شناسی‬
‫(انچه در جهان هست)‬
‫(اعتقادات عامل راجع به حقايق)‬
‫منطق گزاره ای‬
‫منطق رتبه اول‬
‫حقايق‬
‫حقايق‪ ،‬اشيا‪ ،‬رابطه ها‬
‫درست‪/‬نادرست‪/‬نامشخص‬
‫درست‪/‬نادرست‪/‬نامشخص‬
‫منطق موقتی‬
‫حقايق‪ ،‬اشيا‪ ،‬رابطه ها‪ ،‬زمان‬
‫درست‪/‬نادرست‪/‬نامشخص‬
‫نظريه احتمال‬
‫حقايق‬
‫حقايق با درجه ای از درستی متعلق به‬
‫]‪[0,1‬‬
‫درجه ای از اعتقاد متعلق به ]‪[0,1‬‬
‫زبان‬
‫منطق فازی‬
‫‪197‬‬
‫در فاصله معين‬

195.

‫منطق رتبه اول‬
‫نحو و معنای منطق رتبه اول‬
‫‪ ‬نمادهای ثابت؛ اشيا را نشان ميدهد‪ .‬مثال‪ :‬علی‪ ،2 ،‬رضا‪... ،‬‬
‫‪ ‬نمادهای محمول؛ رابطه ها را نشان ميدهد‪ .‬مثال‪:‬برادر بودن‪ ،‬بزرگ تر بودن از‬
‫‪ ‬نمادهای تابع؛ توابع را نشان ميدهند‪ .‬مثال‪ :‬تابع پای چ‪)LeftLeg(،‬‬
‫‪ ‬متغيرها‪x , y , a ,b :‬‬
‫‪ ‬روابط منطقی‪ , , , , :‬‬
‫‪ ‬تساوی‪= :‬‬
‫‪ ‬سورها‪ , :‬‬
‫‪198‬‬

196.

‫منطق رتبه اول‬
‫جمات اتميک‬
‫‪ ‬هر ترم يک عبارت منطقی است که به شيئ اشاره ميکند‬
‫‪ ‬نمادهای ثابت ترم هستند‬
‫‪ ‬هميشه استفاده از نماد متمايز برای نامگذاری شیء اسان نيست‬
‫)‪LeftLeg(John‬‬
‫‪ ‬پای چ‪ ،‬پای پادشاه ‪John‬‬
‫‪.‬‬
‫متغير‬
‫ثابت‬
‫يا‬
‫يا )ترم‪ ،1‬ترم‪ ، ... ،2‬ترم‪(n‬تابع = ترم‬
‫‪ ‬جمات اتميک‪ :‬ترکيب ترمهای اشياء و محولهای روابط‬
‫‪.‬‬
‫ترم‪ =2‬ترم‪1‬‬
‫‪ ‬مثال‪:‬‬
‫‪199‬‬
‫يا‬
‫)ترم‪ ،1‬ترم‪ ، ... ،2‬ترم‪(n‬محمول = جمالت اتميک‬
‫))‪Married(Father(Richard),Mother(John‬‬
‫پدر ريچارد با مادر جان ازدواج کرده است‬

197.

‫منطق رتبه اول‬
‫جمات پيچيده‬
‫با ترکيب جمات اتميک و روابط منطقی ميتوان جمات پيچيده تری ساخت‬
S, S1 S2, S1 S2, S1 S2, S1 S2
Brother(LeftLeg(Richard),John)
:‫مثال‬
Brother(Richard,John) Brother(John,Richard)
King(Richard) King(John)
King(Richard) King(John)
200

198.

‫منطق رتبه اول‬
‫‪ ‬مثال‬
‫مدلی با پنج شیء‪،‬‬
‫دو رابطه دودوي ي‪،‬‬
‫سه رابطه يکانی و‬
‫يک تا يکانی به نام‬
‫پای چ‪،‬‬
‫‪201‬‬

199.

‫منطق رتبه اول‬
‫سورها‬
‫‪ ‬کمک ميکنند تا به جای شمارش اشيا از طريق نام انها‪ ،‬خواص کلکسيون اشيا را‬
‫بيان کرد‬
‫‪ ‬سور عمومی؛ ‪“ ‬برای همه”‬
‫‪ ‬سور وجودی؛ ‪ “ ‬وجود دارد حداقل‪”...‬‬
‫‪202‬‬

200.

‫منطق رتبه اول‬
‫سور عمومی‬
‫>جمله< >متغيرها<‪ ‬‬
‫‪ x P ‬که در ان ‪ P‬يک عبارت منطقي است‪ ،‬بيان ميکند که ‪ P‬برای‬
‫هر شیء ‪ x‬درست است‬
‫‪ ‬مثال‪:‬‬
‫‪203‬‬
‫)‪ x King(x) Person(x‬‬

201.

‫منطق رتبه اول‬
‫سور وجودی‬
‫>جمله< >متغيرها< ‪ ‬‬
‫‪ x P ‬که در ان ‪ P‬يک عبارت منطقي است‪ ،‬بيان ميکند که ‪P‬‬
‫حداقل برای يک شیء ‪ x‬درست است‬
‫‪ ‬مثال‪ x Crown(x) OnHead(x , John) :‬‬
‫‪204‬‬

202.

‫منطق رتبه اول‬
‫خصوصيات سورها‬
‫‪ ‬رابط طبيعي برای کار با ‪ ‬و ‪ ‬رابط طبيعي برای کار با ‪ ‬ميباشد‬
‫‪ ‬استفاده از ‪ ‬بعنوان رابط اصلی با ‪ ‬منجر به حکم قوی ميشود‬
‫‪ ‬استفاده از ‪ ‬با ‪ ‬منجر به حکم ضعيفي ميشود‬
‫‪ x y ‬برابر است با‪ y x‬و ‪ x y‬برابر است با ‪ y x‬‬
‫‪ x y ‬برابر نيست با‪ y x‬‬
‫‪ x y Loves(x,y) ‬‬
‫‪ ‬حداقل يک نفر وجود دارد که همه چيز در جهان را دوست دارد‬
‫‪ y x Loves(x,y) ‬‬
‫‪ ‬همه در دنيا حداقل يک نفر را دوست دارند‬
‫‪205‬‬

203.

‫منطق رتبه اول‬
‫خصوصيات سورها‬
‫‪“ ‬هر کسی بستنی را دوست دارد” به معنای اين است که “هيچ کس وجود ندارد که بستنی را‬
‫دوست نداشته باشد”‬
‫‪ x Likes(x , IceCream) ‬هم ارز )‪ x Likes(x , IceCream‬‬
‫‪ x P ‬هم ارز ‪ x P‬‬
‫‪ x P ‬هم ارز ‪ x P‬‬
‫‪ x P ‬‬
‫هم ارز ‪ x P‬‬
‫‪ x P ‬‬
‫هم ارز ‪ x P‬‬
‫‪206‬‬

204.

‫منطق رتبه اول‬
‫تساوی‬
‫‪ ‬با استفاده از = دو ترم به يک شیء اشاره ميکنند‬
‫‪ ‬برای تعيين درستی جمله تساوی بايد ديد که ايا ارجام ها به دو ترم‪ ،‬اشيای‬
‫يکسانی اند يا خير‬
‫‪ ‬مثال‪ :‬ريچارد حداقل دو برادر دارد‬
‫)‪ x,y Brother(x,Richard) ^ Brother(y,Richard) ^ (x=y‬‬
‫‪207‬‬

205.

‫منطق رتبه اول‬
‫ادعاها و تقاضاها‬
‫‪ ‬جمات از طريق ‪ TELL‬به پايگاه دانش اضافه ميشوند‬
‫‪ ‬اين جمات را ادعا گويند‬
‫‪TELL (KB , King(John)) ‬‬
‫‪TELL (KB , x King(x) => Person(x)) ‬‬
‫‪ ‬با استفاده از ‪ ASK‬تقاضاهاي ي را از پايگاه دانش انجام ميدهيم‬
‫‪ ‬اين پرسشها‪ ،‬تقاضا يا هدف نام دارد‬
‫‪ASK (KB , Person(John)) ‬‬
‫‪ASK(KB , x Person(x)) ‬‬
‫‪ ‬ليست جانشيني يا انقياد‬
‫‪ ‬ليستي از جانشينيها در صورت وجود بيش از يک پاسخ‬
‫‪208‬‬

206.

‫منطق رتبه اول‬
‫دامنه خويشاوندی‬
‫‪ ‬مادر هر فرد والد مؤنث ان فرد است‬
‫‪ m,c Mother(c) = m Femail(m) ^ Parent(m,c) ‬‬
‫‪ ‬شوهر هر فرد‪ ،‬همسر مذکر ان فرد است‬
‫‪ w,h Husband(h,w) Male(h) ^ Spouse(h,w) ‬‬
‫‪ ‬مذکر و مؤنث بودن طبقه های متمايزی هستند‬
‫‪ x, Male(x) Female(x) ‬‬
‫‪ ‬والد و فرزند‪ ،‬رابطه های معکوس هستند‬
‫‪ p,c Parent(p,c) Child(c,p) ‬‬
‫والدين والدين هر فرد است‬
‫‪ ‬پدر بزرگ يا مادربزرگ‬
‫ِ‬
‫‪ g,c Grandparent(g,c) p Parent(g,p) ^ Parent(p,c) ‬‬
‫‪209‬‬

207.

‫منطق رتبه اول‬
‫اعداد و مجموعه ها‬
s Set(s) (s = {} ) ( x,s2 Set(s2) s = {x|s2})
x,s {x|s} = {}
x,s x s s = {x|s}
x,s x s [ y,s2} (s = {y|s2} (x = y x s2))]
210

208.

‫منطق رتبه اول‬
‫مهندسي دانش‬
‫‪ ‬فرايند کلی ساخت پايگاه دانش که شامل مراحل ذيل ميباشد‪:‬‬
‫‪ ‬مشخص کردن کار‬
‫‪ ‬مونتاژ دانش مربوطه‬
‫‪ ‬تصميم گيری در مورد واژه نامه محمولها‪ ،‬توابع و وراثت‬
‫‪ ‬کدگزاری دانش کلی در مورد دامنه‬
‫‪ ‬کد گزاری توصيف نمونه مسئله خاص‬
‫‪ِ ‬اعمال تقاضاها به رويه استنتاج و دريافت پاسخ‬
‫‪211‬‬
‫‪ ‬اشکال زداي ي پايگاه دانش‬
English     Русский Правила