الگوریتم های مسیریابی – بخش اول (الگوریتم دیکسترا)

مقدمه

من جمله مسائل اصلی در تئوری شبکه های هندسی در جی.آی.اس مسئله مسیریابی یعنی یافتن کوتاهنرین مسیر بین دو نقطه است. در سال های اخیر، با استفاده از متدهای هوش مصنوعی روشهای مدرنی برای پیدا کردن کوتاه ترین مسیر ارایه شده است. در گذشته برای حل این مسیله الگوریتم هایی مانند دیکسترا، A*، بلمن فورد، فلوید وارشال، جانسون و … ارایه شده است. این الگوریتم ها از روش های کلاسیک برای پیدا کردن کوتاه ترین مسیر می باشند. در سال های اخیر استفاده از روش های هوش مصنوعی مانند الگوریتم های ژنتیک در تعیین بهترین مسیر اهمیت خاصی یافته است.

در این پست و پست های بعدی الگوریتم های دیکسترا، A* ، بلمن فورد و فلوید وارشال به عنوان روش های کلاسیک و نمونه ای از الگوریتم های ژنتیک به اختصار شرح داده خواهد شد.

الگوریتم مسیریابی دیکسترا (Dijkstra)

این الگوریتم در سال 1959 توسط یک دانشمند هلندی ارایه شد. این الگوریتم بهترین مسیر را بین دو راس در یک گراف پیدا می کند. بهترین مسیر می تواند کوتاه ترین ، ارزان ترین یا سریع ترین مسیر در نظر گرفته شود که بستگی به نحوه ی انتخاب طول یال های گراف دارد.

روند الگوریتم دیکسترا مطابق زیر می باشد :

  1. انتخاب راس مبدا
  2. مجموعه ی S ، شامل ریوس گراف ، معین می شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه ریوسی که کوتاه ترین مسیر به آن ها یافت شده است را در بر می گیرد.
  3. راس مبدا با اندیس صفر را در داخل S قرار می دهد.
  4. برای رئوس خارج از S ، اندیسی معادل ، طول یال + اندیس راس قبلی ، در نظر می گیرد . اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل ، می باشد.
  5. از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعه ی S اضافه می گردد.
  6. این کار را دوباره از مرحله ی 4 ادامه داده تا راس مقصد وارد مجموعه ی S شود.

در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهنده ی مسافت بین مبدا و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدا و مقصد موجود نمی باشد.

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

به عنوان مثال، گراف زیر را در نظر بگیرید:

 

1 thumb الگوریتم های مسیریابی   بخش اول (الگوریتم دیکسترا)

 

راس A را به عنوان راس مبدا در نظر بگیرید. روند الگوریتم به صورت زیر است:

  1. A با اندیس صفر وارد مجموعه ی S می شود. S={ A }
  2. B اندیس 14 ، D اندیس 22 و E اندیس 4 خواهند داشت. S = { A , E }
  3. B اندیس 14 ، D اندیس 16 و F اندیس 14 خواهند داشت. از بین B و F به اختیار یکی را انتخاب می کنیم. S = { A , E , F}
  4. اندیس ها هیچ تغییری نمی کنند. S = { A , E , F , B }
  5. اندیس ها مانند قبل بوده فقط راس G اندیس 17 می گیرد. S = { A , E , F , B , D }
  6. در این مرحله، اندیس ها هیچ تغییری نمی کنند .S = { A , E , F , B , D , G }
  7. عملیات متوقف شده زیرا هیچ راس با اندیسی خارج از S قرار نگرفته.

هم اکنون، اندیس های نقاط نشان دهنده ی کوتاه ترین فاصله از راس مبدا به نقاط گراف می باشد. توجه کنید که به نقاط بدون اندیس ( مانند C ) هیچ مسیری از راس مبدا وجود ندارد.

2 topodin, Это: Какими ссылками лучше продвигаться Сколько ссылок безопасно покупать каждый месяц Сколько ссылок нужно для топа Сколько раз использовать анкоры Какие системы использовать для продвижения ссылками Рассмотрим каждый из вышеперечисленных вопросов более подробно

مطالب مرتبط

2 نظر

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *