advertise laitec sharif univercity
دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

10000 تومان
سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

10000 تومان
دانلود مقاله ای در مورد الگوریتم  کرم شب تاب FireFly در هوش مصنوعی

دانلود مقاله ای در مورد الگوریتم کرم شب تاب FireFly در هوش مصنوعی

10000 تومان
دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

28000 تومان
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

148000 تومان

الگوریتم مسیر یابی کوتاه ترین مسیر در شبکه

برای انتخاب مسیری بین دو مسیر یاب معین ، الگوریتم ، کوتاه ترین مسیر بین آنها را درگراف می یابد ، درک این الگوریتم آسان است .
الگوریتم مسیر یابی کوتاه ترین مسیر در شبکه

الگوریتم مسیر یابی کوتاه ترین مسیر در شبکه

 

یک راه اندازه گیری طول مسیر ، تعداد جهش ها است، معیار دیگر فاصله جغرافیایی به کیلومتر است .

علاوه بر جهش ها و فاصله فیزیکی ، معیار های دیگری نیز قابل استفاده اند . به عنوان مثال ، هر یال می تواند با میانگین تاخیر صف بندی و انتقال برای بعضی از بسته های آزمایشی ، برچسب گذاری شود . با این برچسب گذاری ، کوتاه ترین مسیر (به جای مسیری با کمترین یال یا فاصله)، سریع ترین مسیر است .

در حالت کلی ، برچسب های یال ها باید به صورت تابعی از فاصله ، پهنای باند ، میانگین ترافیک ، هزینه ارتباط ، میانگین طول صف ، تاخیر اندازه گیری شده ، و سایر عوامل محاسبه شود . با تغییر تابع وزنی ، الگوریتم ، "کوتاه ترین "مسیر وزن دار را براساس هر یک از معیار های فوق یا ترکیبی از آن ها محاسبه می کند .

الگوریتم های متعددی برای محاسبه الگوریتم مسیر یابی کوتاه ترین مسیر در شبکه بین دو گره گرا ف شناسایی شده اند .یکی از این الگوریتم ها به دیکسترا(1995)نسبت داده می شود . هر گره دارای برچسب هایی (در پرانتز)است که فاصله آن تا گره منبع ، از طریق بهترین مسیر شناخته شده است . در آغاز ، هیچ مسیری شناخته شده نیست ، لذا تمام گره ها دارای برچسب بی نهایت هستند . با ادامه اجرای الگوریتم وپیدا شدن مسیر ها ، امکان دارد برچسب ها تغییر کنند تا مسیر های بهتری را منعکس نمایند . برچسب ممکن است موقتی یا دائمی باشد . در آغاز ، تمام برچسب ها موقتی اند . وقتی مشخص شد که برچسبی کوتاه ترین مسیر بین منبع به آن گره را نمایش می دهد ، دائمی می شود و از آن پس تغییر نمی کند .

برای اینکه مشخص شود الگوریتم برچسب گذاری  چگونه کار می کند ، گراف وزن دار بدون جهت شکل اول را در نظر بگیرید ، که وزن ها ، مثلا فاصله را نشان می دهند . می خواهیم کوتاه ترین مسیر ازA بهDرا بیابیم . با علامت گذاری گره Aبه عنوان گره ثابت به صورت دایره پر نشان داده شده است ، شروع می کنیم . سپس به نوبت ، تمام گره های همجوار A(گره کاری)را تست می کنیم ، هر کدام را با فاصله آن بهA ، مجددا برچسب می دهیم . هر وقت گره ای مجددا برچسب دهی شد ، آن را با گره ای که کار از آن جا آغاز شد ، برچسب می دهیم ؛ به این ترتیب میتوانیم مسیر نهایی را بازسازی کنیم . با بررسی تمام گره های همجوار A ، تمام گره هایی را که در کل گراف به طور موقت برچسب دهی شدند بررسی می کنیم و گره ای که دارای کوچک ترین برچسب است ، دائمی می کنیم (شکل اول  (ب)) . این گره به عنوان گره کاری جدید انتخاب می شود .

