الگوریتم دایجسترا
الگوریتم دایجسترا
الگوریتم های حریصانه مشابه برنامه نویسی پویا، بیشتر برای حل مسائل بهینه سازی به كار می روند. با این اختلاف كه در برنامه سازی پویا از یك رابطه بازگشتی برای حل زیرمسأله ها استفاده می كنند. در روش حریصانه، تقسیم مسأله ها به زیر مسأله ها انجام نمی گیرد و روش تكرارشونده را به كار می برند.در روش حریصانه در هر لحظه، با توجه به عناصر داده ای مفروض، عنصری را كه دارای ویژگی بهترین یا بهینه است (مانند كوتاه ترین مسیر، بالاترین ارزش، كمترین سرمایه گذاری، بیشترین سود و ...) انتخاب می كنند بدون این كه انتخاب های قبلی ما بعدی را در نظر بگیرد ولی انتخاب های بهینه محلی همواره منجر به راه حل بهینه سراسری نمی شود. این روش انتخاب، منجر به ارائه یك الگوریتم ساده و كارآمد می شود.تعیین درخت های پوشالی مینیمم با استفاده از الگوریتم های پرایم، كروسكال محاسبه كوتاه ترین مسیر تك منبع با كاربرد الگوریتم دایجسترا ، مسأله زمان بندی مانند بهینه سازی زمان انتظار و سرویس به كاربران برای دسترسی به دیسك گردان ها در یك شبكه رایانه ای، تعیین حداكثر بهره برای مشتریان در یك زمان معین و مسأله كوله پشتی (كسری، صفرو یك) با استفاده از روش حریصانه قابل اجرا هستند.الگوریتم عقبگرد ▪ الگوریتم عقبگرد، برای یافتن جواب مسأله ای با فضای جست وجو به طور گسترده ای به كار می رود و از آن به عنوان حالت اصلاح شده جست وجوی عمقی یك درخت نام می برند. در این روش، منظور از عقبگرد، پیدا كردن راه حل مسأله از طریق جست وجوی عمقی در درخت فضای حالت برای یافتن گره های امید بخش است. در صورتی كه موقع پیمایش درخت به یك گروه غیرامیدبخش برخورد كند كه منجر یه یافتن جواب مسأله نمی شود، باید به سمت ریشه درخت برگشته و عمل جست وجو را در دیگر شاخه ها ادامه داد. این فرآیند را هرس كردن درخت فضای حالت می نامند.به عنوان مثال، مسأله n وزیر، استفاده از الگوریتم مونت كارلو برای نخستین كارآیی یك الگوریتم عقبگرد، مسأله حاصل جمع زیرمجموعه ها، مسأله رنگ آمیز گراف، مسأله مدارهای هامیلتونی، مسأله كوله پشتی صفر و یك با استفاده از راهبرد عقبگرد، قابل حل هستند.▪ الگوریتم شاخه وقید روش شاخه و قید با ایجاد درختی از زیرمسأله ها با توجه به مسأله اولیه و پیمایش درخت بدون قاعده خاصی، دنبال جواب های مسأله می گردد. این روش شكل بهبود یافته ای از الگوریتم عقبگرد است كه در آن شیوه خاصی را برای ملاقات گره ها اعمال نمی كند و در هر گره برای امیدبخش بودن آن گره، قید یا عددی را محاسبه می كند و فقط برای مسائل بهینه سازی استفاده می شود. به عنوان مثال مسأله كوله پشتی صفر و یك، بهترین جست وجو با هرس كردن، ایجاد ...
دانلود پروژه رایگان الگوریتم دایجسترا با نرم افزار MATLAB
دانلود پروژه رایگان الگوریتم دایجسترا با نرم افزار MATLABلینک دانلودعکس 1عکس 2عکس 3
مسیریابی شبکه های کامپیوتری
انواع مسیریابی الگوریتم های مسیریابی در شبکه ادهاک انواع پروتکل های مسیر یابی در شبکه های ad- hocانواع پروتکل های مسیر یابی در شبکه های ad- hoc در شبکه های Mobile Ad hoc عمل مسیر یابی به دلایلی همچون متحرک بودن و نبود سیستم کنترلی متمرکز از اهمیت بالایی بر خوردار بوده و مطالعه و بررسی بیشتری را می طلبد . قبل از بررسی این پروتکل ها باید توجه کنیم که هدف از الگوریتم ها و استراتژی های مسیریابی جدید کاهش سربار ناشی از مسیریابی در کل شبکه , یافتن مسیرهای کوتاه تر و انتقال صحیح داده ها و اطلاعات می باشد.تقسیم بندی های مختلفی در مورد پروتکل های مسیر یابی شبکه های Mobile ad hoc وجود دارد که از این میان می توان به 2 نوع زیر اشاره کرد:تقسیم بندی اول : Pro active(Table driven) Reactive(On demand) Hybrid(Table driven & On demand)هر کدام از این انواع خود شامل پروتکل هایی هستند که در زیر اشاره شده است:تقسیم بندی دوم: Flat routing protocols Hierarchal routing approaches GPS Augmented geographical routing approachesدر اینجا به توضیحاتی در مورد پروتکل های تقسیم بندی اول می پردازیم:1.Table driven Pro active - در پروتکلهای از این نوع , node ها مدام در حال جستجوی اطلاعات مسیر یابی جدید درون شبکه هستند به صورتی که حتی با تغییر مکان node ها در صورت نیاز به راحتی می توان مسیر مناسبی را یافته و برای ارسال و دریافت اطلاعات بین هر دو node ی استفاده کرد . به عبارت بهتر می توان گفت که در این شبکه ها مسیر ها از قبل موجود هستند.و به محض آنکه node ی اقدام به ارسال داده به node دیگری کند قادر خواهد بود مسیر موجود را از روی اطلاعات از قبل جمع آوری شده شناسایی کرده و مورد استفاده قرار دهد و لذا تاخیری در این مورد متوجه node نیست. DSDV این پروتکل بر مبنای الگوریتم کلاسیک Bellman-Ford بنا شده است.در این حالت هر node لیستی از تمام مقصد هاو نیز تعداد hop ها تا هر مقصد را تهیه می کند.هر مدخل لیست با یک عدد شماره گزاری شده است . برای کم کردن حجم ترافیک ناشی از به روز رسانی مسیر ها در شبکه از incremental packets استفاده می شود.تنها مزیت این پروتکل اجتناب از به وجود آمدن حلقه های مسیر یابی در شبکه های شامل مسیر یاب های متحرک است.بدین ترتیب اطلاعات مسیر ها همواره بدون توجه به این که آیا node در حال حاضر نیاز به استفاده از مسیر دارد یا نه فراهم هستند. معایب پروتکل DSDV نیازمند پارامترهایی از قبیل بازه ی زمانی به روز رسانی اطلاعات و تعداد به روز رسانی های مورد نیاز می باشد. WRP این پروتکل بر مبنای الگوریتم path-finding بنا شده با این استثنا که مشکل count-to-infinity این الگوریتم را برطرف کرده است. در این پروتکل هر node , 4 جدول تهیه می کند جدول فاصله , جدول مسیر یابی , جدول link-cost و جدولی در مورد پیامهایی که ...
الگوريتم دايكسترا (Dijkstra's algorithm) چيست؟
الگوريتم دايكسترا (Dijkstra's algorithm) چيست؟ در نظریه گراف، الگوریتمدایكسترا به انگلیسی : (Dijkstra's algorithm) یکی از الگوریتم های پیمایش گرافاست که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دِیْکْسْترادر سال 1959ارایه شد. اين الگوريتم به عنوان الگوريتم حريصانه و كوتاه ترين مسير تك منبع (Single-Source Shortest Path) نيز شناخته شده است. این الگوریتم یکی از الگوریتم‌های پیمایش گرافاست که مسئله کوتاه ترین مسیراز مبدأ واحد را برای گراف‌های وزن‌داریکه یال با وزن منفی ندارند، حل می کند و در نهایت با ایجاد درخت کوتاه ترین مسیر، کوتاه ترین مسیر از مبدأ به همه رأس‌هایگرافرا به دست می دهد. همچنین می توان از این الگوریتم برای پیدا کردن کوتاه ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیدا شدن کوتاه ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.
دانلود رایگان سورس الگوریتم دیکسترا به زبان ++C
دانلود سورس الگوریتم دیکسترا به زبان ++Cاین الگوریتم یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌هایگراف را به دست می‌دهد.------------------------------------------------------------------------------- لينك دانلودرمز فایل:www.papro.blogfa.com-------------------------------------------------------------------------------روند الگوریتم دیکسترا مطابق زیر می باشد : 1- انتخاب راس مبدا 2- مجموعه ی S ، شامل رئوس گراف ، معین می شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه رئوسی که کوتاه ترین مسیر به آن ها یافت شده است را در بر می گیرد. 3- راس مبدا با اندیس صفر را در داخل S قرار می دهد. 4- برای رئوس خارج از S ، اندیسی معادل ، طول یال + اندیس راس قبلی ، در نظر می گیرد . اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل ، می باشد. 5- از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعه ی S اضافه می گردد. 6- این کار را دوباره از مرحله ی 4 ادامه داده تا راس مقصد وارد مجموعه ی S شود. در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهنده ی مسافت بین مبدا و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدا و مقصد موجود نمی باشد. همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهنده ی راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود.
الگوریتم‌های مسیریابی
در شبکه‌های کوچک، و در نقاطی که انتقال اطلاعات معمولا مستقیم است، مسیریابی چندان جدی گرفته نمی‌شود. اما هنگامی که شبکه‌ها از حالت‌های ایستگاه‌های کاری خارج می‌شوند و کمی پیچیده‌تر می‌شوند، در این حالت، مسیریابی و انتخاب مسیر بهینه برای ارسال بسته‌های اطلاعاتی، به یک امر مهم بدل می‌شود. در شبکه‌های بزرگ، دستگاه‌هایی به‌عنوان مسیریاب (1) وجود دارند که عمل مسیریابی را انجام می‌دهند. الگوریتم مسیریابی‌ای مناسب است که 6 ویژگی زیر را داشته باشد: صحت عملکرد(2) ، سادگی(3)، قابلیت اطمینان(4)، پایداری(5)، عدالت(6) و بهینگی(7). بدیهی است که الگوریتمی بهتر است که صحت عملکرد بالایی داشته باشد و در عین حال ساده باشد، اما چه الگوریتمی قابلیت اتکای خوبی دارد؟ الگوریتمی مناسب است که در گذشت زمان، با تغییر نرم‌افزارها و سخت‌افزارهای شبکه و تغییر پروتکل‌ها، همچنان مسیریابی درستی ارائه دهد. همچنین مهم است که بعد از یک مدت زمان خاص، الگوریتم مسیریابی به حالتی پایدار برسد و همزمان با آن، مسیریابی بهینه‌ای داشته باشد و در ارسال بسته‌ها عدالت را رعایت کند. الگوریتم کوتاه‌ترین مسیر ساده‌ترین روش مسیریابی، روش کوتاه‌ترین مسیر است. هدف اصلی از این الگوریتم، این است که گراف زیرشبکه را طوری تشکیل بدهیم که در آن هر گره را یک مسیریاب فرض کنیم و هر یال را یک خط ارتباطی میان دو مسیریاب. در این حالت، هر یال یک وزن خواهد داشت و با توجه به الگوریتم کوتاه‌ترین مسیر دایجسترا(8) می‌توان کوتاه‌ترین مسیر ممکن را محاسبه کرد. الگوریتم سیل‌آسا در این روش، هر بسته ورودی که به یک مسیریاب می‌رسد، از تمام کانال‌های خروجی مسیریاب خارج می‌شود. بدین‌ترتیب تعداد زیادی بسته تکراری وجود خواهد داشت و عملا میزان آن بی‌نهایت خواهد بود. بنابراین باید برای خاتمه این تعداد بسته‌ها راهکاری اندیشید. راهکارهای پیشنهادی برای این روش، استفاده از یک شمارنده گام است. بدین صورت که در سرآیند(9) هر بسته یک شمارنده بگذاریم و در هر گام یک شماره از آن کم کنیم تا به صفر برسد و بسته حذف شود. در این صورت مبدا باید طول شبکه را بداند و در بدترین حالت، طول شبکه را طولانی‌ترین فاصله در نظر بگیرد. یک روش دیگر، استفاده از حالتی نیمه‌منطقی است. مسیریاب در این روش، بسته را به تمام کانال‌های خروجی نمی‌فرستد. بلکه به کانال‌هایی می‌فرستد که احتمال رسیدن آنها به مقصد وجود دارند. در این صورت اگر بسته‌ای به سمت غرب بخواهد برود، نبایستی از کانال‌های شرقی مسیریاب استفاده کرد، مگر اینکه مسیریاب از ساختار شبکه مطلع ...
انواع الگوریتم مسیریابی
بدیهی است که الگوریتمی بهتر است که صحت عملکرد بالایی داشته باشد و در عین حال ساده باشد، اما چه الگوریتمی قابلیت اتکای خوبی دارد؟ الگوریتمی مناسب است که در گذشت زمان، با تغییر نرم‌افزارها و سخت‌افزارهای شبکه و تغییر پروتکل‌ها، همچنان مسیریابی درستی ارائه دهد. همچنین مهم است که بعد از یک مدت زمان خاص، الگوریتم مسیریابی به حالتی پایدار برسد و همزمان با آن، مسیریابی بهینه‌ای داشته باشد و در ارسال بسته‌ها عدالت را رعایت کند. الگوریتم کوتاه‌ترین مسیر ساده‌ترین روش مسیریابی، روش کوتاه‌ترین مسیر است. هدف اصلی از این الگوریتم، این است که گراف زیرشبکه را طوری تشکیل بدهیم که در آن هر گره را یک مسیریاب فرض کنیم و هر یال را یک خط ارتباطی میان دو مسیریاب. در این حالت، هر یال یک وزن خواهد داشت و با توجه به الگوریتم کوتاه‌ترین مسیر دایجسترا(8) می‌توان کوتاه‌ترین مسیر ممکن را محاسبه کرد. الگوریتم سیل‌آسا در این روش، هر بسته ورودی که به یک مسیریاب می‌رسد، از تمام کانال‌های خروجی مسیریاب خارج می‌شود. بدین‌ترتیب تعداد زیادی بسته تکراری وجود خواهد داشت و عملا میزان آن بی‌نهایت خواهد بود. بنابراین باید برای خاتمه این تعداد بسته‌ها راهکاری اندیشید. راهکارهای پیشنهادی برای این روش، استفاده از یک شمارنده گام است. بدین صورت که در سرآیند(9) هر بسته یک شمارنده بگذاریم و در هر گام یک شماره از آن کم کنیم تا به صفر برسد و بسته حذف شود. در این صورت مبدا باید طول شبکه را بداند و در بدترین حالت، طول شبکه را طولانی‌ترین فاصله در نظر بگیرد. یک روش دیگر، استفاده از حالتی نیمه‌منطقی است. مسیریاب در این روش، بسته را به تمام کانال‌های خروجی نمی‌فرستد. بلکه به کانال‌هایی می‌فرستد که احتمال رسیدن آنها به مقصد وجود دارند. در این صورت اگر بسته‌ای به سمت غرب بخواهد برود، نبایستی از کانال‌های شرقی مسیریاب استفاده کرد، مگر اینکه مسیریاب از ساختار شبکه مطلع باشد و بداند که این کانال‌ها به کجا منتهی می‌شوند. الگوریتم سیل‌آسا به جز چند مورد خاص، از جمله سیستم‌های توزیعی که عملکردهای موازی در آنها نیاز است، کاربرد علمی دیگری ندارد. الگوریتم بردار فاصله در این روش، مسیریاب‌ها در خود جدولی (برداری) ذخیره می‌کنند با عنوان بردار فاصله که در آن بهترین فاصله تا هر مسیریاب دیگر در شبکه را ذخیره می‌کنند. در این صورت، تصمیم‌گیری بهتری هنگام مسیریابی اتخاذ می‌شود. این جدول‌ها با اطلاعات مسیریاب‌های همسایه به‌روز می‌شود. هر یک از عناصر این جدول‌ها یک درایه دوبخشی دارند که یکی از آنها نشانگر خط خروجی مناسب برای ...
انواع الگوریتم search
انواع الگوریتم search در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مساله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه حل‌های ممکن، یک راه حل برای آن مساله برمی گرداند.مجموعهٔ راه حل‌های ممکن برای یک مساله را فضای جستجو می‌نامند.بعضی از الگوریتم‌ها که با عنوان الگوریتم‌های ناآگاهانه شناخته می‌شوند الگوریتم‌هایی هستند که از متدهای ساده‌ای برای جستجوی فضای نمونه استفاده می‌کنند.در حالی که الگوریتم‌های آگاهانه با استفاده روش‌هایی مبتنی بر دانش در بارهٔ ساختار فضای جستجو، می‌کوشند تا زمان جستجو را کاهش دهند. رده بندی در کتاب راسل این الگوریتم‌ها به شکل زیر رده بندی شده‌اند. · الگوریتم‌های ناآگاهانه · الگوریتم نخست-پهنا · الگوریتم نخست-ژرفا · الگوریتم‌های آگاهانه · الگوریتم نخست-بهترین · الگوریتم مکاشفه‌ای جستجوی ناآگاهانه یک الگوریتم جستجوی ناآگاهانه الگوریتمی است که به ماهیت مساله کاری ندارد.از این رو می‌توانند به طور عمومی طراحی شوند و از همان طراحی برای محدودهٔ عظیمی از مسائل استفاده کنند، این امر نیاز به طراحی انتزاعی دارد. از جمله مشکلاتی که این چنین الگوریتم‌هایی دارند این است که اغلب فضای جستجو بسیار بزرگ است و نیازمند زمان زیادی (حتی برای نمونه‌های کوچک) می‌باشد.از این رو برای بالا بردن سرعت پردازش غالبا از الگوریتم‌های آگاهانه استفاده می‌کنند. جستجوی لیست الگوریتم‌های جستجوی لیست شاید از ابتدایی ترین انواع الگوریتم‌های جستجو باشند.هدف آن پیدا کردن یک عنصر از مجموعه‌ای از کلید هاست(ممکن است شامل اطلاعات دیگری مرتبط با آن کلید نیز باشد). ساده ترین این الگوریتم‌ها، الگوریتم جستجوی ترتیبی است که هر عنصر از لیست را با عنصر مورد نظر مقایسه می‌کند. جستجوی درختی الگوریتم‌های جستجوی درختی، قلب شیوه‌های جستجو برای داده‌های ساخت یافته هستند.مبنای اصلی جستجوی درختی، گره‌هایی است که از یک ساختمان داده گرفته شده‌اند. هر عنصر که بخواهد اضافه شود با داده‌های موجود در گره‌های درخت مقایسه می‌شود و به ساختار درخت اضافه می‌شود.با تغییر ترتیب داده‌ها و قرار دادن آنها در درخت، درخت با شیوه‌های مختلفی جستجو می‌شود. برای مثال سطح به سطح (جستجوی نخست-پهنا) یا پیمایش معکوس درخت (جستجوی نخست-ژرفا).از مثال‌های دیگر جستجوهای درختی می‌توان به جستجوی عمقی تکرار شونده،جستجوی عمقی محدود شده، جستجوی دوطرفه، جستجوی هزینه یکنواخت اشاره کرد. جستجوی گراف بسیاری ...
الگوریتم پریم چگونه کار می کند ؟
این الگوریتم جز الگوریتم های حریصانه است . همان طور که از نامش پیداست این الگوریتم ها حرص می زنند . این الگوریتم به دنبال یک درخت پوشاست با حداقل هزینه است . یعنی همه گره ها به هم وصل باشند با کمترین هزینه . برای درک بهتر این الگوریتم ، گراف زیر را در نظر بگیرد . می خواهیم درخت پوشا با کمترین هزینه این گراف را بدست آوریم . قبل از بیان الگوریتم پریم یکی از راه های بدست آوردن درخت پوشا کمینه از یک گراف این است که تمام درخت های پوشای گراف را بدست آوریم و بعد آن هایی که کمترین هزینه را دارند را انتخاب کنیم که بسیار هزینه بر است .(تعداد درخت پوشا در یک گراف کامل 2n-1-1 است . ) اما مثال : با الگوریتم پریم می خواهیم درخت پوشای کمینه کراف زیر را بدست آوریم . در قدم اول یک گره را به طور اختیاری انتخاب می کنیم . ما در این مثال گره صفر را انتخاب می کنیم. در قدم دوم باید گره هایی که به طور مستقیم به گره صفر وصل شده اند را بررسی کنیم و گره ای که کمترین هزینه را دارد را انتخاب کنیم . همان طور که در شکل زیر مشاهده می شود ، گره صفر به گره 1 با هزینه 4 و به گره 7 با هزینه 8 متصل است . پریم از آن جایی که الگوریتمی حریصانه است کمترین هزینه را انتخاب می کند . پس گره 1 با هزینه 4 انتخاب می شود . حال دوباره باید نزدیک ترین گره هایی که به طور مستقیم به گره های انتخاب شده متصل هستند را بررسی کنیم. همانطور که در شکل زیر مشاهده می کنید گره 2 با هزینه 8 به گره 1 متصل است و گره 7 با هزینه 8 به گره صفر متصل است . حال کدام یک انتخاب می شود ؟ وقتی هر دو یک هزینه دارند ! مهم نیست یک گره را به دلخواه انتخاب کنید . ( علت دلخواهی بودن چیست ؟ علت این است که برای یک گراف درخت پوشای کمینه زیادی وجود دارد . یک گراف فقط یک درخت پوشای کمینه ندارد ) نکته : از گره 1 به گره 7 هم یک مسیر وجود دارد و علت این که بررسی نمی شود این است که ایجاد حلقه می کند . پس در تصاویر ما یال هایی که ایجاد حلقه می کنند را ذکر نکردیم . ما گره هفت را انتخاب کردیم . پس گره هایی که تاکنون حل شده اند : {0,1,7 } . حال دوباره باید گره هایی که به طور مستقیم به گره های حل شده وصل هستند را بررسی کنیم . همان طور که ملاحظه می شود : گره 2 با هزینه 8 به گره 1 گره 6 با هزینه 1 به گره 7 گره 8 با هزینه 7 به گره 7 گره 6 با هزینه یک انتخاب می شود . پس گره های حل شده عبارتند از : {0,1,7,6} . حال دوباره باید گره هایی که به طور مستقیم به گره های حل شده وصل هستند را بررسی کنیم . به گره 1 : گره 2 با هزینه 8 وصل است. یادآوری نکته بالا : گره های وصل شده به هفت را بررسی نمی کنیم چون ایجا حلقه می کنند . به گره 6 : گره 8 با هزینه 6 و گره 5 با هزینه 2 وصل است . گره 5 با ...