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