بخشی از پاورپوینت

اسلاید 1 :

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

اسلاید 2 :

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

اسلاید 3 :

عاملهای حل مسئله یک نوع از عاملهای هدف گرا است.
عاملهای حل مسئله با یافتن دنباله ای از فعالیت هایی که منجر به حالتهای مطلوب می شوند تصمیم می گیرند که چه کاری باید انجام دهند.

الگوریتم های آگاهانه و ناآگاهانه
تصمیم گیری عامل در حل مسئله، مبتنی بر آگاهی و شواهد نزدیکی به جواب است یا نه

عاملهای حل مسئله

اسلاید 4 :

Problem-solving agents
فرضیات در مورد محیط: ایستا، قابل مشاهده، گسسته و قطعی
14 Jan 2004
CS 3243 - Blind Search

اسلاید 5 :

حل مسئله با جستجو(مسیریابی در نقشه رومانی)

اسلاید 6 :

فرموله سازی مسئله
حالت اولیه: بودن در آراد
حالت هدف: بودن در بخارست

حالات: شهرهای مختلف
عملیات: رفتن از شهری به شهر دیگر (مجاور)

یافتن پاسخ: دنباله ای از شهرها:
آراد > سیبیو > فاراگراس > بخارست

اسلاید 7 :

فرموله کردن مسئله

یک مسئله بوسیله 4 مورد تعریف میشود:

2- حالت اوليه: حالتی که عامل از آن شروع ميکند.
در مثال رومانی: شهر آراد in(Arad)

3- عملها یا تابع جانشين: S(x) = مجموعه ای از زوجهای عمل-حالت
در مثال رومانی:< GO(Sibiu) , in(Sibiu)>,…
با توجه به حالت اولیه و تابع جانشین ، فضای حالت مسئله را می توان تعریف کرد
فضای حالت : مجموعه ای از حالتهاست که از حالت اولیه می توان به آنها رسید

اسلاید 8 :

4-آزمون هدف: تعيين ميکند که آيا حالت خاصی، حالت هدف است يا خير
هدف صريح: در مثال رومانی، رسيدن به بخارست
هدف انتزاعی: در مثال شطرنج، رسيدن به حالت کيش و مات

5- تابع هزینه ی مسیر:
مسیر:دنباله ای از فعالیتها که دنباله ای از حالات را ایجاد میکند.
در مثال رومانی: Arad, Sibiu, Fagaras يک مسير است
هزینه گام (step cost): c(x,a,y)

هزینه مسیر: مجموع فواصل، تعداد عملهای انجام شده
راه حل مسئله مسيری از حالت اوليه به حالت هدف است
راه حل بهينه کمترين هزينه مسير را دارد
مسئله و راه حل های خوش تعریف(ادامه)

اسلاید 9 :

14 Jan 2004
CS 3243 - Blind Search
حل مسئله با جستجو(مثال جارو برقی)
states?
actions?
goal test?
path cost?

اسلاید 10 :

14 Jan 2004
CS 3243 - Blind Search
حل مسئله با جستجو(مثال جارو برقی)
states? integer dirt and robot location
actions? Left, Right, Suck
goal test? no dirt at all locations
path cost? 1 per action

اسلاید 11 :

14 Jan 2004
CS 3243 - Blind Search
حل مسئله با جستجو(مثال معمای 8)
states?
actions?
goal test?
path cost?

اسلاید 12 :

14 Jan 2004
CS 3243 - Blind Search
حل مسئله با جستجو(مثال معمای 8)
states? locations of tiles
actions? move blank left, right, up, down
goal test? = goal state (given)
path cost? 1 per move


[Note: optimal solution of n-Puzzle family is NP-hard]

اسلاید 13 :

حل مسئله با جستجو(مثال معمای 8-ادامه)
معمای 8 به خانوادهی معماهای جابجایی بلوک تعلق دارد که برای آزمون الگوریتم های جستجوی جدید در AI بکار می رود.
این رده از مسائل را NP کامل می گویند.
معمای 8 دارای 2/!9 یعنی 440/181 حالت قابل رسیدن است.
معمای 15(صفحه ی4*4) تقریبا دارای 3/1 تریلیون حالت است اما در چند میلی ثانیه حل می شوند.
معمای 24 (صفحه ی 5*5) تقریبا 25^10حالت دارد و حل نمونه های آن با بهترین الگوریتم ها و ماشین های فعلی دشوار است.

اسلاید 14 :

14 Jan 2004
CS 3243 - Blind Search
ربات اسمبل کننده
states?: real-valued coordinates of robot joint angles parts of the object to be assembled

actions?: continuous motions of robot joints

goal test?: complete assembly

path cost?: time to execute

اسلاید 15 :

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

اسلاید 16 :

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

اسلاید 17 :

مسئله
بازی X-O ؛ tic tac toe

اسلاید 18 :

14 Jan 2004
CS 3243 - Blind Search
الگوریتمهای جستجوی درختی tree search
ایده اصلی
کاوش افلاین و شبیه سازی شده فضای حالت بوسیله تولید حالات بعدی ِ حالاتی که تاکنون دیده شده اند

اسلاید 19 :

14 Jan 2004
CS 3243 - Blind Search
مثال جستجوی درختی

اسلاید 20 :

14 Jan 2004
CS 3243 - Blind Search

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید