الگوریتم دایجسترا

الگوریتم های حریصانه مشابه برنامه نویسی پویا، بیشتر برای حل مسائل بهینه سازی به كار می روند. با این اختلاف كه در برنامه سازی پویا از یك رابطه بازگشتی برای حل زیرمسأله ها استفاده می كنند. در روش حریصانه، تقسیم مسأله ها به زیر مسأله ها انجام نمی گیرد و روش تكرارشونده را به كار می برند.
در روش حریصانه در هر لحظه، با توجه به عناصر داده ای مفروض، عنصری را كه دارای ویژگی بهترین یا بهینه است (مانند كوتاه ترین مسیر، بالاترین ارزش، كمترین سرمایه گذاری، بیشترین سود و ...) انتخاب می كنند بدون این كه انتخاب های قبلی ما بعدی را در نظر بگیرد ولی انتخاب های بهینه محلی همواره منجر به راه حل بهینه سراسری نمی شود. این روش انتخاب، منجر به ارائه یك الگوریتم ساده و كارآمد می شود.
تعیین درخت های پوشالی مینیمم با استفاده از الگوریتم های پرایم، كروسكال محاسبه كوتاه ترین مسیر تك منبع با كاربرد الگوریتم دایجسترا ، مسأله زمان بندی مانند بهینه سازی زمان انتظار و سرویس به كاربران برای دسترسی به دیسك گردان ها در یك شبكه رایانه ای، تعیین حداكثر بهره برای مشتریان در یك زمان معین و مسأله كوله پشتی (كسری، صفرو یك) با استفاده از روش حریصانه قابل اجرا هستند.
الگوریتم عقبگرد
▪ الگوریتم عقبگرد، برای یافتن جواب مسأله ای با فضای جست وجو به طور گسترده ای به كار می رود و از آن به عنوان حالت اصلاح شده جست وجوی عمقی یك درخت نام می برند. در این روش، منظور از عقبگرد، پیدا كردن راه حل مسأله از طریق جست وجوی عمقی در درخت فضای حالت برای یافتن گره های امید بخش است. در صورتی كه موقع پیمایش درخت به یك گروه غیرامیدبخش برخورد كند كه منجر یه یافتن جواب مسأله نمی شود، باید به سمت ریشه درخت برگشته و عمل جست وجو را در دیگر شاخه ها ادامه داد. این فرآیند را هرس كردن درخت فضای حالت می نامند.
به عنوان مثال، مسأله n وزیر، استفاده از الگوریتم مونت كارلو برای نخستین كارآیی یك الگوریتم عقبگرد، مسأله حاصل جمع زیرمجموعه ها، مسأله رنگ آمیز گراف، مسأله مدارهای هامیلتونی، مسأله كوله پشتی صفر و یك با استفاده از راهبرد عقبگرد، قابل حل هستند.
▪ الگوریتم شاخه وقید
روش شاخه و قید با ایجاد درختی از زیرمسأله ها با توجه به مسأله اولیه و پیمایش درخت بدون قاعده خاصی، دنبال جواب های مسأله می گردد. این روش شكل بهبود یافته ای از الگوریتم عقبگرد است كه در آن شیوه خاصی را برای ملاقات گره ها اعمال نمی كند و در هر گره برای امیدبخش بودن آن گره، قید یا عددی را محاسبه می كند و فقط برای مسائل بهینه سازی استفاده می شود. به عنوان مثال مسأله كوله پشتی صفر و یك، بهترین جست وجو با هرس كردن، ایجاد یك تور بهینه و محاسبه طول آن، مسأله فروشنده دوره گرد و استنباط با عكس العمل استفاده از روش شاخه و قید اجرا می شود.

الگوریتم دایجسترا

مطالب مشابه :

الگوریتم دایجسترا

دانلود پروژه رایگان الگوریتم دایجسترا با نرم افزار MATLAB

مسیریابی شبکه های کامپیوتری

الگوريتم دايكسترا (Dijkstra's algorithm) چيست؟

دانلود رایگان سورس الگوریتم دیکسترا به زبان ++C

الگوریتم‌های مسیریابی

انواع الگوریتم مسیریابی

انواع الگوریتم search

الگوریتم پریم چگونه کار می کند ؟