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

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

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

فرض کنید که می خواهیم یک بازی معمای هشت را حل کنیم.

قواعد این معما را می توان همانند شکل 1 نشان داد.

در اینجا می خواهیم معمای شکل 2 را حل کنیم.

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

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

برای سطح بعدی درخت عمل فوق را در مورد گره های سطح قبلی انجام دهید.

به این کار آنقدر ادامه دهید تا به وضعیتی برابر با وضعیت هدف رسیده باشید.

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

وضعیت(های) هدف را در ریشه درخت قرار دهید.

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

با استفاده از سمت چپ این قواعد و بکارگیری آنها گره های سطح دوم این درخت را بسازید.

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

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

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

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

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

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

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

در کدام جهت فاکتور شاخه شاخه شدن بزرگتر است؟

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

اگر این طور است بهتر است حرکت در جهتی باشد که با طرز تفکر استفاده کننده مطابقت بیشتری دارد.ذکر چند مثال برای روشنتر شدن مطلب ضروری است.

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

چرا؟

فاکتور شاخه شاخه شدن تقریباً در هر دو جهت یکسان است.

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

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

از طرف دیگر یک مسئله انتگرال گیری را در نظر بگیرید.

فضای مسئله عبارت است از مجموعه فرمولها که برخی دارای عبارت انتگرال هستند.

وضعیت آغازی یک فرمول بخصوص با عبارت انتگرال است.

وضعیت هدف فرمولی است که معادل فرمول اولی است ولی عبارت انتگرال ندارد.

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

در مثال فوق فرض ما این بوده است که فاکتور شاخه شاخه شدن در هر دو جهت تقریباً یکسان است.

اگر اینگونه نباشد باید آنرا نیز در نظر گرفت.

باز هم مسئله ثابت کردن تئوری هایی در یک قلمرو بخصوص ریاضی را در نظر بگیرید.

وضعیت هدف ما عبارتست از اثبات یک تئوری خاص.

وضعیت آغازی ما معمولاً تعداد کمی از اصول می باشند.

این دو مجموعه هدف و آغازی معمولاً از نظر اندازه فرقی ندارند.

اما فاکتور شاخه شاخه شدن در هر دو جهت را در نظر بگیرید.

از یک تعداد کمی اصل، می توانیم تعداد زیادی تئوری نتیجه بگیریم.

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

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

این بدین معناست که ما بهتر است در هنگام اثبات تئوریها از اثبات شروع کنیم و به عقب برویم.

ریاضیدانان مدتهاست که این را درک کرده اند.

سومین عاملی که جهت جستجو را تعیین می کند این است که گاهی برنامه مجبور است دلایل خود را توجیه کند.

طراحان MYCIN (برنامه تشخیص بیماری های عفونی) به این نکته توجه خاصی مبذول داشتند.

این برنامه از هدفش که تعیین علت بیماری شخص مریض است به طرف عقب استدلال می کند.

برای این منظور از قواعدی استفاده می کند که به آن چیزهایی مشابه عبارت زیر را می گویند: "If the organism has the following set of characteristics as determined by the lab results, then it is likely that it is organism X" با استدلال عقب رو با استفاده از قواعدی همچون قواعد فوق، برنامه می تواند به سئوالاتی از قبیل سئوال: Why should I perform that test you just asked for?

پاسخی همانند زیر بدهد: "Because it would help to determine whether organism X is present." از اکثر تکنیک های جستجو که در این فصل معرفی می شوند در استدلال جلورو و عقب رو می توان استفاده کرد.

یکی از کارهای جالب این است که از هر دو جهت شروع کنیم تا اینکه از دو مسیر به هم برسند.

به این استراتژی جستجوی دوسو می گویند.

این روش همیشه مؤثر نیست و شکل 3 یکی از علل شکست این گونه جستجو را نشان می دهد: ************************* شکل 3- استفاده بد از جستجوی هیوریستیک دوسو ارائه دانش به کمک سایر منطق ها مقدمه همانطوری که درقسمت پیش گفتیم، تکنیک های منطق مسند برای حل مسائل گوناگون مفید هستند.

اما متأسفانه منطق مسند در بسیاری دیگر از قلمروها، راهی مناسب برای ارائه و کار با اطلاعات مهم فراهم نمی آورد.

به عنوان نمونه در زیر چند نوع از اطلاعاتی که ارائه آنها در منطق مسند دشوار است آمده اند: «امروز خیلی گرم است».

چگونه می توان درجات نسبی گرما را نشان داد؟

«افرا مو زرد معمولاً چشمان آبی دارند».

چگونه می توان یک «مقدار» اطمینان را ارائه نمود؟

«فرض کنید هر فرد بالغی که می بینید، بلد است بخواند، مگر اینکه گواهی برخلاف آن وجود داشته باشد».

چگونه می توان این نکته را ارائه نمود که از عدم حضور یک حقیقت می توان حقیقت دیگری را استنتاج نمود؟

«بهتر است که قطعات بیشتری (مهره های بیشتری) نسبت به رقیب خود در صفحه داشته باشید» چگونه می توان این نوع از اطلاعات هیوریستیک را ارائه نمود؟» «من می دانم که Bill فکر می کند تیم Giants خواهد برد.

اما خودم فکر می کنم که آنها خواهند باخت».

چگونه می توان چند سیستم تفکر متفاوت را یکجا ارائه نمود؟

بسیاری از استدلال هایی که انسان ها انجام می دهند عبارت از کار با یک مجموعه از اعتقادات و تغییر دادن آنها است.

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

ناکامل و ناسازگار بودن می تواند از مشخصات طبیعی یک مجموعه از اعتقادات، که به آن «سیستم اعتقادات» می گوییم، باشد.

برای اینکه برنامه ها بتوانند با سیستم های اعتقادات کار کنند، احتیاج به سیستم استدلال است که بتواند برنامه های بتوانند با سیستم های اعتقادات کار کنند، احتیاج به سیستم استدلال است که بتواند با اطلاعاتی همچون آنها که در بالا آمدند کار کند.

برای اینکه بهتر بفهمیم منظور از اعتقادات، ایجاد، تست و همچنین تغییر آنها چیست یک مثال از کتابی به نام The web of belief را به فارسی برمی گردانیم و آنرا بررسی می کنیم.

فرض کنید فهیمی، صدری و تفضلی از افراد مورد ظن در رابطه با یک قتل می باشند!

فهیمی دارای عذری است.

به این ترتیب که اسم او در دفتر هتل عباسی برای روز قتل ثبت شده است.

صدری هم عذری دارد زیرا برادر خانمش تأیید کرده که وی در زمان وقوع قتل نزد او بوده است.

تفضلی هم عذری دارد، او می گوید در استادیوم تختی مشغول تماشای مسابقه فوتبال بین تیم استقلال و آزادی بوده است فرض کنید فهیمی، صدری و تفضلی از افراد مورد ظن در رابطه با یک قتل می باشند!

تفضلی هم عذری دارد، او می گوید در استادیوم تختی مشغول تماشای مسابقه فوتبال بین تیم استقلال و آزادی بوده است.

اما ما فقط گفته خودش را داریم.

بنابراین ما معتقدیم که: 1- فهیمی مرتکب قتل نشده است.

2- صدری هم مرتکب قتل نشده است.

3- فهیمی، صدری یا تفضلی مرتکب قتل شده اند.

اما تفضلی شانس خوبی آورده است: تلویزیون او را در استادیوم در تاریخ مورد نظر نشان داده است.

پس اعتقاد جدیدی برای ما حاصل می شود: 4- تفضلی مرتکب قتل نشده است.

اعتقادات 1 تا4 ما ناسازگار هستند.

پس باید یکی را برای رد کردن انتخاب نمود.

کدامیک ضعیف ترین گواهی را دارا می باشند؟

پایه و اساس اعتقاد 1 قوی است زیرا هتل عباسی هتل معتبری است.

پایه اعتقاد 2 ضعیف تر است، زیرا ممکن است برادرخانم صدری دروغ بگوید.

اعتقاد 3 از دو جهت محکم می شود: اول اینکه هیچ علامت دزدی وجود ندارد و دوم اینکه اگر از امکان دزدی بگذریم فقط فهیمی، صدری یا تفضلی می توانسته اند سودی از قتل ببرند!

این حذف امکان دزدی قطعی است اما قسمت دوم هنوز قطعی نیست زیرا ممکن است نفر چهارمی باشد که او هم سودی از قتل می برده است.

اعتقاد 4 قطعی است.

به این ترتیب 2 و 3 ضعیف هستند یعنی یا باید صدری را متهم کرد یا به دنبال نفر چهارم گشت.

ببینید چگونه تجدیدنظر ما تا پایین ادامه می یابد.

اگر 2 را رد نماییم در واقع در اعتقاد قبلی خود (هر چند ضمنی) که برادرخانمش راست گفته است تجدیدنظر کرده ایم.

اگر 3 را رد کنیم، در اعتقاد قبلی خود مبنی بر اینکه از دزدی که بگذریم فقط این سه نفر می توانسته اند از قتل سودی ببرند تجدیدنظر نموده ایم.

در ضمن نوعی حالت اختیاری و دلبخواهی در سازمان این بررسی وجود دارد.

البته اعتقادات ناسازگار 1 تا 4 را بیرون و سپس آنها را با برخی اعتقادات ضمنی همراه کردیم: برای مثال اعتقاد در مورد قسمت پذیرش هتل، اعتبار هتل، تلویزیون و برادر خانم.

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

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

ما چهارتایی اصلی را انتخاب نمودیم و برای حذف یا انتخاب یکی از سایر اعتقادات کمک گرفتیم.

این در واقع همان استراتژی divide and conquer است.

به این ترتیب که وقتی که یک مجموعه از اعتقادات به گونه ای در کنار هم جمع شده اند که تناقض ایجاد می کنند، زیر مجموعه ای کوچک از آنها را طوری انتخاب کنید که هنوز دارای تناقض باشند.

برای مثال: 1 تا 4.

زیرا مطمئن هستیم که به این روش بزودی برخی از اعتقادات را از زیرمجموعه حذف خواهیم کرد.

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

کی از کنکاش در عقاید دست برخواهیم داشت؟

در رابطه با عقاید 1 تا 4 دیدیم که عقاید زیرین آنها را نیز بیرون کشیدیم.

البته می توانستیم عمیق تر هم برویم.

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

داستان بالا تعدادی از مشکلات مربوط به دانش غیرمطمئن و مشکوک را نشان می دهد.

در علوم کامپیوتر چندین راه حل برای این مشکلات پیشنهاد شده است: منطق غیریکنواخت- این منطق اجازه می دهد احکام از بانک اطلاعات حذف شوند یا بدان اضافه