Y@SiN
01-25-2010, 02:10 PM
مهمترین مشکل روش جستجوی عمقی را که در برخی از مسائل با آن مواجه خواهیم بود، قرار گرفتن این روش جستجو در حلقه بینهایت می باشد. به عنوان مثال گراف شکل روبرو را در نظر بگیرید . فرض کنید می خواهیم مسیری از گره 1 به گره 5 با استفاده از روش جستجوی عمقی پیدا کنیم. شکل زیر مراحل مختلف تشکیل درخت جستجو را نشان می دهد :
http://pnu-club.com/imported/mising.jpg
http://pnu-club.com/imported/mising.jpg
همانطور که از شکل پیداست ، استفاده از روش جستجوی عمقی برای حل این مساله هیچگاه به یافتن جواب منجر نخواهد شد. چرا که حلقه بینهایتی از گسترش گره های 1 و 2 تشکیل می شود. مشکل قرار گرفتن در حلقه بینهایت از گسترش حالت های تکراری در هنگام جستجو حاصل شده است. بنابراین یکی از روش های حل این مشکل تشخیص حالت های تکراری هنگام گسترش فرزندان یک گره می باشد.
تشخیص حالت های تکراری یکی از مهمترین نکات طراحی الگوریتم های هوش مصنوعی می باشد که وابستگی بسیاری به نحوه نمایش راه حل مساله دارد. نحوه نمایش مساله و تشخیص حالت های تکراری را در انتهای فصل و در مثال های مختلف مورد بررسی قرار خواهیم داد. در حال حاضر با روش دیگری به رفع این مشکل خواهیم پرداخت.
می دانیم در صورتی که مسیری از گره 1 به گره 5 در گراف وجود داشته باشد، طول این مسیر نمی تواند بیش از 5 یال باشد. بنابراین می توان با اتخاذ یک محدودیت به روش جستجوی عمقی از گسترش گره هایی که در عمق 5 از درخت جستجو قرار دارند، جلوگیری کرد. به عبارت دیگر برای گره هایی که در عمق 5 از درخت جستجو قرار دارند ، هیچ فرزندی تولید نکنیم. پیمایش در فضای جستجوی مساله با این روش را روش جستجوی عمقی محدود شده می نامیم. یکبار دیگر با استفاده از روش جستجوی عمقی محدود شده به عمق 5 به حل مساله فوق می پردازیم. شکل زیر مراحل مختلف تشکیل درخت جستجو را نشان می دهد ( ادامه درخت جستجوی شکل بالا) :
http://pnu-club.com/imported/mising.jpg
با توجه به گراف شکل بالا ، مسیر 5-4-3-1-2-1 ما را از گره 1 به گره شماره 5 هدایت می کند. با وجود اینکه محدود کردن عمق درخت مشکل حلقه بینهایت را رفع کرد، اما هنوز مشکل حالت تکراری در روش جستجوی عمقی محدود شده وجود دارد. برای حل همزمان مشکل حلقه بینهایت و حالت تکراری، می توان از روش جستجوی سطحی استفاده کرد که در بخش بعد به شرح آن می پردازیم.
http://pnu-club.com/imported/mising.jpg
http://pnu-club.com/imported/mising.jpg
همانطور که از شکل پیداست ، استفاده از روش جستجوی عمقی برای حل این مساله هیچگاه به یافتن جواب منجر نخواهد شد. چرا که حلقه بینهایتی از گسترش گره های 1 و 2 تشکیل می شود. مشکل قرار گرفتن در حلقه بینهایت از گسترش حالت های تکراری در هنگام جستجو حاصل شده است. بنابراین یکی از روش های حل این مشکل تشخیص حالت های تکراری هنگام گسترش فرزندان یک گره می باشد.
تشخیص حالت های تکراری یکی از مهمترین نکات طراحی الگوریتم های هوش مصنوعی می باشد که وابستگی بسیاری به نحوه نمایش راه حل مساله دارد. نحوه نمایش مساله و تشخیص حالت های تکراری را در انتهای فصل و در مثال های مختلف مورد بررسی قرار خواهیم داد. در حال حاضر با روش دیگری به رفع این مشکل خواهیم پرداخت.
می دانیم در صورتی که مسیری از گره 1 به گره 5 در گراف وجود داشته باشد، طول این مسیر نمی تواند بیش از 5 یال باشد. بنابراین می توان با اتخاذ یک محدودیت به روش جستجوی عمقی از گسترش گره هایی که در عمق 5 از درخت جستجو قرار دارند، جلوگیری کرد. به عبارت دیگر برای گره هایی که در عمق 5 از درخت جستجو قرار دارند ، هیچ فرزندی تولید نکنیم. پیمایش در فضای جستجوی مساله با این روش را روش جستجوی عمقی محدود شده می نامیم. یکبار دیگر با استفاده از روش جستجوی عمقی محدود شده به عمق 5 به حل مساله فوق می پردازیم. شکل زیر مراحل مختلف تشکیل درخت جستجو را نشان می دهد ( ادامه درخت جستجوی شکل بالا) :
http://pnu-club.com/imported/mising.jpg
با توجه به گراف شکل بالا ، مسیر 5-4-3-1-2-1 ما را از گره 1 به گره شماره 5 هدایت می کند. با وجود اینکه محدود کردن عمق درخت مشکل حلقه بینهایت را رفع کرد، اما هنوز مشکل حالت تکراری در روش جستجوی عمقی محدود شده وجود دارد. برای حل همزمان مشکل حلقه بینهایت و حالت تکراری، می توان از روش جستجوی سطحی استفاده کرد که در بخش بعد به شرح آن می پردازیم.