اکنون ازB شروع می کنیم و تمام گره های همجوار آن را مورد بررسی قرار می دهیم . اگر مجموع برچسب در B و فاصله B تا گره ای که باید در نظر گرفته شود کمتر از برچسب موجود در آن گره باشد ، کوتاه ترین مسیر پیدا شده ، این گره مجددا برچسب گذاری می شود .

پس از اینکه تمام گره های همجوار گره کاری بررسی شدند و گره های موقتی تغییر کردند ، کل گراف مورد جستجو قرار می گیرد تا گره ای موقتی با کمترین مقدار برچسب پیدا شود . این گره دائمی می شود و برای سیکل بعدی به عنوان گره کاری انتخاب می شود . شکل اول پنج مرحله  اول الگوریتم را نشان می دهد .

برای پی بردن به عملکرد الگوریتم ، شکل اول (ج) را ببینید . در این شکل ، E دائمی است ، فرض کنید مسیر AXYZA کوتاه تر از ABE باشد . دو امکان وجود دارد : یا گره Z به عنوان گره دائمی منظور شده ، یا نشده است . اگر دائمی باشد ، E تا کنون بررسی شده است (در سیکلی بعد از آن که Z دائمی شد) ، لذا AXYZE از دید ما خاج نبوده است ونمی تواند مسیر کوتاه تری باشد .

اکنون حالتی را در نظر بگیرید که هنوز برچسب Z موقتی باشد . برچسب موجود در Zبزرگ تر یا مساوی برچسب درE است ، که دراین حالت AXYZE نسبت به ABE مسیر کوتاه تری نیست ؛ یا کمتر از E است که در این حالت  Z وE  نمی توانند دائمی گردند وE ازZ  مورد جستجو قرار می گیرد .

این الگوریتم در شکل دوم آمده است . متغیر های عمومی n وdist گراف را توصیف می کنند و قبل از فراخوانی shortest-path مقدار می گیرد . تنها تفاوت بین برنامه و الگوریتمی که تشریح شد این است که کوتاه ترین مسیر ، نه از گره منبع sبلکه از گره پایانی t محاسبه شده است . چون کوتاه ترین مسیر از tبهs در گراف بدون جهت ، مانند کوتاه ترین مسیر از sبهt است ، مهم نیست که از کدام طرف شروع کنیم (مگر اینکه ، کوتاه ترین مسیر متعددی وجود داشته باشد ، که در آن حالت ، جستجوی معکوس ، مسیر دیگری را انتخاب می نماید .) دلیل جستجوی معکوس این است که هرگره با گره قبلی خود (به جای گره بعدی) برچسب گذاری می شود . هنگام کپی کردن مسیر نهایی در متغیر خروجی path ، مسیر ، معکوس می شود . با معکوس کردن جستجو ،این دو اثر خنثی می شود و پاسخ به ترتیب درستی تولید می گردد . 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
دانلود الگوریتم کوتاه ترین مسیر در شبکهshortest-path Algorithm on networkنحوه کار الگوریتم مسیر کوتاه در شبکهمسیر یابی کوتاه ترین مسیر در شبکه چگونه استآموزش کار با الگوریتم کوتاه ترین مسیرالگوریتم shortest-path در شبکهالگوریتم مسیر یابی کوتاه ترین مسیر در شبکهپیاده سازی کوتاه ترین مسیر در شبکهتبلیغات ارزان سایت آموزش برنامه نویسیتبلیغات مخصوص طراحان وب سایتتبلیغات در سایت برنامه نویسیتبلیغات اینترنتی برای برنامه نویساندر آغوش مینیمالیسممنوی همبرگر با سه خط افقی که روی یکدیگر قرار گرفته اند نشانه چیست؟ سوئیچ به یک ستون واحدتبدیل متن ساده به وبلاگ و سایت های پویا با React.jsکتابخانه sass برای استفاده آسان تر از آنکتابخانه سطح بالا برای اتوماتیک سازی اعمال مرورگر لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php