پاورپوینت حل مسئله با جستجو در هوش مصنوعی

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

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

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

4
حل مسئله با جستجو
مثال: نقشه رومانی

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

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

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

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

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

10
حل مسئله با جستجو
مثال: معمای8
حالتها: مکان هر هشت خانه شماره دار و خانه خالی در یکی از 9 خانه
حالت اولیه: هر حالتی را میتوان به عنوان حالت اولیه در نظر گرفت
تابع جانشین: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا یا پایین
آزمون هدف: بررسی میکند که حالتی که اعداد به ترتیب چیده شده اند(طبق شکل روبرو) رخ داده یا نه
هزینه مسیر: برابر با تعداد مراحل در مسیر

11
حل مسئله با جستجو
مثال: معمای8
حالتها: مکان هر هشت خانه شماره دار و خانه خالی در یکی از 9 خانه
حالت اولیه: هر حالتی را میتوان به عنوان حالت اولیه در نظر گرفت
تابع جانشین: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا یا پایین
آزمون هدف: بررسی میکند که حالتی که اعداد به ترتیب چیده شده اند(طبق شکل روبرو) رخ داده یا نه
هزینه مسیر: برابر با تعداد مراحل در مسیر

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

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

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

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

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

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

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

19
حل مسئله با جستجو
جستجوی عرضی

20

حل مسئله با جستجو
جستجوی عرضی
کامل بودن: بله
بهینگی: بله (مشروط)
در صورتی بهینه است که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد.(مثل وقتی که فعالیتها هزینه یکسانی دارند)
پیچیدگی زمانی:
پیچیدگی فضا:

کامل بودن:
بهینگی: بله (مشروط)

21
حل مسئله با جستجو
جستجوی هزینه یکنواخت
این جستجو گره n را با کمترین هزینه مسیر بسط میدهد

22
حل مسئله با جستجو
کامل بودن: بله
هزینه هر مرحله بزرگتر یا مساوی یک مقدار ثابت و مثبت ε باشد.(هزینه مسیر با حرکت در مسیر افزایش می یابد)
بهینگی: بله
هزینه هر مرحله بزرگتر یا مساوی ε باشد
پیچیدگی زمانی:
پیچیدگی فضا:

جستجوی هزینه یکنواخت
کامل بودن:
بهینگی:

23
حل مسئله با جستجو
جستجوی عمقی
2
3
4
5
6
7

24
حل مسئله با جستجو
کامل بودن: خیر
اگر زیر درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل باشد، جستجو هرگز خاتمه نمی یابد.
بهینگی: خیر
پیچیدگی زمانی:
پیچیدگی فضا:

جستجوی عمقی
کامل بودن:
بهینگی:

25
حل مسئله با جستجو
جستجوی عمقی محدود
مسئله درختهای نامحدود میتواند به وسیله جست و جوی عمقی با عمق محدود L بهبود یابد

26
حل مسئله با جستجو
جستجوی عمقی محدود
کامل بودن: خیر
اگر L<d و سطحی ترین هدف در خارج از عمق محدود قرار داشته باشد، این راهبرد کامل نخواهد بود.
بهینگی: خیر
اگر L>d انتخاب شود، این راهبرد بهینه نخواهد بود.
پیچیدگی زمانی:
پیچیدگی فضا:

کامل بودن:
بهینگی:

27
حل مسئله با جستجو
جستجوی عمیق کننده تکراری

28
حل مسئله با جستجو
جستجوی عمیق کننده تکراری

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

30
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
کامل بودن: بله
در صورتی که فاکتور انشعاب محدود باشد
بهینگی: بله
وقتی که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد
پیچیدگی زمانی:
پیچیدگی فضا:

کامل بودن:
بهینگی:

31
حل مسئله با جستجو
جستجوی دو طرفه
انجام دو جست و جوی همزمان، یکی از حالت اولیه به هدف و دیگری از هدف به حالت اولیه تا زمانی که دو جست و جو به هم برسند

32
حل مسئله با جستجو
جستجوی دو طرفه
کامل بودن: بله
اگر هر دو جستجو، عرضی باشند و هزینه تمام مراحل یکسان باشد
بهینگی: بله
اگر هر دو جستجو، عرضی باشند و هزینه تمام مراحل یکسان باشد
پیچیدگی زمانی:
پیچیدگی فضا:

کامل بودن:
بهینگی:

33
حل مسئله با جستجو
اجتناب از حالتهای تکراری
وجود حالتهای تکراری در یک مسئله قابل حل، میتواند آن را به مسئله غیر قابل حل تبدیل کند

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

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

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