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