فصل چهارم

روش‌های جستجو آگاهانه

1. فصل اول هوش مصنوعی Artificial Intelligence
2. فصل دوم عامل های هوشمند
3. فصل سوم حل مسائل توسط جستجو
4. فصل چهارم روش‌های جستجو آگاهانه
5. فصل 5 تئوری بازی
6. فصل ششم عامل‌هاییکه به طور منطقی استدلال می‌‌کنند
7. فصل هفتم منطق مرتبه اول
8. فصل هشتم استنتاج در منطق مرتبه اول
9. فصل نهم برنامه‌ریزی
10. فصل دهم عدم قطعیت

 

 

جستجوی بهترین:

این استراتژی به این صورت بیان می‌شود که در یک درخت، زمانی که گره‌ها مرتب می‌شوند، گره‌ای که بهترین ارزیابی را داشته باشد، قبل از دیگر گره‌ها بسط داده می‌شود.

هدف: یافتن راه‌حل‌های کم‌هزینه است، این الگوریتم‌ها عموماً از تعدادی معیار تخمین برای هزینه راه‌حل‌ها استفاده می‌‌کنند و سعی بر حداقل کردن آنها دارند.

حداقل هزینه تخمین زده شده برای رسیدن به هدف: جستجوی حریصانه

یکی از ساده‌ترین استراتژی‌های جستجوی بهترین، به حداقل رساندن هزینه تخمین زده شده برای رسیدن به هدف است. بدین صورت که حالت گره‌ای که به حالت هدف نزدیک‌تر است، ابتدا بسط داده می‌شود.

تابع کشف‌کننده: هزینه رسیدن به هدف از یک حالت ویژه می‌تواند تخمین زده شود اما دقیقاً تعیین نمی‌شود. تابعی که چنین هزینه‌هایی را محاسبه می‌کند تابع کشف‌کننده h نامیده می‌شود.

جستجوی حریصانه: جستجوی بهترین که h را به منظور انتخاب گره بعدی برای بسط استفاده می‌کند، جستجوی حریصانه (greedy search) نامیده می‌شود.

ویژگی‌های جستجوی حریصانه:

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

حداقل‌سازی مجموع هزینه مسیر: جستجوی A*

جستجو با هزینه یکسان، هزینه مسیر، g(n) را نیز حداقل می‌کند.

با ترکیب دو تابع ارزیابی داریم:

f(n) = g(n) + h(n)

:g(n) هزینه مسیر از گره آغازین به گره n  را به ما می‌دهد.

h(n): هزینه تخمین زده شده از ارزانترین مسیر از n به هدف است

و ما داریم:

هزینه تخمین زده شده ارزانترین راه حل از طریق n = f(n)

کشف‌کنندگی قابل قبول:

تابع hای را که هزینه‌ای بیش از تخمین برای رسیدن به هدف نداشته باشد، یک کشف‌کنندگی قابل قبول (admissible heuristic) گویند.

جستجوی A*:

جستجوی بهترین که f به عنوان تابع ارزیاب و یک تابع h قابل قبول استفاده می‌کند، به عنوان جستجوی A* شناخته می‌شود.

رفتار جستجوی A*

نگاهی گذرا به اثبات کامل و بهینه بودن A*:

مشاهده مقدماتی:

تقریباً تمام کشف‌کنندگی‌های مجاز دارای این ویژگی هستند که در طول هر مسیری از ریشه، هزینه f هرگز کاهش پیدا نمی‌کند.

این خاصیت برای کشف‌کنندگی، خاصیت یکنوایی (monotonicity) گفته می‌شود.

اگر یکنوا نباشد، با ایجاد یک اصلاح جزئی آن را یکنوا می‌کنیم.

بنابراین هر گره جدیدی که تولید می‌شود، باید کنترل کنیم که آیا هزینه f این گره از هزینه f پدرش کمتر است یا خیر. اگر کمتر باشد، هزینه f پدر به جای فرزند می‌نشیند:

بنابراین:

f همیشه در طول هر مسیری از ریشه غیرکاهشی خواهد بود، مشروط بر اینکه h امکان‌پذیر باشد.

h*(n) : هزینه واقعی رسیدن از n به هدف است.

در استفاده عملی، خطاها با هزینه مسیر متناسب هستند، و سرانجام رشد نمایی هر کامپیوتر را تسخیر می‌کند. البته، استفاده از یک کشف‌کنندگی خوب هنوز باعث صرفه‌جویی زیادی نسبت به جستجوی ناآگاهانه می‌شود.

