الگوریتم تقریبی برای پیدا کردن کوتاه ترین مسیر با محدودیت راسی در گراف های بزرگ
- سال انتشار: 1398
- محل انتشار: هفتمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات
- کد COI اختصاصی: CECCONF07_009
- زبان مقاله: فارسی
- تعداد مشاهده: 823
نویسندگان
دانشگاه زنجان، دانشکده علوم، گروه ریاضی
دانشگاه زنجان، دانشکده علوم، گروه ریاضی
چکیده
جستجوی کوتاه ترین مسیر یکی از مسائل مهم در نظریه گراف است که به خوبی مورد توجه و مطالعه قرار گرفته است. این مقاله، حالت خاصی از مسئله کوتاه ترین مسیر است، پیدا کردن کوتاه ترین مسیر با محدودیت راسی که توسط کاربر تعیین شده اند را مورد مطالعه قرار می دهد، که این مسئله، یک مسئله NP- سخت است. برای حل کوتاه ترین مسیر الگوریتم های زیادی موجود هستند که اکثر آ نها تمام جایگشت های رئوس داده را محاسبه می کنند سپس کوتاه ترین آ نها را از میان این جایگشت ها می یابند. زمانی که اندازه گراف یا مجموعه رئوس داده شده بزرگ باشند، هزینه انجام محاسبات به شدت زیاد خواهد بود. در این مقاله ابتدا یک الگوریتم ابتکاری برای جستجوی بهترین- اولین را مطرح شده و سپس یک الگوریتم تقریبی ابتکاری در زمان چند جمله ای برای این مسئله روی گراف های بزرگ ارائه شده است. نتایج تجربی معتبری وجود دارند که نشان می دهند حتی اگر اندازه گراف یا مجموعه رئوس بزرگ باشند الگوریتم های ارائه شده، از روش های موجود بهتر هستند.کلیدواژه ها
کوتاه ترین مسیر، الگوریتم تقریبی، پیچیدگی محاسباتیمقالات مرتبط جدید
- مرور سیستماتیک کاربرد هوش مصنوعی در موسیقی
- In-silico Analyses for Finding Potential Key Genes and Pathways Associated with Guillain-Barré Syndrome Using Computational Tools
- OCD Severity Based on EEG Signals
- Investigating the (non) -Impact of Customizing Knowledge Bases of Artificial Intelligence -Driven Robot on Language for Specific Purposes Learning
- The Need for Telehealth and Tele-Educationon in Optimizing Measles Surveillance and Reducing Healthcare Costs
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.