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

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

اتوماتاهای یادگیر، الگوریتم ژنتیک، درخت اشتاینر