بهبود الگوریتم های فلوید و دیکسترا با رویکرد شیءگرایی و محاسبات موازی
- سال انتشار: 1393
- محل انتشار: دومین کنفرانس دانش پژوهان کامپیوتر و فناوری اطلاعات
- کد COI اختصاصی: CSCCIT02_018
- زبان مقاله: فارسی
- تعداد مشاهده: 569
نویسندگان
دانشجوی ارشد –دانشگاه علوم و تحقیقات -واحد یزد– گروه کامپیوتر
استادیار- دانشگاه آزاد اسلامی- واحد میبد-گروه کامپیوتر
چکیده
مسئله یافتن کوتاه ترین مسیر، یکی از مسائل معروف بهینه سازی گراف است؛ که امروزه در زمینه های مختلف ارتباطی، ریاضی، تجارت، حمل ونقل و غیره کاربرد دارد. سال ها است که این مسائل توسط متخصصان تحت الگوریتم هایی با پیچیدگی هایمختلف مورد ارزیابی و مطالعه قرارگرفته است و همواره سعی بر بهبود آن داشته اند. برای نیل به این هدف، از ساختمان داده های متفاوتی ازجمله صف، ماتریس، لیست های پیوندی، پشته ها و غیره برای پیاده سازی این الگوریتم ها استفاده شده است. همچنین در طول زمان، رویکرد ها و تکنولوژی های گوناگون برای افزایش کارایی و بهینه نمودن هرچه بیشتر این مسائل مطرح شده است.از مهم ترین الگوریتم های یافتن کوتاه ترین مسیر می توان به الگوریتم فلوید-مارشال 1 و دیکسترا 2 اشاره نمود. این مقاله با استفاده از قابلیت های شیءگرایی برای تشکیل گراف و همچنین محاسبات موازی 3 و تعریف واسط مناسب، به ارائه رویکردی مناسب برای افزایش کارایی الگوریتم های یادشده، که از مهم ترین الگوریتم های یافتن کوتاه ترین مسیر با دو روش متفاوت برنامه نویسی پویا وحریصانه هستند؛ پرداخته است. سپس به مقایسه و ارزیابی عملکرد مدل ارائه شده تحت گراف های متفاوت، با تعداد نودهای متفاوت در دو روش سری و موازی پرداخته شده است. نتایج به دست آمده از نرم افزار که در قالب نمودارهایی به صورت آماری ارائه گردید؛ نشان دهنده افزایش سرعت قابل ملاحظه ای است. در مدل ارائه شده همچنین امکان پویای تعریف نود در محاسبات موازی توسط کاربر در زمان کامپایل به وجود آمده است که نوعی بهبود در اجرای محاسبات موازی نیز به شمار می آیدکلیدواژه ها
یافتن کوتاه ترین مسیر، پیچیدگی زمانی، الگوریتم فلوید و دیکسترا، محاسبات موازی، شی ءگراییمقالات مرتبط جدید
- سیستم تشخیص نفوذ در محیط رایانش ابری با استفاده از یادگیری ویژ گی
- کاهش هزینه تعمیراتی ماشین های سنگین از طریق بهبود الگوریتم درخت تصمیم با الگوریتم های انتخاب ویژگی Information Gain ،Correlation و SVM
- پردازش کوانتومی تصاویر پزشکی و تشخیص لبه آن با استفاده از الگوریتم QHED
- بررسی و مقایسه روشهای تشخیص اکانت های جعلی در شبکه های اجتماعی
- مکان یابی و مقدار بهینه منابع تولید پراکنده به منظورکاهش تلفات و بهبود انحراف ولتاژ شبکه نامتعادل توزیع
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.