هوش مصنوعی کشف یک مسیر از میان فضاهای مسئله از یک وضعیت آغازی به وضعیت هدف 60 ص

لینک دانلود و خرید پایین توضیحات

فرمت فایل word  و قابل ویرایش و پرینت

تعداد صفحات: 64

استدلال جلورو در مقابل عقب رو

هدف روال جستجو، کشف یک مسیر از میان فضاهای مسئله از یک وضعیت آغازی به وضعیت هدف است. چنین جستجویی می تواند در دو جهت حرکت کند:

به طرف جلو، از وضعیت های آغازی

به طرف عقب، از وضعیت های هدف

این دو قرینه هستند. فرض کنید که می خواهیم یک بازی معمای هشت را حل کنیم. قواعد این معما را می توان همانند شکل 1 نشان داد. در اینجا می خواهیم معمای شکل 2 را حل کنیم. این کار را می توان به دو طریق انجام داد:

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

Square 1 empty and Square 2 contains tile n (

Square 2 empty and Square 1 contains tile n

Square 1 empty and Square 4 contains tile n (

Square 4 empty and Square 1 contains tile n

Square 2 empty and Square 1 contains tile n (

Square 1 empty and Square 2 contains tile n

شکل 1 : یک نمونه از قواعد برای حل کردن معمای هشت

شکل 2 : یک مثال از بازی معمای هشت

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

به روش فوق استدلال هدف گرا یا زنجیرة عقب رو می گویند.

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

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

سه فاکتور در رابطه با این سئوال که استدلال باید در کدام جهت باشد مهم هستند:

تعداد وضعیت های آغازی بیشتر است یا هدف؟ ما همیشه مایلیم که از تعداد کمتر وضعیت ها به طرف تعداد بیشتر برویم.

در کدام جهت فاکتور شاخه شاخه شدن بزرگتر است؟ (این فاکتور تعداد متوسط گره هایی است که مستقیماً می توان از یک گره تک رسید) ما مایلیم در جهتی حرکت کنیم که این فاکتور کوچکتر است.

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

ذکر چند مثال برای روشنتر شدن مطلب ضروری است. به نظر می رسد که رانندگی از یک محل ناآشنا به طرف منزل خیلی راحت تر از منزل به طرف محل ناآشنا باشد. چرا؟ فاکتور شاخه شاخه شدن تقریباً در هر دو جهت یکسان است. نکتة مهم این است که ما خیلی نقاط نزدیک منزل را هم همانند منزل تلقی می کنیم و به این ترتیب تعداد محل هایی که جزء تعریف خانة ما می گنجند بیش از تعداد محل هایی است که به عنوان هدف ناآشنای ما وجود دارند. بنابراین اگر نقطة آغازی ما منزل ما ست و هدف ما یک محل ناآشناست بهتر است از استدلال عقب رو با شروع از محل ناآشنا استفاده کنیم.

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