مسئله كوتاه ترين مسير يكي از مسائل معروف بهينه سازي مي باشد كه توسط دانشمندان زيادي مورد مطالعه قرار گرفته است. از جمله كاربردهاي اين مسئله در زمينه هاي ارتباطي و حمل و نقل است كه عموماً توسط الگوريتم ديجسترا (نشانه گذاري) حل مي شود. در اين مقاله دو حوزه علمي مجزاي الكترونيك و تحقيق در عمليات به هم ارتباط داده شده است تا الگوريتم جديدي جهت يافتن جواب بهينه مسئله كوتاه ترين مسير با استفاده از قوانين و شبكه هاي الكتريكي پديد آيد. الگوريتم پيشنهادي قادر به حل مسئله كوتاه ترين مسير در گرافهاي جهت دار و بدون جهت و همچنين حل مسائل طولاني ترين مسير در گراف هاي جهت دار مي باشد. در اين الگوريتم از شبكه هاي الكتريكي بدين طريق استفاده مي شود كه مقدار مقاومت الكتريكي هر شاخه معادل با وزن هر يال در مسئله كوتا هترين مسير فرض مي شود. سپس با استفاده از قوانين اهم و ولتاژ كيرشهف (KVL) جريان در هر حلقه محاسبه مي گردد. پس از آن، شاخه هايي كه داراي بيشترين جريان عبوري هستند مشخص شده كه در نتيجه طبق قانون اهم داراي كمترين مقاومت يا كمترين وزن در مسئله كوتاهترين مسير مي باشند. بدين ترتيب كوتاه ترين مسير در شبكه به دست مي آيد. از مزاياي اين الگوريتم هم گرايي سريع تر به جواب و زمان محاسبات كمتر نسبت به روشهاي مرسوم به خصوص در شبكه هايي با تعداد گره هاي زياد مي باشد. الگوريتم مزبور براي سه مثال تشريح گرديده است.
کلید واژگان :كوتاه ترين مسير، مدارهاي الكتريكي، قانون اهم، قانون KVL، مقاومت، جواب بهينه
ارزش ریالی : 600000 ریال
با پرداخت الکترونیک