بهبود الگوریتم های فلوید و دیکسترا با رویکرد شیءگرایی و محاسبات موازی

سال انتشار: 1393
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 552

فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

CSCCIT02_018

تاریخ نمایه سازی: 9 فروردین 1395

چکیده مقاله:

مسئله یافتن کوتاه ترین مسیر، یکی از مسائل معروف بهینه سازی گراف است؛ که امروزه در زمینه های مختلف ارتباطی، ریاضی، تجارت، حمل ونقل و غیره کاربرد دارد. سال ها است که این مسائل توسط متخصصان تحت الگوریتم هایی با پیچیدگی هایمختلف مورد ارزیابی و مطالعه قرارگرفته است و همواره سعی بر بهبود آن داشته اند. برای نیل به این هدف، از ساختمان داده های متفاوتی ازجمله صف، ماتریس، لیست های پیوندی، پشته ها و غیره برای پیاده سازی این الگوریتم ها استفاده شده است. همچنین در طول زمان، رویکرد ها و تکنولوژی های گوناگون برای افزایش کارایی و بهینه نمودن هرچه بیشتر این مسائل مطرح شده است.از مهم ترین الگوریتم های یافتن کوتاه ترین مسیر می توان به الگوریتم فلوید-مارشال 1 و دیکسترا 2 اشاره نمود. این مقاله با استفاده از قابلیت های شیءگرایی برای تشکیل گراف و همچنین محاسبات موازی 3 و تعریف واسط مناسب، به ارائه رویکردی مناسب برای افزایش کارایی الگوریتم های یادشده، که از مهم ترین الگوریتم های یافتن کوتاه ترین مسیر با دو روش متفاوت برنامه نویسی پویا وحریصانه هستند؛ پرداخته است. سپس به مقایسه و ارزیابی عملکرد مدل ارائه شده تحت گراف های متفاوت، با تعداد نودهای متفاوت در دو روش سری و موازی پرداخته شده است. نتایج به دست آمده از نرم افزار که در قالب نمودارهایی به صورت آماری ارائه گردید؛ نشان دهنده افزایش سرعت قابل ملاحظه ای است. در مدل ارائه شده همچنین امکان پویای تعریف نود در محاسبات موازی توسط کاربر در زمان کامپایل به وجود آمده است که نوعی بهبود در اجرای محاسبات موازی نیز به شمار می آید

کلیدواژه ها:

یافتن کوتاه ترین مسیر ، پیچیدگی زمانی ، الگوریتم فلوید و دیکسترا ، محاسبات موازی ، شی ءگرایی

نویسندگان

مریم مخبری

دانشجوی ارشد –دانشگاه علوم و تحقیقات -واحد یزد– گروه کامپیوتر

کمال میرزایی

استادیار- دانشگاه آزاد اسلامی- واحد میبد-گروه کامپیوتر

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • ستوده نیا، پارسا، یک برنامه، یک هدف، چندپردازنده، ماهنامه شبکه ...
  • ناطق الاسلام، سید مصطفی، خودکار کردن موازی‌سازی و دستیابی به ...
  • بچ زهی، نیک محمد، آموزش، Mpi دانشگاه علم و صنعت، ...
  • R. Neapolitan , and K. Naimipour, "Foundations of Algorithms", Fourth ...
  • T. Cormen, C. Leiserson, R. Rivest and C. Stein , ...
  • A. Grama, A. Gupta, G. Karypis and V. Kumar , ...
  • Gregor, Douglas, and Andrew Lumsdaine. "Design and implementation of a ...
  • B. Parhami, "Introduction to Parallel Processing: Algorithms and Architectures" _ ...
  • PACS Training Group, Introduction to MPI, Board of Trustees of ...
  • Hanuliak, P., & Hanuliak, J. , Complex performance modeling of ...
  • نمایش کامل مراجع