مشاهده مشخصات مقاله
يک الگوريتم توزيع شده کارا براي يافتن کوتاه‌ترين مسيرهاي تک مبدأ تصادفي با قابليت پياده سازي در شبکه‌هاي واقعي
|
Authors |
-
مهدی قربعلی پور
-
امیدرضا معروضی
|
|
Conference |
بیست و چهارمین کنفرانس ملی سالانه انجمن کامپیوتر ایران |
|
Abstract |
در اين مقاله براي اولين بار يک الگوريتم توزيع شده براي يافتن کوتاه‌ترين مسيرهاي تک مبدأ تصادفي ارائه شده است. اين الگوريتم که مبتني بر آتاماتاي يادگير است مي‌تواند کوتاه‌ترين مسيرها از يک مبدأ به ساير گره‌ها را در يک گراف تصادفي بيابد. گراف تصادفي، گرافي است که در آن هزينه منتسب به لينک‌ها، متغيرهاي تصادفي با توزيع از پيش ناشناخته مي‌باشد. کوتاه‌ترين مسير بين دو گره مسيري با کمترين طول مورد انتظار تعريف مي‌شود. در الگوريتم پيشنهادي ابتدا هر گره مجهز به يک آتاماتون يادگير مي‌شود و سپس يک الگوريتم محلي در هر گره به صورت تکراري در فواصل ثابت زماني تا همگرا شدن آتاماتون يادگير اجرا مي‌شود. در هر تکرار الگوريتم محلي، آتاماتون يادگير فعال شده و لينکي که بايد از آن نمونه‌گيري شود را مشخص مي‌کند. اين روش نمونه‌گيري منجر به کاهش نمونه‌گيري‌هاي زائد و در نتيجه موجب سرعت اجراي الگوريتم مي‌شود. نتايج آزمايشي حاکي از برتري الگوريتم پيشنهادي از نظر سرعت و دقت نسبت به الگوريتم‌هاي ارائه شده قبلي (که غير توزيع شده‌اند) مي‌باشد. به دليل توزيع شدگي الگوريتم، قابليت پياده سازي آن در شبکه‌هاي واقعي امکان پذير است. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}