A* معمولاً قبل از اینکه دچار کمبود زمان شود، دچار کمبود فضا می‌شود. زیرا این جستجو تمام گره‌های تولید شده را در حافظه ذخیره می‌کند.

توابع کشف‌کننده:

مسئله 8 را بررسی می‌کنیم:

معمای 8 یکی از مسائل اولیه کشف‌کنندگی بود.

هدف: لغزاندن چهارخانه‌ها به طور افقی یا عمودی به طرف فضای خالی است تا زمانی که ساختار کلی مطابق با هدف (goal) باشد.

 

 

 

 

 

 

 

اگر خواستار یافتن راه‌حل‌های کوتاه باشیم، به یک تابع کشف‌کننده نیاز داریم که هرگز در تعداد مراحل به هدف اغراق نکند. در اینجا ما دو کاندید داریم:

h1   = تعداد چهارخانه‌هایی که در مکان‌های نادرست هستند. h1  یک کشف‌کننده مجاز است، زیرا واضح است که هر چهارخانه‌ای که خارج از مکان درست باشد حداقل یکبار باید جابجا شود.

h2  = مجموع فواصل چهارخانه‌ها از مکان‌های هدف صحیحشان است. فاصله‌ای که ما حساب می‌کنیم، مجموع فواصل عمودی و افقی است که بعضی وقتها city block distance و یا Manhattan distance نامیده می‌شود.

اثر صحت کشف‌کنندگی بر کارایی:

یک راه برای تشخیص کیفیت کشف‌کنندگی فاکتور انشعاب مؤثر b* است. اگر مجموع تعداد گره‌های بسط داده شده توسط A* برای یک مسئله ویژه N باشد و عمق راه حل d، سپسb*  فاکتور انشعابی است که یک درخت یکنواخت با عمق d خواهد داشت تا گره‌های N را نگهدارد. بنابراین:

N=1+ b*+( b*)2…+( b*)d

• معمولاً فاکتور انشعاب مؤثر که توسط کشف‌کنندگی نمایش داده می‌شود، مقدار ثابتی دارد.
• یک کشف‌کنندگی خوب طراحی شده، b* در حدود 1 دارد.

کشف‌کننده‌ها برای مسائل ارضا محدودیت:

مسئله ارضاء محدودیت شامل یک سری از متغیرهایی است که ,ویژگی‌های زیر را دارا هستند:

• می‌توانند مقادیری را از دامنه داده شده دریافت کنند.
• با یک سری از محدودیت‌ها، ویژگی‌های راه حل را مشخص کنند.

رنگ‌آمیزی نقشه نمونه‌ای از این کشف‌کننده‌هاست:

هدف رنگ‌آمیزی نقشه، اجتناب از رنگ‌آمیزی مشابه دو کشور همسایه است.

ما حداکثر از سه رنگ (قرمز، آبی، سبز) می‌توانیم استفاده کنیم:

اگر رنگ سبز را برای کشور A، قرمز را برای B، انتخاب کنیم، کشور E باید آبی باشد. در این صورت ما ناچاریم که C را به رنگ قرمز درآوریم و F سبز باشد. رنگ‌آمیزی D با رنگ آبی یا قرمز، بستگی به راه‌حل دارد. در این حالت مسئله بدون هیچگونه جستجویی حل می‌شود.

جستجوی SMA*:

الگوریتم SMA*، حافظه محدود A* ساده شده (Simplified-Memory-BoundedA*) می‌باشد.

این الگوریتم، قادر است تا از تمام حافظه موجود برای اجرای جستجو استفاده کند. استفاده از حافظه بیشتر کارایی جستجو را وسعت می‌بخشد. می‌توان همیشه از فضای اضافی صرفنظر کرد.

SMA*  دارای خواص زیر است:

• می‌تواند از تمام حافظه قابل دسترس استفاده کند.
• از حالات تکراری تا جایی که حافظه اجازه می‌دهد، جلوگیری می‌کند.
• این الگوریتم کامل است به شرط آنکه حافظه برای ذخیره کم عمق‌ترین مسیر راه حل کافی باشد.
• این الگوریتم بهینه است، اگر حافظه کافی برای ذخیره کم‌عمق‌ترین مسیر راه‌حل کافی باشد. بعلاوه بهترین راه‌حلی را برمی‌گرداند که بتواند با حافظه موجود مطابقت داشته باشد.
• زمانی که حافظه موجود برای درخت جستجوی کامل کافی باشد، جستجو Optimally efficient است.

طراحی SMA* ساده است.

