1
هوش مصنوعی(مرجع)
نام مرجع :
Artificial Intelligence A Modern Approach
2
هوش مصنوعی
فصل اول
مقدمه
هوش مصنوعی Artificial Intelligence
فهرست
هوش مصنوعی چیست؟
مبانی هوش مصنوعی
تاریخچه هوش مصنوعی
4
مقدمه
هوش مصنوعی چیست؟
مانند انسان فکر کردن
مانند انسان عمل کردن
عاقلانه عمل کردن
عاقلانه فکر کردن
5
مقدمه
مانند انسان عمل کردن Acting humanly
هنر ساخت ماشینهایی که کارهایی را انجام میدهند که آن کارها توسط انسان با فکر کردن انجام میشوند.
مطالعه برای ساخت کامپیوترها برای انجام کارهایی که فعلاً انسان آنها را بهتر انجام میدهد.
6
مقدمه (مانند انسان عمل کردن)
تست تورینگ
A
B
کدام انسان است؟
A یا B
7
مقدمه
مانند انسان فکر کردن Thinking humanly
تلاش جدید و هیجان انگیز برای ساخت ماشین هایی متفکر و با حس کامل
خودکارسازی فعالیت های مرتبط با تفکر انسان، فعالیتهایی مثل تصمیم گیری، حل مسئله، یادگیری
8
مقدمه
عاقلانه فکر کردن Think rationally
مطالعه توانایی های ذهنی از طریق مدل های محاسباتی (منطق گرایی)
مطالعه محاسباتی که منجر به درک و استدلال می شود.
9
مقدمه
عاقلانه عمل کردن Act rationally
طوری عمل کند که بهترین نتیجه را ارائه دهد
هوش محاسباتی، مطالعه طراحی عامل های هوشمند است
10
مقدمه
مبانی هوش مصنوعی
فلسفه: منطق، استدلال، ناشی شدن تفکر از مغز فیزیکی، مبانی یادگیری، زبان و عقلانیت
ریاضیات: نمایش رسمی الگوریتمها، محاسبات، تصمیم پذیری و تصمیم ناپذیری، احتمال
روان شناسی: تطبیق، اثر طبیعی ادراک و تاثیر آن بر محیط
زبان شناسی: علم ارائه، گرامر
11
مقدمه
اقتصاد: نظریه تصمیمهای عقلایی، نظریه بازی
علوم عصبی: نحوه پردازش اطلاعات توسط مغز
نظریه کنترل و سیبرنتیک: تحت کنترل در آوردن محصولات مصنوعی، ثبات و پایداری، طراحی عامل بهینه
مهندسی کامپیوتر: ساخت کامپیوترهای سریع
مبانی هوش مصنوعی
12
مقدمه
تاریخچه هوش مصنوعی
1943، مک کولوچ و والتر پیتز: ارایه مدل نرون مصنوعی بیتی( دو حالته) قابل یادگیری به منظور محاسبه هر تابع قابل محاسبه.
1950، آلن تورینگ اولین بار دید کاملی از هوش مصنوعی را تحت عنوان “ محاسبات ماشینی و هوشمند” ارایه نمود.
1951، هینسکی و ادموندز اولین کامپیوتر شبکه عصبی را طراحی کردند.
1952، آرتور سامویل: برنامه ای ساخت که یاد میگرفت بهتر از نویسنده اش بازی کند؛ در نتیجه این تصور را که “کامپیوتر فقط کاری را انجام میدهد که به آن گفته شود” نقض کرد.
13
مقدمه (تاریخچه هوش مصنوعی)
1956،نشست کارگروهی دورتموند: انتخاب نام هوش مصنوعی
1959، هربرت جلونتر: برنامه(GTP) را ساخت که قضایا را با اصل موضوعات مشخص ثابت می کرد.
1958، جان مک کارتی: تعریف زبان لیسپ که بهترین زبان هوش مصنوعی شد.
1958-1973، جیمز اسلاگل: برنامه حل مسایل انتگرالگیری فرم بسته
تام ایوانز: برنامه حل مشابهت های هندسی
دانیل بابروز: برنامه حل مسایل جبری
دیوید هافمن: پروژه محدوده بینایی روبات در جهان بلوکها
دیوید والتز: سیستم بینایی و انتشار محدود
پاتریک ونیستون: نظریه یادگیری
14
مقدمه (تاریخچه هوش مصنوعی)
(1973-1966) کند شدن مسیر تحقیقات هوش مصنوعی
پیچیده شدن الگوریتم برنامه های جدید
برنامه ترجمه متون
انجام ناپذیری بسیاری از مسائلی که سعی در حل آنها بود
عدم موفقیت اثبات قضایا با مفروضات بیشتر
بکارگیری بعضی محدودیتها روی ساختارهای اساسی
محدودیت نمایش پرسپترون دو ورودی
15
مقدمه (تاریخچه هوش مصنوعی)
(1969- 1979) سیستم های مبتنی بر دانش
جست و جوی همه منظوره که سعی بر یادگیری داشت تا پیمودن راه حل کامل
مثل برنامه DENDRAL، بوچانان و همکارانش در سال 1969
مزیت برنامه DENDRAL این بود که اولین سیستم پاداش غنی بود
متدولوژی جدید سیستم خبره
مثل سیستم MYCIN که برای تشخیص عفونتهای خونی طراحی شد
استفاده از فاکتورهای قطعیت
افزایش تقاضا برای شِمای نمایش دانش
استفاده از منطق در پرولوگ، استفاده از ایده مینسکی یعنی قابها و …
16
مقدمه (تاریخچه هوش مصنوعی)
1980 تا کنون: تبدیل هوش مصنوعی به یک صنعت
1986 تاکنون: برگشت به شبکه های عصبی
1987 تاکنون: هوش مصنوعی به علم تبدیل میشود
1995 تاکنون: ظهور عاملهای هوشمند
17
هوش مصنوعی
فصل دوم
عاملهای هوشمند
18
هوش مصنوعی Artificial Intelligence
فهرست
عامل
خواص محیطهای وظیفه
برنامه های عامل
19
عاملهای هوشمند
تابع عامل
رفتار عامل توسط تابع عامل توصیف میشود که هر دنباله ادراک را به یک فعالیت نقش میکند.
دنباله ادراک
سابقه کامل هر چیزی است که عامل تاکنون درک کرده است.
فعالیت دنباله ادراک : تابع عامل
20
عاملهای هوشمند
عامل
حسگرها
محرکها
?
محیط
ادراک ها
فعالیت ها
عامل
21
عاملهای هوشمند
معیارهای کارایی
معیار کارایی، معیاری برای موفقیت رفتار عامل است.
بر اساس خواسته های فرد در محیط انتخاب میشود
معیار کارایی که ملاکهای موفقیت را تعریف میکند
دانش قبلی عامل نسبت به محیط
فعالیتهایی که عامل میتواند انجام دهد
دنباله ادراک عامل در این زمان
رفتار عقلایی
22
عاملهای هوشمند
عامل عالـِم Omni science))
خروجی واقعی فعالیت خود را میداند و میتواند بر اساس آن عمل کند
عامل خردمند (Rational agent)
فعالیتی را انتخاب میکند که معیار کارایی اش را حداکثر میکند
جمع آوری اطلاعات، اکتشاف، یادگیری
عامل خود مختار
نقص دانش قبلی خود را میتواند جبران کند
23
عاملهای هوشمند
خواص
محیط های وظیفه
کاملاً قابل مشاهده درمقابل قابلیت مشاهده جزئی
قطعی درمقابل غیر قطعی
راهبردی
رویدادی درمقابل ترتیبی
ایستا درمقابل پویا
گسسته درمقابل پیوسته
تک عاملی درمقابل چند عاملی
چند عاملی رقابتی درمقابل چندعاملی همیاری
24
عاملهای هوشمند
ساختار عاملها
برنامه + معماری = عامل
کار هوش مصنوعی طراحی برنامه عامل است که تابع عامل را پیاده سازی میکند
برنامه های عامل
عاملهای واکنشی ساده
عاملهای هدف گرا
عاملهای واکنشی مدل گرا
عاملهای سودمند
25
عاملهای واکنشی ساده
عاملهای هوشمند
عامل
محیط
حسگرها
جهان چگونه است
محرکها
قانون
شرط عمل
اکنون چه عملی باید انجام دهم
این عاملها فعالیت را بر اساس درک فعلی و بدون در نظر گرفتن سابقه ادراک، انتخاب میکند
به خاطر حذف سابقه ادراک برنامه عامل در مقایسه با جدول آن بسیار کوچک است
انتخاب فعالیت بر اساس یکسری قوانین موقعیت شرطی انجام میشود
26
عاملهای هوشمند
function REFLEX-VACUUM-AGENT ([location, status]) return an action
if status == Dirty then return Suck
else if location == A then return Right
else if location == B then return Left
مثالی از عامل واکنشی ساده در دنیای جاروبرقی
تصمیم گیری آن بر اساس مکان فعلی و کثیف بودن آن مکان صورت میگیرد
در برنامه عامل در مقایسه با جدول آن، تعداد حالتهای ممکن از 4 به 4 کاهش می یابد
انتخاب فعالیت بر اساس موقعیت شرطی:
If dirty then suck
T
27
عاملهای هوشمند
عاملهای واکنشی مدل گرا
عامل
محیط
حسگرها
جهان چگونه است
محرکها
قانون
شرط عمل
اکنون چه عملی باید انجام دهم
استفاده از دانش “چگونگی عملکرد جهان” که مدل نام دارد
عامل بخشی از دنیایی را که فعلا میبیند ردیابی میکند
عامل باید حالت داخلی را ذخیره کند که به سابقه ادراک بستگی دارد
در هر وضعیت, عامل میتواند توصیف جدیدی از جهان را کسب کند
حالت
جهان چگونه تکامل می یابد
کار فعالیت چیست
28
عاملهای هوشمند
عاملهای هدف گرا
عامل
محیط
حسگرها
جهان چگونه است
محرکها
اهداف
اکنون چه عملی باید انجام دهم
حالت
جهان چگونه تکامل می یابد
کار فعالیت چیست
این عامل علاوه بر توصیف حالت فعلی، برای انتخاب موقعیت مطلوب نیازمند اطلاعات هدف نیز میباشد
جست و جو و برنامه ریزی، دنباله ای از فعالیتها را برای رسیدن عامل به هدف، پیدا میکند
این نوع تصمیم گیری همواره آینده را در نظر دارد و با قوانین شرط عمل تفاوت دارد
این نوع عامل کارایی چندانی ندارد، اما قابلیت انعطاف بیشتری دارد
اگر فعالیت A را انجام دهم چه خواهد شد
29
عاملهای هوشمند
عاملهای سودمند
عامل
محیط
حسگرها
جهان چگونه است
محرکها
سودمند
اکنون چه عملی باید انجام دهم
حالت
جهان چگونه تکامل می یابد
کار فعالیت چیست
این عامل برای اهداف مشخص، راه های مختلفی دارد، که راه حل بهتر برای عامل سودمندتر است.
تابع سودمندی، حالت یا دنباله ای از حالتها را به یک عدد حقیقی نگاشت میکند که درجه رضایت را توصیف مِیکند.
وقتی اهداف متضاد باشند، بعضی از آنها برآورده میشوند
اگر هیچیک از اهداف به طور قطعی قابل حصول نباشند، احتمال موفقیت با اهمیت هدف مقایسه میشود
اگر فعالیت A را انجام دهم چه خواهد شد
در چنین حالتی چقدر رضایت دارم
30
عاملهای هوشمند
عاملهای یادگیرنده
عامل
حسگرها
محرکها
عنصرِِیادگیرنده مسئول ایجاد بهبودها
عنصر کارایی مسئول انتخاب فعالیتهای خارجی
منتقد مشخص میکند که یادگیرنده با توجه به استانداردهای کارایی چگونه عمل میکند
مولد مسئله مسئول پیشنهاد فعالیتهایی است که منجر به تجربیات آموزنده جدیدی میشود
محیط
عنصر یادگیرنده
مولد مسئله
استاندارد کارایی
تغییرات
دانش
31
هوش مصنوعی
فصل سوم
حل مسئله با جستجو
32
هوش مصنوعی Artificial Intelligence
فهرست
عاملهای حل مسئله
مسئله
اندازه گیری کارایی حل مسئله
جستجوی ناآگاهانه
اجتناب از حالتهای تکراری
جستجو با اطلاعات ناقص
33
حل مسئله با جستجو
عاملهای حل مسئله
چهار گام اساسی برای حل مسائل
فرموله کردن هدف: وضعیتهای مطلوب نهایی کدامند؟
فرموله کردن مسئله: چه فعالیتها و وضعیتهایی برای رسیدن به هدف موجود است؟
جستجو: انتخاب بهترین دنباله از فعالیتهایی که منجر به حالاتی با مقدار شناخته شده میشود.
اجرا: وقتی دنباله فعالیت مطلوب پیدا شد، فعالیتهای پیشنهادی آن میتواند اجرا شود.
34
حل مسئله با جستجو
مثال: نقشه رومانی
35
حل مسئله با جستجو
صورت مساله: رفتن از آراد به بخارست
فرموله کردن هدف: رسیدن به بخارست
فرموله کردن مسئله:
وضعیتها: شهرهای مختلف
فعالیتها: حرکت بین شهرها
جستجو: دنباله ای از شهرها مثل:آراد، سیبیو، فاگارس، بخارست
این جستجو با توجه به کم هزینه ترین مسیر انتخاب میشود
مثال: نقشه رومانی
36
حل مسئله با جستجو
مسئله
حالت اولیه: حالتی که عامل از آن شروع میکند.
در مثال رومانی: شهر آراد n(Arad)
تابع جانشین: توصیفی از فعالیتهای ممکن که برای عامل مهیا است.
در مثال رومانی:Zerind,Sibui,Timisoara} S(Arad)={
فضای حالت: مجموعه ای از حالتها که از حالت اولیه میتوان به آنها رسید.
در مثال رومانی: کلیه شهرها که با شروع از آراد میتوان به آنها رسید
تابع جانشین + حالت اولیه = فضای حالت
37
حل مسئله با جستجو
آزمون هدف: تعیین میکند که آیا حالت خاصی، حالت هدف است یا خیر
هدف صریح: در مثال رومانی، رسیدن به بخارست
هدف انتزاعی: در مثال شطرنج، رسیدن به حالت کیش و مات
مسیر: دنباله ای از حالتها که دنباله ای از فعالیتها را به هم متصل میکند.
در مثال رومانی: Arad, Sibiu, Fagaras یک مسیر است
هزینه مسیر: برای هر مسیر یک هزینه عددی در نظر میگیرد.
در مثال رومانی: طول مسیر بین شهرها بر حسب کیلومتر
راه حل مسئله مسیری از حالت اولیه به حالت هدف است
راه حل بهینه کمترین هزینه مسیر را دارد
38
حل مسئله با جستجو
مثال: دنیای جارو برقی
حالتها: دو مکان که هر یک ممکن است کثیف یا تمیز باشند.لذا 8 = 2^2* 2حالت در این جهان وجود دارد
حالت اولیه: هر حالتی میتواند به عنوان حالت اولیه طراحی شود
تابع جانشین: حالتهای معتبر از سه عملیات: راست، چپ، مکش
آزمون هدف: تمیزی تمام مربعها
هزینه مسیر: تعداد مراحل در مسیر
39
حل مسئله با جستجو
مثال: دنیای جارو برقی
حالتها: دو مکان که هر یک ممکن است کثیف یا تمیز باشند.لذا 8 = 2^2* 2حالت در این جهان وجود دارد
حالت اولیه: هر حالتی میتواند به عنوان حالت اولیه طراحی شود
تابع جانشین: حالتهای معتبر از سه عملیات: راست، چپ، مکش
آزمون هدف: تمیزی تمام مربعها
هزینه مسیر: تعداد مراحل در مسیر
40
حل مسئله با جستجو
مثال: معمای8
حالتها: مکان هر هشت خانه شماره دار و خانه خالی در یکی از 9 خانه
حالت اولیه: هر حالتی را میتوان به عنوان حالت اولیه در نظر گرفت
تابع جانشین: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا یا پایین
آزمون هدف: بررسی میکند که حالتی که اعداد به ترتیب چیده شده اند(طبق شکل روبرو) رخ داده یا نه
هزینه مسیر: برابر با تعداد مراحل در مسیر
41
حل مسئله با جستجو
مثال: معمای8
حالتها: مکان هر هشت خانه شماره دار و خانه خالی در یکی از 9 خانه
حالت اولیه: هر حالتی را میتوان به عنوان حالت اولیه در نظر گرفت
تابع جانشین: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا یا پایین
آزمون هدف: بررسی میکند که حالتی که اعداد به ترتیب چیده شده اند(طبق شکل روبرو) رخ داده یا نه
هزینه مسیر: برابر با تعداد مراحل در مسیر
42
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی افزایشی
حالتها: هر ترتیبی از 0 تا 8 وزیر در صفحه، یک حالت است
حالت اولیه: هیچ وزیری در صفحه نیست
تابع جانشین: وزیری را به خانه خالی اضافه میکند
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
در این فرمول بندی باید 14^10*3 دنباله ممکن بررسی میشود
43
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی افزایشی
حالتها: هر ترتیبی از 0 تا 8 وزیر در صفحه، یک حالت است
حالت اولیه: هیچ وزیری در صفحه نیست
تابع جانشین: وزیری را به خانه خالی اضافه میکند
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
در این فرمول بندی باید 14^10*3 دنباله ممکن بررسی میشود
44
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی حالت کامل
حالتها: چیدمان n وزیر (0≤ n≤ 8) ، بطوریکه در هر ستون از n ستون سمت چپ، یک وزیر قرار گیرد و هیچ دو وزیری بهم گارد نگیرند
حالت اولیه: با 8 وزیر در صفحه شروع میشود
تابع جانشین: وزیری را در سمت چپ ترین ستون خالی قرار میدهد، بطوری که هیچ وزیری آن را گارد ندهد
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
این فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش میدهد
45
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی حالت کامل
حالتها: چیدمان n وزیر (0≤ n≤ 8) ، بطوریکه در هر ستون از n ستون سمت چپ، یک وزیر قرار گیرد و هیچ دو وزیری بهم گارد نگیرند
حالت اولیه: با 8 وزیر در صفحه شروع میشود
تابع جانشین: وزیری را در سمت چپ ترین ستون خالی قرار میدهد، بطوری که هیچ وزیری آن را گارد ندهد
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
این فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش میدهد
46
حل مسئله با جستجو
اندازه گیری کارایی حل مسئله
کامل بودن: آیا الگوریتم تضمین میکند که در صورت وجود راه حل، آن را بیابد؟
بهینگی: آیا این راهبرد، راه حل بهینه ای را ارائه میکند.
پیچیدگی زمانی: چقدر طول میکشد تا راه حل را پیدا کند؟
تعداد گره های تولید شده در اثنای جستجو
پیچیدگی فضا: برای جستجو چقدر حافظه نیاز دارد؟
حداکثر تعداد گره های ذخیره شده در حافظه
47
حل مسئله با جستجو
اندازه گیری کارایی حل مسئله
کامل بودن: آیا الگوریتم تضمین میکند که در صورت وجود راه حل، آن را بیابد؟
بهینگی: آیا این راهبرد، راه حل بهینه ای را ارائه میکند.
پیچیدگی زمانی: چقدر طول میکشد تا راه حل را پیدا کند؟
تعداد گره های تولید شده در اثنای جستجو
پیچیدگی فضا: برای جستجو چقدر حافظه نیاز دارد؟
حداکثر تعداد گره های ذخیره شده در حافظه
48
حل مسئله با جستجو
جستجوی ناآگاهانه
ناآگاهی این است که الگوریتم هیچ اطلاعاتی غیر از تعریف مسئله در اختیار ندارد
این الگوریتمها فقط میتواند جانشینهایی را تولید و هدف را از غیر هدف تشخیص دهند
راهبردهایی که تشخیص میدهد یک حالت غیر هدف نسبت به گره غیر هدف دیگر، امید بخش تر است، جست و جوی آگاهانه یا جست و جوی اکتشافی نامیده میشود.
راهبردها
جست و جوی عرضی
جست و جوی عمقی
جست و جوی عمیق کننده تکراری
جست و جوی هزینه یکنواخت
جست و جوی عمقی محدود
جست و جوی دو طرفه
49
حل مسئله با جستجو
جستجوی عرضی
50
حل مسئله با جستجو
جستجوی عرضی
کامل بودن: بله
بهینگی: بله (مشروط)
در صورتی بهینه است که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد.(مثل وقتی که فعالیتها هزینه یکسانی دارند)
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی: بله (مشروط)
51
حل مسئله با جستجو
جستجوی هزینه یکنواخت
این جستجو گره n را با کمترین هزینه مسیر بسط میدهد
52
حل مسئله با جستجو
کامل بودن: بله
هزینه هر مرحله بزرگتر یا مساوی یک مقدار ثابت و مثبت ε باشد.(هزینه مسیر با حرکت در مسیر افزایش می یابد)
بهینگی: بله
هزینه هر مرحله بزرگتر یا مساوی ε باشد
پیچیدگی زمانی:
پیچیدگی فضا:
جستجوی هزینه یکنواخت
کامل بودن:
بهینگی:
53
حل مسئله با جستجو
جستجوی عمقی
2
3
4
5
6
7
54
حل مسئله با جستجو
کامل بودن: خیر
اگر زیر درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل باشد، جستجو هرگز خاتمه نمی یابد.
بهینگی: خیر
پیچیدگی زمانی:
پیچیدگی فضا:
جستجوی عمقی
کامل بودن:
بهینگی:
55
حل مسئله با جستجو
جستجوی عمقی محدود
مسئله درختهای نامحدود میتواند به وسیله جست و جوی عمقی با عمق محدود L بهبود یابد
56
حل مسئله با جستجو
جستجوی عمقی محدود
کامل بودن: خیر
اگر L<d و سطحی ترین هدف در خارج از عمق محدود قرار داشته باشد، این راهبرد کامل نخواهد بود.
بهینگی: خیر
اگر L>d انتخاب شود، این راهبرد بهینه نخواهد بود.
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی:
57
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
58
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
59
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
A
B
C
D
E
F
G
H
I
J
K
L
N
M
O
P
Q
S
R
60
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
کامل بودن: بله
در صورتی که فاکتور انشعاب محدود باشد
بهینگی: بله
وقتی که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی:
61
حل مسئله با جستجو
جستجوی دو طرفه
انجام دو جست و جوی همزمان، یکی از حالت اولیه به هدف و دیگری از هدف به حالت اولیه تا زمانی که دو جست و جو به هم برسند
62
حل مسئله با جستجو
جستجوی دو طرفه
کامل بودن: بله
اگر هر دو جستجو، عرضی باشند و هزینه تمام مراحل یکسان باشد
بهینگی: بله
اگر هر دو جستجو، عرضی باشند و هزینه تمام مراحل یکسان باشد
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی:
63
حل مسئله با جستجو
اجتناب از حالتهای تکراری
وجود حالتهای تکراری در یک مسئله قابل حل، میتواند آن را به مسئله غیر قابل حل تبدیل کند
64
حل مسئله با جستجو
جستجو با اطلاعات ناقص
مسئله های فاقد حسگر: اگر عامل فاقد حسگر باشد، میتواند در یکی از چند حالت اولیه باشد و هر فعالیت میتواند آن را به یکی از چند حالت جانشین ببرد
مسئله های اقتضایی: اگر محیط به طور جزئی قابل مشاهده باشد یا اگر فعالیتها قطعی نباشد، ادراکات عامل، پس از هر عمل، اطلاعات جدیدی را تهیه میکنند. هر ادراک ممکن، اقتضایی را تعریف میکند که باید برای آن برنامه ریزی شود
مسائل خصمانه: اگرعدم قطعیت در اثر فعالیتهای عامل دیگری بوجود آید، مسئله را خصمانه گویند
مسئله های اکتشافی: وقتی حالتها و فعالیتهای محیط ناشناخته باشند، عامل باید سعی کند آنها را کشف کند. مسئله های اکتشافی را میتوان شکل نهایی مسئله های اقتضایی دانست
65
حل مسئله با جستجو
مثال: دنیای جاروبرقی فاقد حسگر
عامل جارو تمام اثرات فعالیتهایش را میداند اما فاقد حسگر است.
حالت اولیه آن یکی از اعضای مجموعه{1،2،3،4،5،6،7،8} میباشد
فعالیت ((Right {2،4،6،8}
فعالیت (Right,Suck) {4،8}
فعالیت (Right,Suck,Left,Suck) تضمین میکند که صرف نظر از حالت اولیه، به حالت هدف، یعنی 7 برسد
66
حل مسئله با جستجو
دنیای جاروبرقی فاقد حسگر
عامل باید راجع به مجموعه های حالتی که میتواند به آنها برسد استدلال کند. این مجموعه از حالتها را حالت باور گوییم.
اگر فضای حالت فیزیکی دارای s حالت باشد فضای حالت باور 2^s حالت باور خواهد داشت.
67
هوش مصنوعی
فصل چهارم
جست و جوی آگاهانه و اکتشاف
68
هوش مصنوعی Artificial Intelligence
فهرست
متدهای جست و جوی آگاهانه
یادگیری برای جست و جوی بهتر
جست و جوی محلی و بهینه سازی
جست و جوی محلی در فضاهای پیوسته
عاملهای جست و جوی Online
69
جست و جوی آگاهانه و اکتشاف
متدهای جستجوی آگاهانه
بهترین جستجو
حریصانه
A*
IDA*
RBFS
MA* و SMA*
جستجوی محلی و بهینه سازی
تپه نوردی
شبیه سازی حرارت
پرتو محلی
الگوریتمهای ژنتیک
70
جست و جوی آگاهانه و اکتشاف
تعاریف
تابع هزینه مسیر، g(n) : هزینه مسیر از گره اولیه تا گره n
تابع اکتشافی، h(n) : هزینه تخمینی ارزان ترین مسیر از گره n به گره هدف
تابع بهترین مسیر، h*(n) : ارزان ترین مسیر از گره n تا گره هدف
تابع ارزیابی، f(n) : هزینه تخمینی ارزان ترین مسیر از طریق n
f(n): g(n) + h(n)
f*(n) : هزینه ارزان ترین مسیر از طریقn f*(n): g(n) + h*(n)
71
جست و جوی آگاهانه و اکتشاف
A
B
C
D
E
F
G
H
I
K
M
L
N
O
3
P
Q
J
W
V
X
Y
Z
R
S
T
U
1
1
2
1
3
3
2
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
1
2
5
3
0
1
3
2
3
1
2
2
1
1
2
1
0
2
1
3
1
2
3
3
2
جستجوی حریصانه
72
جست و جوی آگاهانه و اکتشاف
A
B
C
D
E
F
G
N
O
3
X
1
1
2
1
1
1
1
3
1
2
5
3
0
3
1
3
2
جستجوی حریصانه
73
جست و جوی آگاهانه و اکتشاف
جستجوی حریصانه
A
F
G
H
I
M
L
N
O
P
Q
W
V
X
Y
Z
R
S
T
U
1
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
3
2
3
1
2
2
1
1
2
1
0
2
1
3
1
2
3
3
3
74
جست و جوی آگاهانه و اکتشاف
جستجوی حریصانه
A
75
جست و جوی آگاهانه و اکتشاف
جستجوی حریصانه
کامل بودن: خیر
اما اگر h = h* آنگاه جستجو کامل میشود
بهینگی: خیر
اما اگر h = h* آنگاه جستجو کامل میشود
پیچیدگی زمانی:
اما اگر h = h* آنگاه
پیچیدگی فضا:
اما اگر h = h* آنگاه
کامل بودن:
بهینگی:
76
جست و جوی آگاهانه و اکتشاف
جستجوی A*
A/5
B/4
C/4
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
2
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
1
1
1
1
3
3
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
77
جست و جوی آگاهانه و اکتشاف
جستجوی A*
A/5
78
جست و جوی آگاهانه و اکتشاف
جستجوی A*
A/5
B/1
C/4
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
2
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
1
1
1
1
3
3
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
79
جستجوی A*
جست و جوی آگاهانه و اکتشاف
A/5
80
جستجوی A*
جست و جوی آگاهانه و اکتشاف
A/5
B/1
C/9
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
2
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
1
1
1
1
3
3
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
81
جستجوی A*
جست و جوی آگاهانه و اکتشاف
A/5
82
جستجوی A*
جست و جوی آگاهانه و اکتشاف
کامل بودن: بله
بهینگی: بله
پیچیدگی زمانی:
اما اگر h = h* آنگاه
پیچیدگی فضا:
اما اگر h = h* آنگاه
83
جست و جوی آگاهانه و اکتشاف
h ≤ h*
h ≤ h*
/
جستجوی A*
84
جست و جوی آگاهانه و اکتشاف
جستجوی A*
h ≤ h*
h ≤ h*
/
85
جست و جوی آگاهانه و اکتشاف
A/100
B/80
C/95
E/86
F/78
G/90
T/60
H/80
J/82
N/72
L/80
K/85
W/52
X/58
M/75
Y/47
Z/50
O/78
P/79
D/90
M/75
I/87
P/79
O/78
U/81
V/83
T/60
R/20
W/52
X/58
Y/47
Z/50
S/70
10
جستجوی A* و اجتناب از گره های تکراری
هزینه هر مرحله 10 میباشد
86
جست و جوی آگاهانه و اکتشاف
جستجوی A* و اجتناب از گره های تکراری
A/100
87
جست و جوی آگاهانه و اکتشاف
مثال دیگر از جستجوی A*
f(n)=g(n) + h(n)
88
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
جستجوی Bucharest با شروع از Arad
f(Arad) = g(Arad)+h(Arad)=0+366=366
89
جست و جوی آگاهانه و اکتشاف
جستجوی 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 است
90
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََSibiu را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
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 است
91
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََRimnicu Vilcea را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
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 است
92
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََ Fagaras را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591
f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450
بهترین انتخاب شهر Pitesti !!! است
93
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََ Pitesti را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418
بهترین انتخاب شهر Bucharest !!! است
94
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
95
جست و جوی آگاهانه و اکتشاف
جستجوی اکتشافی با حافظه محدود IDA*
ساده ترین راه برای کاهش حافظه مورد نیاز A* استفاده از عمیق کننده تکرار در زمینه جست و جوی اکتشافی است.
الگوریتم عمیق کننده تکرار A* IDA*
در جستجوی IDA* مقدار برش مورد استفاده، عمق نیست بلکه هزینه f(g+h) است.
IDA* برای اغلب مسئله های با هزینه های مرحله ای، مناسب است و از سربار ناشی از نگهداری صف مرتبی از گره ها اجتناب میکند
96
بهترین جستجوی بازگشتی RBFS
جست و جوی آگاهانه و اکتشاف
ساختار آن شبیه جست و جوی عمقی بازگشتی است، اما به جای اینکه دائما به طرف پایین مسیر حرکت کند، مقدار f مربوط به بهترین مسیر از هر جد گره فعلی را نگهداری میکند، اگر گره فعلی از این حد تجاوز کند، بازگشتی به عقب برمیگردد تا مسیر دیگری را انتخاب کند.
این جستجو اگر تابع اکتشافی قابل قبولی داشته باشد، بهینه است.
پیچیدگی فضایی آن O(bd) است
تعیین پیچیدگی زمانی آن به دقت تابع اکتشافی و میزان تغییر بهترین مسیر در اثر بسط گره ها بستگی دارد.
97
جست و جوی آگاهانه و اکتشاف
بهترین جستجوی بازگشتی RBFS
RBFS تا حدی از IDA* کارآمدتر است، اما گره های زیادی تولید میکند.
IDA* و RBFS در معرض افزایش توانی پیچیدگی قرار دارند که در جست و جوی گرافها مرسوم است، زیرا نمیتوانند حالتهای تکراری را در غیر از مسیر فعلی بررسی کنند. لذا، ممکن است یک حالت را چندین بار بررسی کنند.
IDA* و RBFS از فضای اندکی استفاده میکنند که به آنها آسیب میرساند. IDA* بین هر تکرار فقط یک عدد را نگهداری میکند که فعلی هزینه f است. RBFS اطلاعات بیشتری در حافظه نگهداری میکند
98
جست و جوی آگاهانه و اکتشاف
بهترین جستجوی بازگشتی در نقشه رومانی
99
جست و جوی آگاهانه و اکتشاف
بهترین جستجوی بازگشتی در نقشه رومانی
100
بهترین جستجوی بازگشتی در نقشه رومانی
جست و جوی آگاهانه و اکتشاف
101
جست و جوی آگاهانه و اکتشاف
جستجوی حافظه محدود ساده SMA*
SMA* بهترین برگ را بسط میدهد تا حافظه پر شود. در این نقطه بدون از بین بردن گره های قبلی نمیتواند گره جدیدی اضافه کند
SMA* همیشه بدترین گره برگ را حذف میکند و سپس از طریق گره فراموش شده به والد آن بر میگردد. پس جد زیر درخت فراموش شده، کیفیت بهترین مسیر را در آن زیر درخت میداند
اگر عمق سطحی ترین گره هدف کمتر از حافظه باشد, کامل است.
SMA* بهترین الگوریتم همه منظوره برای یافتن حلهای بهینه میباشد
102
جست و جوی آگاهانه و اکتشاف
جستجوی حافظه محدود ساده SMA*
اگر مقدار f تمام برگها یکسان باشد و الگوریتم یک گره را هم برای بسط و هم برای حذف انتخاب کند، SMA* این مسئله را با بسط بهترین برگ جدید و حذف بهترین برگ قدیمی حل میکند
ممکن است SMA* مجبور شود دائما بین مجموعه ای از مسیرهای حل کاندید تغییر موضع دهد، در حالی که بخش کوچکی از هر کدام در حافظه جا شود
محدودیتهای حافظه ممکن است مسئله ها را از نظر زمان محاسباتی، غیر قابل حل کند.
103
جستجوی گراف با A*
جست و جوی آگاهانه و اکتشاف
2
1
4
1
1
1
1
2
4
3
1
H/0
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
1
104
جست و جوی آگاهانه و اکتشاف
A/6
B/5
C/1
6
5
جستجوی گراف با A*
105
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
G/1
6
5
6
7
106
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
G/1
J/1
6
5
6
7
7
107
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
5
4
4
6
5
6
7
5
7
108
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
5
4
4
6
5
6
7
6
5
7
109
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
4
4
5
6
7
6
5
110
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
H/0
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
5
4
4
6
5
6
7
6
5
6
7
111
جست و جوی آگاهانه و اکتشاف
یادگیری برای جست و جوی بهتر
روشهای جست و جوی قبلی، از روشهای ثابت استفاده میکردند.
عامل با استفاده از فضای حالت فراسطحی میتواند یاد بگیرد که بهتر جست و جو کند
هر حالت در فضای حالت فرا سطحی، حالت(محاسباتی) داخلیِ برنامه ای را تسخیر میکند که فضای حالت سطح شیء، مثل رومانی را جست و جو میکند
الگوریتم یادگیری فراسطحی میتواند چیزهایی را از تجربیات بیاموزد تا زیردرختهای غیر قابل قبول را کاوش نکند.
هدف یادگیری، کمینه کردن کل هزینه، حل مسئله است
112
جست و جوی آگاهانه و اکتشاف
توابع اکتشافی
مثال برای معمای8
میانگِین هزینه حل تقریبا 22 مرحله و فاکتور انشعاب در حدود 3 است.
جست و جوی جامع تا عمق 22 :
با انتخاب یک تابع اکتشافی مناسب میتوان مراحل جستجو را کاهش داد
113
جست و جوی آگاهانه و اکتشاف
دو روش اکتشافی متداول برای معمای8
تعداد کاشیها در مکانهای نادرست
در حالت شروع
اکتشاف قابل قبولی است، زیرا هر کاشی که در جای نامناسبی قرار دارد، حداقل یکبار باید جابجا شود
114
جست و جوی آگاهانه و اکتشاف
دو روش اکتشافی متداول برای معمای8
مجموعه فواصل کاشیها از موقعیتهای هدف آنها
در حالت شروع
چون کاشیها نمیتوانند در امتداد قطر جا به جا شوند, فاصله ای که محاسبه میکنیم مجموع فواصل افقی و عمودی است. این فاصله را فاصله بلوک شهر یا فاصله مانهاتان مینامند.
115
جست و جوی آگاهانه و اکتشاف
دو روش اکتشافی متداول برای معمای8
مجموعه فواصل کاشیها از موقعیتهای هدف آنها
قابل قبول است، زیرا هر جابجایی که میتواند انجام گیرد، به اندازه یک مرحله به هدف نزدیک میشود.
هیچ کدام از این برآوردها، هزینه واقعی راه حل نیست
هزینه واقعی 36 است
116
جست و جوی آگاهانه و اکتشاف
اثر دقت اکتشاف بر کارایی
فاکتور انشعاب موثر b*
اگر تعداد گره هایی که برای یک مسئله خاص توسط A* تولید میشود برابر با N و عمق راه حل برابر با d باشد، آن گاه b* فاکتور انشعابی است که درخت یکنواختی به عمق d باید داشته باشد تا حاوی N+1 گره باشد
فاکتور انشعاب موثر معمولاً برای مسئله های سخت ثابت است
اندازه گیریهای تجربی b* بر روی مجموعه کوچکی از مسئله ها میتواند راهنمای خوبی برای مفید بودن اکتشاف باشد
مقدار b* در اکتشافی با طراحی خوب، نزدیک 1 است
117
جست و جوی آگاهانه و اکتشاف
اثر دقت اکتشاف بر کارایی
هزینه جست و جو
فاکتور انشعاب موثر
میانگین گره های بسط یافته در جستجویIDS و A* و فاکتور انشعاب موثر با استفاده ازh1 و h2
118
جست و جوی آگاهانه و اکتشاف
اثر دقت اکتشاف بر کارایی
اگر برای هر گره n داشته باشیم: h2(n) >= h1(n)
h2 بر h1غالب است
غالب بودن مستقیما به کارایی ترجمه میشود
تعداد گره هایی که با بکارگیری h2 بسط داده میشود، هرگز بیش از بکارگیری h1 نیست
همیشه بهتر است از تابع اکتشافی با مقادیر بزرگ استفاده کرد، به شرطی که زمان محاسبه اکتشاف، خیلی بزرگ نباشد
119
جست و جوی آگاهانه و اکتشاف
الگوریتم های جست و جوی محلی و بهینه سازی
الگوریتم های قبلی، فضای جست و جو را به طور سیستماتیک بررسی میکنند
تا رسیدن به هدف یک یا چند مسیر نگهداری میشوند
مسیر رسیدن به هدف، راه حل مسئله را تشکیل میدهد
در الگوریتم های محلی مسیر رسیدن به هدف مهم نیست
مثال: مسئله 8 وزیر
دو امتیاز عمده جست و جوهای محلی
استفاده از حافظه کمکی
ارائه راه حلهای منطقی در فضاهای بزرگ و نامتناهی
این الگوریتمها برای حل مسائل بهینه سازی نیز مفیدند
یافتن بهترین حالت بر اساس تابع هدف
120
جست و جوی آگاهانه و اکتشاف
الگوریتم های جست و جوی محلی و بهینه سازی
121
جست و جوی تپه نوردی
جست و جوی آگاهانه و اکتشاف
حلقه ای که در جهت افزایش مقدار حرکت میکند(بطرف بالای تپه)
رسیدن به بلندترین قله در همسایگی حالت فعلی، شرط خاتمه است.
ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه میدارد
جست و جوی محلی حریصانه نیز نام دارد
بدون فکر قبلی حالت همسایه خوبی را انتخاب میکند
تپه نوردی به دلایل زیر میتواند متوقف شود:
بیشینه محلی
برآمدگی ها
فلات
122
جست و جوی آگاهانه و اکتشاف
انواع تپه نوردی:
تپه نوردی غیرقطعی، تپه نوردی اولین انتخاب، تپه نوردی شروع مجدد تصادفی
مثال: مسئله 8 وزیر
مسئله 8 وزیر با استفاده از فرمولبندی حالت کامل
در هر حالت 8 وزیر در صفحه قرار دارند
تابع جانشین: انتقال یک وزیر به مربع دیگر در همان ستون
تابع اکتشاف: جفت وزیرهایی که نسبت به هم گارد دارند
مستقیم یا غیر مستقیم
جست و جوی تپه نوردی
123
جست و جوی آگاهانه و اکتشاف
مثال جست و جوی تپه نوردی
الف- حالت با هزینه h=17 که مقدار h را برای هر جانشین نشان میدهد
ب- کمینه محلی در فضای حالت 8 وزیر؛ h=1
الف
ب
124
جست و جوی آگاهانه و اکتشاف
جست و جوی شبیه سازی حرارت
تپه نوردی مرکب با حرکت تصادفی
شبیه سازی حرارت: حرارت با درجه بالا و به تدریج سرد کردن
مقایسه با حرکت توپ
توپ در فرود از تپه به عمیق ترین شکاف میرود
با تکان دادن سطح توپ از بیشینه محلی خارج میشود
با تکان شدید شروع(دمای زیاد)
بتدریج تکان کاهش(به دمای پایین تر)
با کاهش زمانبندی دما به تدریج، الگوریتم یک بهینه عمومی را می یابد
125
جست و جوی آگاهانه و اکتشاف
جست و جوی پرتو محلی
به جای یک حالت، k حالت را نگهداری میکند
حالت اولیه: k حالت تصادفی
گام بعد: جانشین همه k حالت تولید میشود
اگر یکی از جانشین ها هدف بود، تمام میشود
وگر نه بهترین جانشین را انتخاب کرده، تکرار میکند
تفاوت عمده با جستجوی شروع مجدد تصادفی
در جست و جوی شروع مجدد تصادفی، هر فرایند مستقل از بقیه اجرا میشود
در جست و جوی پرتو محلی، اطلاعات مفیدی بین k فرایند موازی مبادله میشود
جست و جوی پرتو غیرقطعی
به جای انتخاب بهترین k از جانشینها، k جانشین تصادفی را بطوریکه احتمال انتخاب یکی تابعی صعودی از مقدارش باشد، انتخاب میکند
126
جست و جوی آگاهانه و اکتشاف
الگوریتم های ژنتیک
شکلی از جست و جوی پرتو غیر قطعی که حالتهای جانشین از طریق ترکیب دو حالت والد تولید میشود
127
الگوریتم های ژنتیک
جست و جوی آگاهانه و اکتشاف
جهت اولیه
تابع برازش
انتخاب
تقاطع
جهش
128
جست و جوی آگاهانه و اکتشاف
جست و جوی محلی در فضاهای پیوسته
گسسته در مقابل محیط های پیوسته
در فضاهای پیوسته، تابع جانشین در اغلب موارد، حالتهای نامتناهی را بر میگرداند
حل مسئله:
گسسته کردن همسایه هر حالت
استفاده از شیب منظره
روش نیوتن رافسون
129
جست و جوی آگاهانه و اکتشاف
عاملهای جست و جوی Online و محیطهای ناشناخته
تا به حال همه الگوریتمها برون خطی بودند
برون خطی(Offline):راه حل قبل از اجرا مشخص است
درون خطی(Online):با یک در میان کردن محاسبات و فعالیت عمل میکند
جستجوی درون خطی در محیطهای پویا و نیمه پویا مفید است
آنچه را که باید واقعا اتفاق بیفتد، در نظر گرفته نمیشود
جست و جوی درون خطی ایده ضروری برای مسئله اکتشاف است
فعالیتها و حالتها برای عامل مشخص نیستند
مثال:قرار گرفتن روبات در محیطی جدید, نوزاد تازه بدنیا آمده
130
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
اطلاعات عامل
Actions(s): لیستی از فعالیتهای مجاز در حالت s
تابع هزینه مرحله ای c(s,a,s’): استفاده وقتی که بداند s’ نتیجه است
Goal-Test(s): آزمون هدف
عامل حالت ملاقات شده قبلی را تشخیص میدهد
فعالیتها قطعی اند
دسترسی به تابع اکتشافی قابل قبول h(s)
131
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
هدف: رسیدن به G با کمترین هزینه
هزینه: مجموع هزینه های مراحل مسیری است که عامل طی میکند
نسبت رقابتی: مقایسه هزینه با هزینه مسیری که اگر عامل فضای حالت را از قبل میشناخت، طی میکرد
در بعض موارد، بهترین نسبت رقابتی
نامتناهی است
ممکن است جستجو به یک حالت
بن بست برسد که نتوان از طریق آن به هدف رسید
132
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
دو فضای حالت که عامل جست و جوی Online را به بن بست میرسانند. هر عاملی حداقل در یکی از این دو فضا شکست می خورد
133
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
یک محیط دو بعدی که موجب میشود عامل جست و جویOnline مسیر دلخواه ناکارآمدی را برای رسیدن به هدف حل کند
134
هوش مصنوعی
فصل پنجم
مسائل ارضای محدودیت
135
هوش مصنوعی Artificial Intelligence
فهرست
ارضای محدودیت چیست؟
جست و جوی عقبگرد برای CSP
بررسی پیشرو
پخش محدودیت
136
مسائل ارضای محدودیت
ارضای محدودیت (CSP) چیست؟
مجموعه متناهی از متغیرها؛ X1, X2, …, Xn
مجموعه متناهی از محدودیتها؛ C1, C2, …, Cm
دامنه های ناتهی برای هر یک از متغیرها؛DX1,DX2,…,DXn
هر محدودیت Ci زیرمجموعه ای از متغیرها و ترکیبهای ممکنی از مقادیر برای آن زیرمجموعه ها
هر حالت با انتساب مقادیری به چند یا تمام متغیرها تعریف میشود
انتسابی که هیچ محدودیتی را نقض نکند، انتساب سازگار نام دارد
انتساب کامل آن است که هر متغیری در آن باشد
راه حل CSP یک انتساب کامل است اگر تمام محدودیتها را برآورده کند
بعضی از CSPها به راه حلهایی نیاز دارند که تابع هدف را بیشینه کنند
137
مسائل ارضای محدودیت
مثال CSP: رنگ آمیزی نقشه
متغیرها: WA, NT, Q, NSW, V, SA, T
دامنه: {آبی، سبز، قرمز} = Di
محدودیتها: دو منطقه مجاور، همرنگ نیستند
مثال: WA ≠ NT یعنی (WA,NT) عضو
{(قرمز,سبز),(قرمز,آبی),(سبز,قرمز)، (سبز,آبی),(آبی,قرمز),(آبی,سبز)}
138
مسائل ارضای محدودیت
راه حل انتساب مقادیری است که محدودیتها را ارضا کند
139
مسائل ارضای محدودیت
گراف محدودیت
در گراف محدودیت:
گره ها: متغیرها
یالها: محدودیتها
گراف برای ساده تر کردن جست و جو بکار میرود
140
مسائل ارضای محدودیت
مثال 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 – …
141
مسائل ارضای محدودیت
نمایش حالتها در CSP از الگوی استانداردی پیروی میکند
برای CSP میتوان فرمول بندی افزایشی ارائه کرد:
حالت اولیه: انتساب خالی{} که در آن، هیچ متغیری مقدار ندارد
تابع جانشین: انتساب یک مقدار به هر متغیر فاقد مقدار، به شرطی که با متغیرهایی که قبلا مقدار گرفتند، متضاد نباشند
آزمون هدف: انتساب فعلی کامل است
هزینه مسیر: هزینه ثابت برای هر مرحله
142
مسائل ارضای محدودیت
جست و جوی عقبگرد برای CSP
جست و جوی عمقی
انتخاب مقادیر یک متغیر در هر زمان و عقبگرد در صورت عدم وجود مقداری معتبر برای انتساب به متغیر
یک الگوریتم ناآگاهانه است
برای مسئله های بزرگ کارآمد نیست
143
مسائل ارضای محدودیت
مثال جست و جوی عقبگرد برای CSP
144
مسائل ارضای محدودیت
مثال جست و جوی عقبگرد برای CSP
145
مسائل ارضای محدودیت
مثال جست و جوی عقبگرد برای CSP
146
مسائل ارضای محدودیت
مثال جست و جوی عقبگرد برای CSP
147
مسائل ارضای محدودیت
مقادیر باقیمانده کمینه(MRV)
انتخاب متغیری با کمترین مقادیر معتبر
متغیری انتخاب میشود که به احتمال زیاد، بزودی با شکست مواجه شده و درخت جست و جو را هرس میکند
148
اکتشاف درجه ای
مسائل ارضای محدودیت
سعی میکند فاکتور انشعاب را در انتخاب آینده کم کند
متغیری انتخاب میکند که در بزرگترین محدودیتهای مربوط به متغیرهای بدون انتساب قرار دارد
149
اکتشاف مقداری باکمترین محدودیت
مسائل ارضای محدودیت
این روش مقداری را ترجیح میدهد که در گراف محدودیت، متغیرهای همسایه به ندرت آن را انتخاب میکنند
سعی بر ایجاد بیشترین قابلیت انعطاف برای انتساب بعدی متغیرها
150
مسائل ارضای محدودیت
بررسی پیشرو
وقتی انتساب به X صورت میگیرد، فرایند بررسی پیشرو، متغیرهای بدون انتساب مثل Y را در نظر میگیرد که از طریق یک محدودیت به X متصل است و هر مقداری را که با مقدار انتخاب شده برای X برابر است، از دامنه Y حذف میکند
151
مسائل ارضای محدودیت
بررسی پیشرو
152
مسائل ارضای محدودیت
بررسی پیشرو
153
مسائل ارضای محدودیت
بررسی پیشرو
154
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
155
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
156
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
157
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
158
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
159
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
160
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
161
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
162
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
163
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
164
مسائل ارضای محدودیت
مثال: مسئله 4-وزیر
165
مثال: مسئله 4-وزیر
مسائل ارضای محدودیت
166
مسائل ارضای محدودیت
پخش محدودیت
پخش الزام محدودیتهای یک متغیر به متغیرهای دیگر
مثال: پخش محدودیتهای WA و Q به NT و SA
167
مسائل ارضای محدودیت
سازگاری یال
روش سریعی برای پخش محدود و قویتر از بررسی پیشرو
یال؛ یال جهت دار در گراف محدودیت
بررسی سازگاری یال
یک مرحله پیش پردازش، قبل از شروع جستجو
یک مرحله پخشی پس از هر انتساب در حین جستجو
168
مسائل ارضای محدودیت
مثال: سازگاری یال
SA NSW سازگار است اگر
SA=blue and NSW=red
169
مسائل ارضای محدودیت
مثال: سازگاری یال
NSW SA سازگار است اگر
SA=blue and NSW=red
NSW=blue and SA=???
یال میتواند سازگار شود با حذف blue از NSW
170
مسائل ارضای محدودیت
مثال: سازگاری یال
یال میتواند سازگار شود با حذف blue از NSW
حذف red از V
171
مسائل ارضای محدودیت
مثال: سازگاری یال
یال میتواند سازگار شود با حذف blue از NSW
حذف red از V
تکرار تا هیچ ناسازگاری باقی نماند
172
مسائل ارضای محدودیت
سازگاری K
سازگاری یال تمام ناسازگاریهای ممکن را مشخص نمیکند
با روش سازگاریK، شکلهای قویتری از پخش را میتوان تعریف کرد
در صورتی CSP سازگاریK است، که برای هر k-1 متغیر و برای هر انتساب سازگار با آن متغیرها، یک مقدار سازگار، همیشه بتواند به متغیر kام نسبت داده شود
173
مسائل ارضای محدودیت
سازگاری K
بطور مثال:
سازگاری1: هر متغیر با خودش سازگار است(سازگاری گره)
سازگاری2: مشابه سازگاری یال
سازگاریk: بسط هر جفت از متغیرهای همجوار به سومین متغیر همسایه(سازگاری مسیر)
گراف در صورتی قویا سازگارK است که:
سازگارk باشد
همچنین سازگارk-1 و سازگارk-2 و… سازگار 1 باشد
در این صورت، مسئله را بدون عقبگرد میتوان حل کرد
پیچیدگی زمانی آن O(nd) است
174
مسائل ارضای محدودیت
جست و جوی محلی در مسائل ارضای محدودیت
بسیاری از CSPها را بطور کارآمد حل میکنند
حالت اولیه، مقداری را به هر متغیر نسبت میدهد
تابع جانشین، تغییر مقدار یک متغیر در هر زمان
انتخاب مقدار جدید برای یک متغیر
انتخاب مقداری که کمترین برخورد را با متغیرهای دیگر ایجاد کند(اکتشاف برخورد کم)
زمان اجرای برخورد کم مستقل از اندازه مسئله است
برخورد کم، برای مسئله های سخت نیز کار میکند
جست و جوی محلی میتواند در صورت تغییر مسئله، تنظیمات Online را انجام دهد
175
مسائل ارضای محدودیت
مثال
راه حل دو مرحله ای برای مسئله 8وزیر با استفاده از کمترین برخورد
در هر مرحله، یک وزیر برای انتساب مجدد در ستون خودش انتخاب میگردد
تعداد برخوردها در هر مربع نشان داده شده است
الگوریتم وزیر را به مربعی با کمترین برخورد انتقال میدهد، بطوریکه گره ها را بطور تصادفی میشکند
176
هوش مصنوعی
فصل ششم
جستجوی خصمانه
177
هوش مصنوعی Artificial Intelligence
فهرست
بازیها چیستند و چرا مطالعه میشوند؟
انواع بازیها
الگوریتم minimax
بازیهای چند نفره
هرس آلفا-بتا
بازیهای قطعی با اطلاعات ناقص
بازیهایی که حاوی عنصر شانس هستند
178
جستجوی خصمانه
بازی ها چیستند و چرا مطالعه میشوند؟
بازیها حالتی از محیطهای چند عاملی هستند
هر عامل نیاز به در نظر گرفتن سایر عاملها و چگونگی تاثیر آنها دارد
تمایز بین محیطهای چند عامل رقابتی و همکار
محیطهای رقابتی، که در آنها اهداف عاملها با یکدیگر برخورد دارند، منجر به مسئله های خصمانه میشود که به عنوان بازی شناخته میشوند
چرا مطالعه میشوند؟
قابلیتهای هوشمندی انسانها را به کار میگیرند
ماهیت انتزاعی بازی ها
حالت بازی را به راحتی میتوان نمایش داد و عاملها معمولا به مجموعه کوچکی از فعالیتها محدود هستند که نتایج آنها با قوانین دقیقی تعریف شده اند
179
جستجوی خصمانه
انواع بازی ها
اطلاعات کامل
اطلاعات ناقص
قطعی
تصادفی
شطرنج
ریورسی
تخته نرد
پوکر
180
جستجوی خصمانه
یک نمونه بازی
بازی دو نفره: Min و Max
اول Max حرکت میکند و سپس به نوبت بازی میکنند تا بازی تمام شود
در پایان بازی، برنده جایزه و بازنده جریمه میشود
بازی به عنوان یک جستجو:
حالت اولیه: موقعیت صفحه و شناسه های قابل حرکت
تابع جانشین:لیستی از (حالت,حرکت) که معرف یک حرکت معتبر است
آزمون هدف:پایان بازی چه موقع است؟(حالتهای پایانه)
تابع سودمندی: برای هر حالت پایانه یک مقدار عددی را ارائه میکند. مثلا برنده(1+) و بازنده(1-)
حالت اولیه و حرکات معتبر برای هر بازیکن، درخت بازی را برای آن بازی ایجاد میکند
181
جستجوی خصمانه
یک نمونه بازی
الگوریتم؛
بازیکن: انتخاب بهترین حالت
حریف: انتخاب بهترین موقعیت برای خودش یا بدترین وضعیت برای بازیکن
بازیکن: ماکزیمم حالت
حریف: مینیمم حالت
182
جستجوی خصمانه
الگوریتم minimax
183
جستجوی خصمانه
یک نمونه بازی
184
جستجوی خصمانه
یک نمونه بازی
185
جستجوی خصمانه
یک نمونه بازی
186
جستجوی خصمانه
یک نمونه بازی
187
جستجوی خصمانه
یک نمونه بازی
188
جستجوی خصمانه
الگوریتم minimax
کامل بودن: بله (اگر درخت محدود باشد)
بهینگی: بله
پیچیدگی زمانی:
پیچیدگی فضا:
189
جستجوی خصمانه
بازیهای چند نفره
تخصیص یک بردار به هر گره، به جای یک مقدار
بازیهای چند نفره معولاً شامل اتحاد رسمی یا غیر رسمی بین بازیکنان است
اتحاد با پیشروی بازی ایجاد و از بین میرود
بازیکنان بطور خودکار همکاری میکنند، تا به هدف مطلوب انحصاری برسند
190
جستجوی خصمانه
هرس آلفا-بتا
در الگوریتم MaxMin:
تعداد حالتهای بازی که باید بررسی شوند، بر حسب تعداد حرکتها، توانی است
راه حل: محاسبه تصمیم الگوریتم، بدون دیدن همه گره ها امکانپذیر است
هرس آلفا-بتا:
انشعابهایی که در تصمیم نهایی تاثیر ندارند را حذف میکند
آلفا: مقدار بهترین انتخاب در هر نقطه انتخاب در مسیر Max تاکنون
بتا: مقدار بهترین انتخاب در هر نقطه انتخاب در مسیر Min تاکنون
تعداد گره هایی که باید بررسی شوند به تقلیل میابد
فاکتور انشعاب موثر به جای b برابر با جذرb خواهد بود
پیش بینی آن نسبت به minimax دو برابر است
191
جستجوی خصمانه
هرس آلفا-بتا
گره n که هر جای درخت میتواند باشد، بررسی میشود
اگر بازیکن انتخاب بهتری داشته باشد
در گره والد n
یا هر انتخاب بهتری تا کنون
n هیچوقت در بازی واقعی قابل دسترس نخواهد بود
در نتیجه n هرس میشود
192
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞, +∞]
[-∞,+∞]
محدوده مقادیر ممکن
193
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,3]
[-∞,+∞]
194
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,3]
[-∞,+∞]
195
جستجوی خصمانه
[3,+∞]
[3,3]
196
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,2]
[3,+∞]
[3,3]
این گره برایMax مناسب نیست
197
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,2]
[3,14]
[3,3]
[-∞,14]
,
198
جستجوی خصمانه
مثال: هرس آلفا-بتا
[−∞,2]
[3,5]
[3,3]
[-∞,5]
,
199
جستجوی خصمانه
مثال: هرس آلفا-بتا
[2,2]
[−∞,2]
[3,3]
[3,3]
200
جستجوی خصمانه
مثال: هرس آلفا-بتا
[2,2]
[-∞,2]
[3,3]
[3,3]
201
جستجوی خصمانه
بازیهای قطعی با اطلاعات ناقص
معایب الگوریتم های پیشین
الگوریتم minimax کل فضای جست و جوی بازی را تولید میکند
الگوریتم آلفا-بتا با وجود هرس درخت، اما کل مسیر حالتهای پایانه، حداقل برای بخشی از فضای حالت، باید جست و جو شود
این عمق عملی نیست، زیرا حرکات باید در زمانی معقول انجام شود
شانون(1950)
برای کمتر شدن زمان جست و جو و اعمال تابع ارزیابی اکتشافی به حالتهای جستجو، بهتر است از گره های غیر پایانه به گره های پایانه پرداخته شود
202
جستجوی خصمانه
بازیهای قطعی با اطلاعات ناقص
در شانون, minimax و آلفا-بتا به دو روش بطور متناوب عمل میکنند
جایگزینی تابع سودمندی با تابع ارزیابی اکتشافی بنام EVAL
تخمینی از سودمندی موقعیت ارائه میکند
جایگزین تست پایانه با تست توقف
تصمیم میگیرد EVAL چه موقع اعمال شود
203
جستجوی خصمانه
تابع ارزیابی اکتشافی EVAL
تابع ارزیابی، ارائه تخمینی از سودمندی مورد انتظار بازی از یک موقعیت خاص
توابع اکتشافی، تخمینی از فاصله تا هدف را بر میگرداندند
اغلب توابع ارزیابی، خواص گوناگونی از حالتها را محاسبه میکنند
خواص روی هم رفته، کلاسهای هم ارزی یا دسته های مختلفی از حالتها را تعریف میکنند
حالتهای هر دسته، برای تمام خواص مقدار یکسانی دارند
هر دسته حاوی چند حالت است که
موجب برنده شدن
موجب رسم شدن
منجر به باختن
تابع ارزیابی نمیداند کدام حالت منجر به چه چیزی میشود، اما میتواند مقداری برگرداند که تناسب حالتها را با هر نتیجه نشان دهد
204
جستجوی خصمانه
Eval(s) = w1 f1(s) + w2 f2(s) + … + wnfn(s)
مثال: تابع EVAL
اغلب توابع ارزیابی, مقدار عددی جداگانه ای برای هر خاصیت محاسبه، سپس آنها را ترکیب میکنند تا مقدار کل بدست آید
مثال در تابع بازی شطرنج:
تعداد هر نوع قطعه در صفحه
مقادیر آن قطعات(1 برای پیاده، 3 برای اسب یا فیل،5 برای رخ و …)
205
جستجوی خصمانه
مثال: تابع EVAL
الف) سیاه، مزیت اسب و دو پیاده دارد و بازی را میبرد
ب) پس از اینکه سفید، وزیر را در اختیار میگیرد، سیاه میبازد
ارزیابی تابع EVAL از مقدار پیروزی در دو موقعیت کاملا متفاوت
206
جستجوی خصمانه
اثر افق
وقتی بوجود می آید که برنامه با اثری از رقیب مواجه شود که منجر به خرابی جدی گشته و اجتناب پذیر است
مثال: شکل مقابل؛
سیاه در اصل جلوست، اما اگر سفید پیاده اش را از سطر هفتم به هشتم ببرد، پیاده به وزیر تبدیل میشود و موقعیت برد برای سفید بوجود می آید
207
جستجوی خصمانه
بازیهایی که حاوی عنصر شانس هستند
شانس
شانس
پایانه
208
هوش مصنوعی
فصل هفتم
عامل های منطقی
209
هوش مصنوعی Artificial Intelligence
فهرست
عاملهای مبتنی بر دانش
منطق
منطق گزاره ای
الگوهای استدلال در منطق گزاره ای
الگوریتم resolution
زنجیر پیشرو و عقبگرد
210
عاملهای منطقی
عاملهای مبتنی بر دانش
مولفه اصلی عامل مبتنی بر دانش، پایگاه دانش آن است
پایگاه دانش: مجموعه ای از جملات
جمله: زبان نمایش دانش و بیان ادعاهایی در مورد جهان
برای اضافه کردن جملات به پایگاه دانش و درخواست دانسته ها
TELL و ASK
هر دو ممکن است شامل استنتاج باشند
پیروی:انجام فرایند استنتاج تحت مقررات خاص
بخش استنتاج
پایگاه دانش
محدوده اطلاعات خاص
محدوده اطلاعات خاص
محدوده الگورِیتمهای مستقل
tell
ask
211
عاملهای منطقی
عاملهای مبتنی بر دانش
عامل مبتنی بر دانش باید بتواند:
نمایش حالات و فعالیتها
ترکیب ادراکات جدید
بروز کردن تصور داخلی خود از جهان
استنباط خصوصیات مخفی جهان
استنتاج فعالیتهای مناسب
عامل پایگاه دانش خیلی شبیه به عاملهایی با حالت درونی است
عاملها در دو سطح متفاوت تعریف میشوند:
سطح دانش: عامل چه چیزی میداند و اهداف آن کدامند؟
سطح پیاده سازی: ساختمان داده اطلاعات پایگاه دانش و چگونگی دستکاری آنها
212
عاملهای منطقی
جهان WUMPUS
معیار کارایی:
1000+ انتخاب طلا، 1000- افتادن در گودال یا خورده شدن، 1- هر مرحله، 10- برای استفاده از تیر
محیط:
بوی تعفن در مربعهای همجوار WUMPUS
نسیم در مربعهای همجوار گودال
درخشش در مربع حاوی طلا
کشته شدن WUMPUS با شلیک در صورت مقابله
تیر فقط مستقیم عمل میکند
برداشتن و انداختن طلا
حسگرها:
بو تعفن، نسیم، تابش، ضربه، جیغ زدن
محرکها:
گردش به چپ، گردش به راست، جلو رفتن، برداشتن، انداختن، شلیک کردن
213
عاملهای منطقی
توصیف جهان WUMPUS
قابل مشاهده کامل: خیر, فقط ادراک محلی
قطعی: بله، نتیجه دقیقا مشخص است
رویدادی: خیر، ترتیبی از فعالیتهاست
ایستا: بله, WUMPUS و گودالها حرکت ندارند
گسسته: بله
تک عامله: بله، WUMPUS در اصل یک خصوصیت طبیعی است
214
عاملهای منطقی
کاوش در جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
215
عاملهای منطقی
توصیف جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
216
عاملهای منطقی
توصیف جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
217
عاملهای منطقی
توصیف جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
218
عاملهای منطقی
توصیف جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
219
عاملهای منطقی
توصیف جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
220
عاملهای منطقی
توصیف جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
221
عاملهای منطقی
توصیف جهان WUMPUS
عامل = A
نسیم = B
درخشش،طلا = G
مربع امن = OK
گودال = P
تعفن = S
ملاقات شده = V
Wumpus = W
222
عاملهای منطقی
منطق
یک زبان رسمی:
ترکیب(نحو): چه کلمه بندی صحیح است.(خوش فرم)
معناشناسی: یک کلمه بندی صحیح چه معنایی دارد
در منطق، معنای زبان، درستی هر جمله را در برابر هر جهان ممکن تعریف میکند
مثال، در زبان ریاضیات
X+2 >= y یک جمله اما x2+y جمله نیست
X+2 >= y در جهان درست است اگر x=7 و y =1
X+2 >= y در جهان غلط است اگر x=0 و y =6
223
عاملهای منطقی
استلزام
استلزام منطقی بین جملات این است که جمله ای بطور منطقی از جمله دیگر پیروی میکند
a ╞ b
جمله a استلزام جمله b است
جمله a جمله b را ایجاد میکند
اگر و فقط اگر، در هر مدلی که a درست است، b نیز درست است
اگر a درست باشد، b نیز درست است
درستی b در درستی a نهفته است
مثال: جمله x+y=4 مستلزم جمله 4=x+y است
224
عاملهای منطقی
مدلهای Wumpus
225
عاملهای منطقی
مدلهای Wumpus
KB
=
قوانین دنیای Wumpus
+
مشاهدات
226
عاملهای منطقی
مدلهای Wumpus
KB = wumpusدنیای + مشاهدات
α1 = "[1,2] امن است", KB ╞ α1
227
عاملهای منطقی
مدلهای Wumpus
KB = wumpusدنیای + مشاهدات
228
عاملهای منطقی
مدلهای Wumpus
KB = wumpusدنیای + مشاهدات
α2 = "[2,2] امن است", KB ╞ α2
229
عاملهای منطقی
منطق گزاره ای
نحو منطق گزاره ای، جملات مجاز را تعریف میکند
جملات اتمیک(عناصر غیر قابل تعمیم) تشکیل شده از یک نماد گزاره
هر یک از این نمادها به گزاره ای درست یا نادرست اختصاص دارد
نمادها از حروف بزرگ مثل 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 دو شرطی نام دارد
230
عاملهای منطقی
منطق گزاره ای
231
جدول درستی پنج رابطه منطقی
عاملهای منطقی
232
منطق گزاره ای در دنیای Wumpus
عاملهای منطقی
در B1,1 نسیمی وجود دارد B1,1 (P1,2 ν P2,1)
در [1,1] گودالی وجود ندارد R1: ┐P1,1
233
عاملهای منطقی
الگوهای استدلال در منطق گزاره ای
قوانین استنتاج: الگوهایی استاندارد که زنجیره ای از نتایج را برای رسیدن به هدف ایجاد میکند
قیاس استثنایی: با استفاده از ترکیب عطفی، میتوان هر عطف را استنتاج کرد(یعنی هر وقت جمله ای به شکل a=>b داده شود، جمله b را میتوان استنتاج کرد.)
میتوان از
(WumpusAhead ^ WumpusAlive)
و
(WumpusAhead ^ WumpusAlive) => Shoot
Shoot را استنتاج کرد
234
عاملهای منطقی
حذف and: هر عطف را میتوان از ترکیب عطفی استنتاج کرد
مثال: WumpusAlive را میتوان از جمله زیر استناج کرد
(WumpusAhead ^ WumpusAlive)
خاصیت یکنواختی
مجموعه ای از جملات استلزامی که فقط میتواند در صورت اضافه شدن اطلاعات به پایگاه دانش رشد کند.
برای جملات a و b داریم:
235
عاملهای منطقی
قانون resolution
قانون resolution واحد، یک عبارت و یک لیترال را گرفته، عبارت دیگری تولید میکند
قانون resulotion واحد میتواند به قانون resulotion کامل تعمیم داد:
236
عاملهای منطقی
الگوریتم resolution
شکل نرمال عطفی(CNF): جمله ای که بصورت ترکیب عطفی از ترکیبات فصلی لیترالها بیان میشود.در هر عبارت موجود در جمله k-CNF دقیقا k لیترال وجود دارد
الگوریتم resolution:
برای اینکه نشان دهیمKB|=a , مشخص میکنیم (KB ^ ┐a) ارضا کننده نیست
ابتدا (KB ^ ┐a) را به CNF تبدیل میکنیم
سپس قانون resulotion به عبارات کوچک حاصل اعمال میشود
هر جفتی که شامل لیترالهای مکمل باشد، resulotion میشود تا عبارت جدیدی ایجاد گردد
اگر این عبارت قبلا در مجموعه نباشد، به آن اضافه میشود
فرایند تا محقق شدن یکی از شروط زیر ادامه می یابد:
هیچ عبارت دیگری وجود نداشته باشد که بتواند اضافه شود. در این مورد، b استلزام a نیست
کاربرد قانون resolution، عبارت تهی را بدست میدهد که در این مورد، b استلزام a است
237
عاملهای منطقی
مثال:الگوریتم resolution
KB = (B1,1 (P1,2 P2,1)) B1,1 α = P1,2
238
عاملهای منطقی
زنجیر پیشرو و عقبگرد
عبارات هورن: ترکیب فصلی لیترالهایی است که فقط یکی از آنها مثبت است
هر عبارت هورن را میتوان به صورت یک استلزام نوشت که مقدمه آن ترکیب عطفی لیترالهای مثبت و تالی آن یک لیترال مثبت است
این نوع عبارات هورن که فقط یک لیترال مثبت دارند، عبارات معین نامیده میشوند
لیترال مثبت را راس و لیترالهای منفی را بدنه عبارت گویند
عبارت معینی که فاقد لیترالهای منفی باشد، گزاره ای بنام حقیقت نام دارد
عبارات معین اساس برنامه نویسی منطقی را میسازد
استنتاج با عبارات هورن، از طریق الگوریتم های زنجیر پیشرو و زنجیر عقبگرد انجام میگیرد
239
عاملهای منطقی
زنجیر پیشرو
الگوریتم زنجیر پیشرو تعیین میکند آیا نماد گزاره ای q(تقاضا)، توسط پایگاه دانش عبارات هورن ایجاب میشود یا خیر
240
عاملهای منطقی
زنجیر پیشرو
241
عاملهای منطقی
زنجیر پیشرو
242
عاملهای منطقی
زنجیر پیشرو
243
عاملهای منطقی
زنجیر پیشرو
244
عاملهای منطقی
زنجیر پیشرو
245
عاملهای منطقی
زنجیر پیشرو
246
عاملهای منطقی
زنجیر پیشرو
247
عاملهای منطقی
زنجیر پیشرو
248
عاملهای منطقی
الگوریتم عقبگرد کامل
249
عاملهای منطقی
الگوریتم عقبگرد کامل
تغییرات عمده: خاتمه زودرس، اکتشاف نماد محض، اکتشاف عبارت واحد
250
عاملهای منطقی
الگوریتم عقبگرد کامل
251
عاملهای منطقی
الگوریتم عقبگرد کامل
252
عاملهای منطقی
الگوریتم عقبگرد کامل
253
عاملهای منطقی
الگوریتم عقبگرد کامل
254
عاملهای منطقی
الگوریتم عقبگرد کامل
255
عاملهای منطقی
الگوریتم عقبگرد کامل
256
عاملهای منطقی
الگوریتم عقبگرد کامل
257
عاملهای منطقی
الگوریتم عقبگرد کامل
258
عاملهای منطقی
الگوریتم عقبگرد کامل
259
هوش مصنوعی
فصل هشتم
منطق رتبه اول
260
هوش مصنوعی Artificial Intelligence
فهرست
مروری بر منطق گزاره ای
منطق رتبه اول
انواع منطق
نحو و معنای منطق رتبه اول
مهندسی دانش
261
منطق رتبه اول
مروری بر منطق گزاره ای
ویژگیها
ماهیت اعلانی
دانش و استنتاج متمایزند و استنتاج کاملاً مستقل از دامنه است
قدرت بیان کافی برای اداره کردن اطلاعات جزئی
با استفاده از ترکیب فصلی و نقیض
قابلیت ترکیب
معنای جمله، تابعی از معنای بخشهای آن
معنا، مستقل از متن است
بر خلاف زبانهای طبیعی که، معنای جملات وابسته به متن است
معایب
فاقد قدرت بیانی برای تشریح دقیق محیطی با اشیای مختلف
بر خلاف زبانهای طبیعی
262
منطق رتبه اول
منطق رتبه اول
اساس منطق گزاره ای را پذیرفته و بر اساس آن یک منطق بیانی میسازیم
از ایده های نمایشی زبان طبیعی استفاده کرده، از عیوب آن اجتناب میکنیم
زبانهای طبیعی از جهان طبقه بندی زیر را دارند
اشیاء: افراد، خانه، اعداد، رنگها، بازیهای فوتبال، آتش و …
رابطه ها:
رابطه های یکانی یا خواص مثل قرمز، گرد، اول و …
رابطه های چندتایی مثل برادر بودن، بزرگتر بودن، بخشی از، مالکیت و …
توابع: پدر بودن، بهترین دوست، یکی بیشتر از و …
منطق رتبه اول توسط اشیا و رابطه ها ساخته میشود
اشیاء: افراد، خانه، اعداد، رنگها، بازیهای فوتبال، آتش و …
رابطه ها:
رابطه های یکانی یا خواص مثل قرمز، گرد، اول و …
رابطه های چندتایی مثل برادر بودن، بزرگتر بودن، بخشی از، مالکیت و …
توابع: پدر بودن، بهترین دوست، یکی بیشتر از و …
263
منطق رتبه اول
انواع منطق
264
منطق رتبه اول
نحو و معنای منطق رتبه اول
نمادهای ثابت؛ اشیا را نشان میدهد. مثال: علی، 2، رضا، …
نمادهای محمول؛ رابطه ها را نشان میدهد. مثال:برادر بودن، بزرگتر بودن از
نمادهای تابع؛ توابع را نشان میدهند. مثال: تابع پای چپ(LeftLeg)
متغیرها: x , y , a ,b
روابط منطقی: , , , ,
تساوی: =
سورها: ,
265
منطق رتبه اول
جملات اتمیک
هر ترم یک عبارت منطقی است که به شیئ اشاره میکند
نمادهای ثابت ترم هستند
همیشه استفاده از نماد متمایز برای نامگذاری شیء آسان نیست
پای چپ پای پادشاه John LeftLeg(John)
جملات اتمیک: ترکیب ترمهای اشیاء و محولهای روابط
مثال: Married(Father(Richard),Mother(John))
پدر ریچارد با مادر جان ازدواج کرده است
جملات اتمیک= محمول(nترم1، ترم2، … ، ترم) یا ترم1=ترم2 .
ترم= تابع(nترم1، ترم2، … ، ترم) یا ثابت یا متغیر .
266
منطق رتبه اول
جملات پیچیده
با ترکیب جملات اتمیک و روابط منطقی میتوان جملات پیچیده تری ساخت
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)
267
منطق رتبه اول
مثال
مدلی با پنج شیء، دو رابطه دودویی، سه رابطه یکانی و یک تا یکانی به نام پای چپ
268
منطق رتبه اول
سورها
کمک میکنند تا به جای شمارش اشیا از طریق نام آنها، خواص کلکسیون اشیا را بیان کرد
سور عمومی؛ “برای همه”
سور وجودی؛ “ وجود دارد حداقل…”
269
منطق رتبه اول
سور عمومی
<متغیرها> <جمله>
x P که در آن P یک عبارت منطقی است، بیان میکند که P برای هر شیء x درست است
مثال: x King(x) Person(x)
270
منطق رتبه اول
سور وجودی
<متغیرها> <جمله>
x P که در آن P یک عبارت منطقی است، بیان میکند که P حداقل برای یک شیء x درست است
مثال: x Crown(x) OnHead(x , John)
271
منطق رتبه اول
خصوصیات سورها
رابط طبیعی برای کار با و رابط طبیعی برای کار با میباشد
استفاده از بعنوان رابط اصلی با منجر به حکم قوی میشود
استفاده از با منجر به حکم ضعیفی میشود
x y برابر است با y x و x y برابر است با y x
x y برابر نیست با y x
x y Loves(x,y)
حداقل یک نفر وجود دارد که همه چیز در جهان را دوست دارد
y x Loves(x,y)
همه در دنیا حداقل یک نفر را دوست دارند
272
منطق رتبه اول
خصوصیات سورها
“هر کسی بستنی را دوست دارد” به معنای این است که “هیچ کس وجود ندارد که بستنی را دوست نداشته باشد”
x Likes(x , IceCream) هم ارز x Likes(x , IceCream)
x P هم ارز x P
x P هم ارز x P
x P هم ارز x P
x P هم ارز x P
273
منطق رتبه اول
تساوی
با استفاده از = دو ترم به یک شیء اشاره میکنند
برای تعیین درستی جمله تساوی باید دید که آیا ارجاع ها به دو ترم، اشیای یکسانی اند یا خیر
مثال: ریچارد حداقل دو برادر دارد
x,y Brother(x,Richard) ^ Brother(y,Richard) ^ (x=y)
274
منطق رتبه اول
ادعاها و تقاضاها
جملات از طریق TELL به پایگاه دانش اضافه میشوند
این جملات را ادعا گویند
TELL (KB , King(John))
TELL (KB , x King(x) => Person(x))
با استفاده از ASK تقاضاهایی را از پلیگاه دانش انجام میدهیم
این پرسشها، تقاضا یا هدف نام دارد
ASK (KB , Person(John))
ASK(KB , x Person(x))
لیست جانشینی یا انقیاد
لیستی از جانشینیها در صورت وجود بیش از یک پاسخ
275
منطق رتبه اول
دامنه خویشاوندی
مادر هر فرد والد مونث آن فرد است
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)
276
منطق رتبه اول
اعداد و مجموعه ها
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)
277
منطق رتبه اول
مهندسی دانش
فرایند کلی ساخت پایگاه دانش که شامل مراحل ذیل میباشد:
مشخص کردن کار
مونتاژ دانش مربوطه
تصمیم گیری در مورد واژه نامه محمولها، توابع و وراثت
کدگزاری دانش کلی در مورد دامنه
کد گزاری توصیف نمونه مسئله خاص
اِعمال تقاضاها به رویه استنتاج و دریافت پاسخ
اشکال زدایی پایگاه دانش