سال انتشار: ۱۳۸۶

محل انتشار: اولین کنفرانس بین المللی تحقیق در عملیات ایران

تعداد صفحات: ۲

نویسنده(ها):

اردشیر دولتی – گروه ریاضی، دانشگاه شاهد
مهدی سهرابی – دانشگاه اراک
سعید صفایی – دانشگاه اراک

چکیده:

در این مقاله الگوریتمی را معرفی خواهیم کرد که مساله کوتاهترین مسیر مقید را که یکی از مسائل بسیار مهم و شناخته شده در زمینه الگوریتمهای گراف است، را در زمان حل می کند. قید این الگوریتم بر روی تعداد رئوس است .این مساله یک مساله NP-Complete می باشد. این الگوریتم را می توان برای حل مسائل TSP و مسیر هامیلتونی و دور هامیلتونی در حالت کلی و مقید به کار برد. با تغییری اندک در این الگوریتم آن را می توان بر روی مسائل فوق با قید بر روی یالها به کار برد که در این حالت الگوریتم در زمان انجام پذیر است