سال انتشار: ۱۳۹۰

محل انتشار: اولین کنفرانس ملی دانش پژوهان کامپیوتر و فناوری اطلاعات

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

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

میر محمد علیپور – دانشگاه بناب – گروه مهندسی کامپیوتر

چکیده:

امروزه صنایع فراوانی با مساله پیدا کردن کوتاهتیرین مدار هامیلتونی (مساله فروشنده دوره گرد) درگیر می باشند و با توجه به اینکه این مساله جزء مسائل np-complete بوده و راه حل قاطعی که تابحال برای آن ارائه شده ، دارای مرتبه زمانی نمایی است بهمین دلیل الگوریتم های تقریبی متعددی از جمله الگوریتم های مبتنی بر شبکه های عصبی ، کولونی مورچه ها ، الگوریتم ژنتیکی و غیره برای حل آن گزارش شده است . در این مقاله با استفاده از اتوماتای یادگیر توزیع شده که یک ابزار جستجوی عمومی بوده و برای حل تعدادی از مسائل np-complete یکار برده شده اسن یک الگوریتم جدید برای حل مساله فروشنده دوره گرد معرفی خواهیم کرد که کارایی آن را با استفاده از هیوریستیک جستجوی محلی opt-2 افزایش داده ایم و در نهایت کارایی الگوریتم تلفیفی ارائه شده را بر روی نمونه مسائل استاندارد مساله فروشنده دوره گرد بررسی کرده و نتایج بدست امده را با الگوریتم قبلی که از هیوریستیک opt-2 استفاده نمی نماید و نیز با برخی از الگوریتم های تقریبی موجود مقایسه می کنیم. آزمیشهای انجام گرفته نشان می دهد که الگوریتم پیشنهادی در مقایسه با الگوریتم های بررسی شده از کارایی بهتری برخوردار است.