• زمانی که نیاز به تولید فرزند داشته باشد ولی حافظه‌ای نداشته باشد، نیاز به ساختن فضا بر روی صف دارد. برای انجام این امر، یک گره را حذف می‌کند. گره‌هایی که به این طریق از صف حذف می‌شوند، گره‌های فراموش‌شده یا (forgotten nodes) نامیده می‌شوند.
• برای اجتناب از جستجوی مجدد زیردرخت‌هایی که از حافظه حذف شده‌اند، در گره‌های اجدادی، اطلاعاتی در مورد کیفیت بهترین مسیر در زیر درخت فراموش شده، نگهداری می‌شود.

الگوریتم‌های اصلاح تکراری

• بهترین راه برای فهم الگوریتم‌های اصلاح تکراری درنظر داشتن تمام حالاتی است که روی سطح یک دورنمایی در معرض دید قرار داده شده است. ارتفاع هر نقطه در دورنما مطابق با تابع ارزیاب حالت آن نقطه است. ایده اصلاح تکراری، حرکت کردن در اطراف دورنما و سعی بر یافتن قله‌های مرتفع است، که همانا راه‌حل‌های بهینه هستند.
• الگوریتم‌های اصلاح تکراری معمولاً اثر حالت جاری را فقط حفظ می‌کنند، و توجهی فراتر از همسایگی آن حالت ندارند.

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

این الگوریتم‌ها به دو گره اصلی تقسیم می‌شوند.

• الگوریتم‌های تپه‌نوردی (Hill-climbing)
• Simulated annealing

1- الگوریتم‌های جستجوی تپه‌نوردی (Hill-climbing)

یک اصلاح خوب این است زمانی که بیش از یک فرزند خوب برای انتخاب وجود دارد، الگوریتم بتواند به طور تصادفی از میان آنها یکی را انتخاب کند.

این سیاست ساده، سه زیان عمده دارد:

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

در هر مورد، الگوریتم به نقطه‌ای می‌رسد که هیچ پیشرفتی نیست. اگر این اتفاق بیفتد، تنها کار ممکن برای انجام دادن آغاز مجدد از نقطه شروع دیگری دوباره آغاز می‌شود.

موفقیت hill-climbing خیلی به ظاهر فضای حالت «سطح» بستگی دارد: اگر فقط ماکزیمم‌های محلی کمی وجود داشته باشد، تپه‌نوردی با شروع تصادفی خیلی سریع راه‌حل خوبی را پیدا خواهد کرد.

2- Simulated annealing

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

راه‌حل دو مرحله‌ای برای مسئله 8 وزیر با استفاده از حداقل برخوردها را نشان می‌دهد. در هر مرحله یک وزیر به منظور تعیین مجدد ستون انتخاب می‌شود. تعداد برخوردها (در این مورد، تعداد وزیرهای حمله‌کننده) در هر چهارخانه نشان داده شده است. الگوریتم وزیر را به چهارخانه‌ای که حداقل برخورد را داشته باشد، برای از بین بردن تصادفی برخوردها، حرکت می‌دهد.

اگر حرکت واقعاً شرایط را بهبود بخشد، آن حرکت همیشه اجرا می‌شود.

پارامتر‌های مؤثر به شرح زیر می‌باشند:

1-  : چگونگی ارزیابی.

2- T: تعیین احتمال.

الگوریتم شباهت صریحی با annealing (پردازشی که به طور آهسته مایعی را تا زمانی که یخ ببندد سرد می‌کند)، گسترش یافته است. مقدار تابع مطابق با انرژی ورودی اتم‌های ماده است، و T با دما مطابقت دارد. جدول میزان دما را در جایی که پائین آمده است، تعیین می‌کند.

کاربردها در مسائل ارضا محدودیت

مسائل ارضاء محدودیت (CSP)، می‌توانند توسط روش‌های اصلاح تکراری با استفاده از موارد زیر حل شوند.

• مقدار دادن به تمام متغیرها.
• به کاربردن عملگرهای تغییر به منظور حرکت دادن ساختار به طرف یک راه‌حل.

الگوریتم‌هایی که CSPها را حل می‌کنند، روش‌های تصحیح کشف‌کنندگی، نامیده می‌شوند، زیرا آنها تناقضات را در ساختار جاری مسئله اصلاح می‌کنند.

در انتخاب مقدار جدید برای یک متغیر، واضح‌ترین کشف‌کنندگی انتخاب مقداری است که کمترین مقدار تناقضات را با دیگر متغیرها نتیجه دهد، که همان کشف‌کنندگی مینیمم تناقضات است.