الگوریتم تقریبی برای پیدا کردن کوتاه ترین مسیر با محدودیت راسی در گراف های بزرگ
Publish place: The 7th National Conference on Computer Science and Engineering and Information Technology - January 2019
Publish Year: 1398
Type: Conference paper
Language: Persian
View: 774
This Paper With 10 Page And PDF Format Ready To Download
- Certificate
- I'm the author of the paper
Export:
Document National Code:
CECCONF07_009
Index date: 15 August 2019
الگوریتم تقریبی برای پیدا کردن کوتاه ترین مسیر با محدودیت راسی در گراف های بزرگ abstract
جستجوی کوتاه ترین مسیر یکی از مسائل مهم در نظریه گراف است که به خوبی مورد توجه و مطالعه قرار گرفته است. این مقاله، حالت خاصی از مسئله کوتاه ترین مسیر است، پیدا کردن کوتاه ترین مسیر با محدودیت راسی که توسط کاربر تعیین شده اند را مورد مطالعه قرار می دهد، که این مسئله، یک مسئله NP- سخت است. برای حل کوتاه ترین مسیر الگوریتم های زیادی موجود هستند که اکثر آ نها تمام جایگشت های رئوس داده را محاسبه می کنند سپس کوتاه ترین آ نها را از میان این جایگشت ها می یابند. زمانی که اندازه گراف یا مجموعه رئوس داده شده بزرگ باشند، هزینه انجام محاسبات به شدت زیاد خواهد بود. در این مقاله ابتدا یک الگوریتم ابتکاری برای جستجوی بهترین- اولین را مطرح شده و سپس یک الگوریتم تقریبی ابتکاری در زمان چند جمله ای برای این مسئله روی گراف های بزرگ ارائه شده است. نتایج تجربی معتبری وجود دارند که نشان می دهند حتی اگر اندازه گراف یا مجموعه رئوس بزرگ باشند الگوریتم های ارائه شده، از روش های موجود بهتر هستند.
الگوریتم تقریبی برای پیدا کردن کوتاه ترین مسیر با محدودیت راسی در گراف های بزرگ Keywords:
الگوریتم تقریبی برای پیدا کردن کوتاه ترین مسیر با محدودیت راسی در گراف های بزرگ authors
محمدرضا قائمی
دانشگاه زنجان، دانشکده علوم، گروه ریاضی
نوید تقی پور
دانشگاه زنجان، دانشکده علوم، گروه ریاضی