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

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

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

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

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

چکیده:

مساله درخت اشتاینر یکی از مسایل NP-complete می باشد و بهمین دلیل الگوریتمهای تقریبی متعددی برای حل آن گزارش شده است. در این مقاله ابتدا یک الگوریتم تقریبی که از ترکیب الگوریتم ژنتیکی و اتوماتاهای یادگیر حاصل شده است برای حل مساله اشتاینر ایستا پیشنهاد می شود و سپس با استفاده از این الگوریتم ، الگوریتمی برای حل مساله درخت اشتاینر پویا ارایه می گردد . به منظور نشان دادن کارایی الگوریتم های پیشنهادی، این الگوریتم ها بر روی گرافهای مجموعه Bمسائل بیسلی اجرا و سپس نتایج بدست آمده با نتایج بدست آمده برای تعدادی از الگوریتمهای گزارش شده مقایسه گردیده است. نتایج ازمایشها کارایی الگوریتم پیشنهادی را نشان می دهد.