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