|
|
|
|
الگوریتم مستطیل آبشاری و ماتریس انتقال در شبکه های کوتاه ترین مسیر بادور
|
|
|
|
|
|
|
|
نویسنده
|
عینی اصغر ,عشقی کورش
|
|
منبع
|
تحقيق در عمليات در كاربردهاي آن - دانشگاه آزاد اسلامي لاهيجان - 1396 - دوره : 14 - شماره : 4 - صفحه:67 -87
|
|
چکیده
|
مساله کوتاه ترین مسیر یکی از مسائل مشهور، بنیادی و پرطرفدار در نظریه گراف و شبکه است. در ادبیات این مساله، الگوریتم های کارای زیادی برای تعیین کوتاه ترین مسیر و مسافت بین هرزوج گره بر پایه جبر ماتریسی وجود دارد. در این مقاله، یک الگوریتم دقیق جدید با نام الگوریتم مستطیل آبشاری به کمک ساختار اصلی الگوریتم های قبلی و با بهبود روش های جدید، ارائه شده است. درالگوریتم ارائه شده سعی می شود تمام محاسبات و عملیات ریاضی الگوریتم در قالب تعدادی مستطیل پیاده سازی شود. الگوریتم مستطیل آبشاری، یک الگوریتم کاراست بطوری که روش اجرای ساده و زمان اجرای سریع دارد. بعلاوه، یک ماتریس جدید براساس ماتریس مسیر، با نام ماتریس انتقال تعریف شده که درتحلیل حساسیت و بهینه سازی مجدد شبکه های کوتاه ترین مسیر کاربرد دارد. درپایان، برای نشان دادن جزئیات اجرای الگوریتم های مستطیل آبشاری، فلوید وارشال، ماتریس تجدید نظرشده هو و ماتریس انتقال، یک مثال بصورت گام به گام حل شده است.
|
|
کلیدواژه
|
الگوریتم های شبکه کوتاه ترین مسیر با دور، الگوریتم آبشاری، روش ماتریس تجدید نظر شده، الگوریتم فلوید و وارشال، روش آبشاری تجدید نظر شده
|
|
آدرس
|
دانشگاه صنعتی شریف, دانشکده مهندسی صنایع, ایران, دانشگاه صنعتی شریف, دانشکده مهندسی صنایع, ایران
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cascade rectangle algorithm and transposition matrix in the cycled shortest path networks.
|
|
|
|
|
Authors
|
Aini Asghar ,Eshghi Kourosh
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|