به نام خدا
2
عامل حل مسئله با جستجو در هوش مصنوعی
مقدمه
هوش مصنوعی به هوشی که یک ماشین از خود نشان میدهد و یا به دانشی در کامپیوترکه سعی در ایجاد آن دارد گفته می شود. جان مک کارتی "پدر علم و دانش ماشینهای هوشمند" ، واژه هوش مصنوعی را در سال 1956 به کار برد . تحقیقات و جستجوهای انجام شده برای رسیدن به ساخت چنین ماشینهائی مرتبط با بسیاری از علوم دیگر مانند رایانه ، روان شناسی ، فلسفه ، عصب شناسی ، علوم ادراکی ، تئوری کنترل ، احتمالات ، بهینه سازی و منطق می باشد .
3
هنوز تعریف دقیقی برای هوش مصنوعی ارائه نشده است که مورد قبول همه ی دانشمندان صاحب نظر در این زمینه باشد و این خود به علت آن است که اساس این موضوع یعنی هوش مورد جنجال و اختلاف است و تعریف جامعی درباره آن وجود ندارد.
بطور کلی ماهیت وجودی هوش به مفهوم جمع آوری اطلاعات، استقرا و تحلیل تجربیات به منظور رسیدن به دانش و یا ارایه تصمیم می باشد. در واقع هوش به مفهوم به کارگیری تجربه به منظور حل مسائل دریافت شده تلقی می شود. هوش مصنوعی علم و مهندسی ایجاد ماشینهایی با هوش با به کارگیری از کامپیوتر و الگوگیری از درک هوش انسانی و یا حیوانی و نهایتاً دستیابی به مکانیزم هوش مصنوعی در سطح هوش انسانی می باشد.
در مقایسه هوش مصنوعی با هوش انسانی می توان گفت که انسان قادر به مشاهده و تجزیه و تحلیل مسایل در جهت قضاوت و اخذ تصمیم می باشد در حالی که هوش مصنوعی مبتنی بر قوانین و رویه هایی از قبل تعبیه شده بر روی کامپیوتر می باشد. در نتیجه علی رغم وجود کامپیوترهای بسیار کارا و قوی در عصر حاضر ما هنوز قادر به پیاده کردن هوشی نزدیک به هوش انسان در ایجاد هوشهای مصنوعی نبوده ایم.
5
تعریف
بطور کلی ماهیت وجودی هوش به مفهوم جمع آوری اطلاعات، استقرا و تحلیل تجربیات به منظور رسیدن به دانش و یا ارایه تصمیم می باشد. در واقع هوش به مفهوم به کارگیری تجربه به منظور حل مسائل دریافت شده تلقی می شود. هوش مصنوعی علم و مهندسی ایجاد ماشینهایی با هوش با به کارگیری از کامپیوتر و الگوگیری از درک هوش انسانی و یا حیوانی و نهایتاً دستیابی به مکانیزم هوش مصنوعی در سطح هوش انسانی می باشد.
در مقایسه هوش مصنوعی با هوش انسانی می توان گفت که انسان قادر به مشاهده و تجزیه و تحلیل مسایل در جهت قضاوت و اخذ تصمیم می باشد در حالی که هوش مصنوعی مبتنی بر قوانین و رویه هایی از قبل تعبیه شده بر روی کامپیوتر می باشد. در نتیجه علی رغم وجود کامپیوترهای بسیار کارا و قوی در عصر حاضر ما هنوز قادر به پیاده کردن هوشی نزدیک به هوش انسان در ایجاد هوشهای مصنوعی نبوده ایم.
بطور کلّی، هوش مصنوعی را می توان از زوایای متفاوتی مورد بررسی و مطالعه قرار داد. مابین هوش مصنوعی به عنوان یک هدف، هوش مصنوعی به عنوان یک رشته تحصیلی دانشگاهی، و یا هوش مصنوعی به عنوان مجموعهٔ فنون و راه کارهایی که توسط مراکز علمی مختلف و صنایع گوناگون تنظیم و توسعه یافته است باید تفاوت قائل بود.
ایجاد و ابداع فنون و تکنیک های لازم برای مدیریّت پیچیدگی را باید به عنوان هستهٔ بنیادین تلاش های علمی و پژوهشی گذشته، حال، و آینده، در تمامی زمینه های علوم رایانه، و به ویژه، در هوش مصنوعی معرّفی کرد. شیوه ها و تکنیک های هوش مصنوعی، در واقع، برای حل آن دسته از مسائل به وجود آمده است که به طور سهل و آسان توسط برنامه نویسی تابعی (Functional programming) ، یا شیوه های ریاضی قابل حلّ نبوده اند.
بطور کلّی، هوش مصنوعی را می توان از زوایای متفاوتی مورد بررسی و مطالعه قرار داد. مابین هوش مصنوعی به عنوان یک هدف، هوش مصنوعی به عنوان یک رشته تحصیلی دانشگاهی، و یا هوش مصنوعی به عنوان مجموعهٔ فنون و راه کارهایی که توسط مراکز علمی مختلف و صنایع گوناگون تنظیم و توسعه یافته است باید تفاوت قائل بود.
ایجاد و ابداع فنون و تکنیک های لازم برای مدیریّت پیچیدگی را باید به عنوان هستهٔ بنیادین تلاش های علمی و پژوهشی گذشته، حال، و آینده، در تمامی زمینه های علوم رایانه، و به ویژه، در هوش مصنوعی معرّفی کرد. شیوه ها و تکنیک های هوش مصنوعی، در واقع، برای حل آن دسته از مسائل به وجود آمده است که به طور سهل و آسان توسط برنامه نویسی تابعی (Functional programming) ، یا شیوه های ریاضی قابل حلّ نبوده اند.
8
9
هوش مصنوعی Artificial Intelligence
فهرست
عاملهای حل مسئله
مسئله
اندازه گیری کارایی حل مسئله
جستجوی ناآگاهانه
اجتناب از حالتهای تکراری
جستجو با اطلاعات ناقص
10
حل مسئله با جستجو
عاملهای حل مسئله
چهار گام اساسی برای حل مسائل
فرموله کردن هدف: وضعیتهای مطلوب نهایی کدامند؟
فرموله کردن مسئله: چه فعالیتها و وضعیتهایی برای رسیدن به هدف موجود است؟
جستجو: انتخاب بهترین دنباله از فعالیتهایی که منجر به حالاتی با مقدار شناخته شده میشود.
اجرا: وقتی دنباله فعالیت مطلوب پیدا شد، فعالیتهای پیشنهادی آن میتواند اجرا شود.
11
حل مسئله با جستجو
مثال: نقشه رومانی
12
حل مسئله با جستجو
صورت مساله: رفتن از آراد به بخارست
فرموله کردن هدف: رسیدن به بخارست
فرموله کردن مسئله:
وضعیتها: شهرهای مختلف
فعالیتها: حرکت بین شهرها
جستجو: دنباله ای از شهرها مثل:آراد، سیبیو، فاگارس، بخارست
این جستجو با توجه به کم هزینه ترین مسیر انتخاب میشود
مثال: نقشه رومانی
13
حل مسئله با جستجو
مسئله
حالت اولیه: حالتی که عامل از آن شروع میکند.
در مثال رومانی: شهر آراد n(Arad)
تابع جانشین: توصیفی از فعالیتهای ممکن که برای عامل مهیا است.
در مثال رومانی:Zerind,Sibui,Timisoara} S(Arad)={
فضای حالت: مجموعه ای از حالتها که از حالت اولیه میتوان به آنها رسید.
در مثال رومانی: کلیه شهرها که با شروع از آراد میتوان به آنها رسید
تابع جانشین + حالت اولیه = فضای حالت
14
حل مسئله با جستجو
آزمون هدف: تعیین میکند که آیا حالت خاصی، حالت هدف است یا خیر
هدف صریح: در مثال رومانی، رسیدن به بخارست
هدف انتزاعی: در مثال شطرنج، رسیدن به حالت کیش و مات
مسیر: دنباله ای از حالتها که دنباله ای از فعالیتها را به هم متصل میکند.
در مثال رومانی: Arad, Sibiu, Fagaras یک مسیر است
هزینه مسیر: برای هر مسیر یک هزینه عددی در نظر میگیرد.
در مثال رومانی: طول مسیر بین شهرها بر حسب کیلومتر
راه حل مسئله مسیری از حالت اولیه به حالت هدف است
راه حل بهینه کمترین هزینه مسیر را دارد
15
حل مسئله با جستجو
مثال: دنیای جارو برقی
حالتها: دو مکان که هر یک ممکن است کثیف یا تمیز باشند.لذا 8 = 2^2* 2حالت در این جهان وجود دارد
حالت اولیه: هر حالتی میتواند به عنوان حالت اولیه طراحی شود
تابع جانشین: حالتهای معتبر از سه عملیات: راست، چپ، مکش
آزمون هدف: تمیزی تمام مربعها
هزینه مسیر: تعداد مراحل در مسیر
16
حل مسئله با جستجو
مثال: دنیای جارو برقی
حالتها: دو مکان که هر یک ممکن است کثیف یا تمیز باشند.لذا 8 = 2^2* 2حالت در این جهان وجود دارد
حالت اولیه: هر حالتی میتواند به عنوان حالت اولیه طراحی شود
تابع جانشین: حالتهای معتبر از سه عملیات: راست، چپ، مکش
آزمون هدف: تمیزی تمام مربعها
هزینه مسیر: تعداد مراحل در مسیر
17
حل مسئله با جستجو
مثال: معمای8
حالتها: مکان هر هشت خانه شماره دار و خانه خالی در یکی از 9 خانه
حالت اولیه: هر حالتی را میتوان به عنوان حالت اولیه در نظر گرفت
تابع جانشین: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا یا پایین
آزمون هدف: بررسی میکند که حالتی که اعداد به ترتیب چیده شده اند(طبق شکل روبرو) رخ داده یا نه
هزینه مسیر: برابر با تعداد مراحل در مسیر
18
حل مسئله با جستجو
مثال: معمای8
حالتها: مکان هر هشت خانه شماره دار و خانه خالی در یکی از 9 خانه
حالت اولیه: هر حالتی را میتوان به عنوان حالت اولیه در نظر گرفت
تابع جانشین: حالتهای معتبر از چهار عمل، انتقال خانه خالی به چپ، راست، بالا یا پایین
آزمون هدف: بررسی میکند که حالتی که اعداد به ترتیب چیده شده اند(طبق شکل روبرو) رخ داده یا نه
هزینه مسیر: برابر با تعداد مراحل در مسیر
19
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی افزایشی
حالتها: هر ترتیبی از 0 تا 8 وزیر در صفحه، یک حالت است
حالت اولیه: هیچ وزیری در صفحه نیست
تابع جانشین: وزیری را به خانه خالی اضافه میکند
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
در این فرمول بندی باید 14^10*3 دنباله ممکن بررسی میشود
20
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی افزایشی
حالتها: هر ترتیبی از 0 تا 8 وزیر در صفحه، یک حالت است
حالت اولیه: هیچ وزیری در صفحه نیست
تابع جانشین: وزیری را به خانه خالی اضافه میکند
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
در این فرمول بندی باید 14^10*3 دنباله ممکن بررسی میشود
21
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی حالت کامل
حالتها: چیدمان n وزیر (0≤ n≤ 8) ، بطوریکه در هر ستون از n ستون سمت چپ، یک وزیر قرار گیرد و هیچ دو وزیری بهم گارد نگیرند
حالت اولیه: با 8 وزیر در صفحه شروع میشود
تابع جانشین: وزیری را در سمت چپ ترین ستون خالی قرار میدهد، بطوری که هیچ وزیری آن را گارد ندهد
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
این فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش میدهد
22
حل مسئله با جستجو
مثال: مسئله 8 وزیر
فرمول بندی حالت کامل
حالتها: چیدمان n وزیر (0≤ n≤ 8) ، بطوریکه در هر ستون از n ستون سمت چپ، یک وزیر قرار گیرد و هیچ دو وزیری بهم گارد نگیرند
حالت اولیه: با 8 وزیر در صفحه شروع میشود
تابع جانشین: وزیری را در سمت چپ ترین ستون خالی قرار میدهد، بطوری که هیچ وزیری آن را گارد ندهد
آزمون هدف: 8وزیر در صفحه وجود دارند و هیچ کدام به یکدیگر گارد نمیگیرند
این فرمول بندی فضای حالت را از 14^10*3 به 2057 کاهش میدهد
23
حل مسئله با جستجو
اندازه گیری کارایی حل مسئله
کامل بودن: آیا الگوریتم تضمین میکند که در صورت وجود راه حل، آن را بیابد؟
بهینگی: آیا این راهبرد، راه حل بهینه ای را ارائه میکند.
پیچیدگی زمانی: چقدر طول میکشد تا راه حل را پیدا کند؟
تعداد گره های تولید شده در اثنای جستجو
پیچیدگی فضا: برای جستجو چقدر حافظه نیاز دارد؟
حداکثر تعداد گره های ذخیره شده در حافظه
24
حل مسئله با جستجو
اندازه گیری کارایی حل مسئله
کامل بودن: آیا الگوریتم تضمین میکند که در صورت وجود راه حل، آن را بیابد؟
بهینگی: آیا این راهبرد، راه حل بهینه ای را ارائه میکند.
پیچیدگی زمانی: چقدر طول میکشد تا راه حل را پیدا کند؟
تعداد گره های تولید شده در اثنای جستجو
پیچیدگی فضا: برای جستجو چقدر حافظه نیاز دارد؟
حداکثر تعداد گره های ذخیره شده در حافظه
25
حل مسئله با جستجو
جستجوی ناآگاهانه
ناآگاهی این است که الگوریتم هیچ اطلاعاتی غیر از تعریف مسئله در اختیار ندارد
این الگوریتمها فقط میتواند جانشینهایی را تولید و هدف را از غیر هدف تشخیص دهند
راهبردهایی که تشخیص میدهد یک حالت غیر هدف نسبت به گره غیر هدف دیگر، امید بخش تر است، جست و جوی آگاهانه یا جست و جوی اکتشافی نامیده میشود.
راهبردها
جست و جوی عرضی
جست و جوی عمقی
جست و جوی عمیق کننده تکراری
جست و جوی هزینه یکنواخت
جست و جوی عمقی محدود
جست و جوی دو طرفه
26
حل مسئله با جستجو
جستجوی عرضی
27
حل مسئله با جستجو
جستجوی عرضی
کامل بودن: بله
بهینگی: بله (مشروط)
در صورتی بهینه است که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد.(مثل وقتی که فعالیتها هزینه یکسانی دارند)
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی: بله (مشروط)
28
حل مسئله با جستجو
جستجوی هزینه یکنواخت
این جستجو گره n را با کمترین هزینه مسیر بسط میدهد
29
حل مسئله با جستجو
کامل بودن: بله
هزینه هر مرحله بزرگتر یا مساوی یک مقدار ثابت و مثبت ε باشد.(هزینه مسیر با حرکت در مسیر افزایش می یابد)
بهینگی: بله
هزینه هر مرحله بزرگتر یا مساوی ε باشد
پیچیدگی زمانی:
پیچیدگی فضا:
جستجوی هزینه یکنواخت
کامل بودن:
بهینگی:
30
حل مسئله با جستجو
جستجوی عمقی
2
3
4
5
6
7
31
حل مسئله با جستجو
کامل بودن: خیر
اگر زیر درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل باشد، جستجو هرگز خاتمه نمی یابد.
بهینگی: خیر
پیچیدگی زمانی:
پیچیدگی فضا:
جستجوی عمقی
کامل بودن:
بهینگی:
32
حل مسئله با جستجو
جستجوی عمقی محدود
مسئله درختهای نامحدود میتواند به وسیله جست و جوی عمقی با عمق محدود L بهبود یابد
33
حل مسئله با جستجو
جستجوی عمقی محدود
کامل بودن: خیر
اگر L<d و سطحی ترین هدف در خارج از عمق محدود قرار داشته باشد، این راهبرد کامل نخواهد بود.
بهینگی: خیر
اگر L>d انتخاب شود، این راهبرد بهینه نخواهد بود.
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی:
34
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
35
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
36
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
A
B
C
D
E
F
G
H
I
J
K
L
N
M
O
P
Q
S
R
37
حل مسئله با جستجو
جستجوی عمیق کننده تکراری
کامل بودن: بله
در صورتی که فاکتور انشعاب محدود باشد
بهینگی: بله
وقتی که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی:
38
حل مسئله با جستجو
جستجوی دو طرفه
انجام دو جست و جوی همزمان، یکی از حالت اولیه به هدف و دیگری از هدف به حالت اولیه تا زمانی که دو جست و جو به هم برسند
39
حل مسئله با جستجو
جستجوی دو طرفه
کامل بودن: بله
اگر هر دو جستجو، عرضی باشند و هزینه تمام مراحل یکسان باشد
بهینگی: بله
اگر هر دو جستجو، عرضی باشند و هزینه تمام مراحل یکسان باشد
پیچیدگی زمانی:
پیچیدگی فضا:
کامل بودن:
بهینگی:
40
حل مسئله با جستجو
اجتناب از حالتهای تکراری
وجود حالتهای تکراری در یک مسئله قابل حل، میتواند آن را به مسئله غیر قابل حل تبدیل کند
41
حل مسئله با جستجو
جستجو با اطلاعات ناقص
مسئله های فاقد حسگر: اگر عامل فاقد حسگر باشد، میتواند در یکی از چند حالت اولیه باشد و هر فعالیت میتواند آن را به یکی از چند حالت جانشین ببرد
مسئله های اقتضایی: اگر محیط به طور جزئی قابل مشاهده باشد یا اگر فعالیتها قطعی نباشد، ادراکات عامل، پس از هر عمل، اطلاعات جدیدی را تهیه میکنند. هر ادراک ممکن، اقتضایی را تعریف میکند که باید برای آن برنامه ریزی شود
مسائل خصمانه: اگرعدم قطعیت در اثر فعالیتهای عامل دیگری بوجود آید، مسئله را خصمانه گویند
مسئله های اکتشافی: وقتی حالتها و فعالیتهای محیط ناشناخته باشند، عامل باید سعی کند آنها را کشف کند. مسئله های اکتشافی را میتوان شکل نهایی مسئله های اقتضایی دانست
42
حل مسئله با جستجو
مثال: دنیای جاروبرقی فاقد حسگر
عامل جارو تمام اثرات فعالیتهایش را میداند اما فاقد حسگر است.
حالت اولیه آن یکی از اعضای مجموعه{1،2،3،4،5،6،7،8} میباشد
فعالیت ((Right {2،4،6،8}
فعالیت (Right,Suck) {4،8}
فعالیت (Right,Suck,Left,Suck) تضمین میکند که صرف نظر از حالت اولیه، به حالت هدف، یعنی 7 برسد
43
حل مسئله با جستجو
دنیای جاروبرقی فاقد حسگر
عامل باید راجع به مجموعه های حالتی که میتواند به آنها برسد استدلال کند. این مجموعه از حالتها را حالت باور گوییم.
اگر فضای حالت فیزیکی دارای s حالت باشد فضای حالت باور 2^s حالت باور خواهد داشت.
منابع
• آیلین ریچ، هوش مصنوعی (و تکنیک ها)، ترجمه آزاد از دکتر مهرداد فهیمی، نشر جلوه، ۱۳۷۵،
• نظام الدین فقیه، هوش مصنوعی در پیش بینی ایست خط تولید (کاربرد شبکه های عصبی مصنوعی)
• هوش مصنوعی: به شیوه ای مدرن
• هوش مصنوعی: راهنمائی برای سامانه های هوشمند
• کاربردهای هوش مصنوعی
با تشکر از توجه شما