درخت پوشای مینیمم با محدودیت تاخیر با استفاده از اتوماتای یادگیر

مسئله درخت پوشای کمینه عبارت است از یافتن یک زیر گراف از گراف غیرجهت دار و وزن دار به طوری که همه گره های گراف را پوشش دهد و وزن کلی تخصیص داده شده به یال های آن از بین همه درخت های پوشای ممکن کمتر باشد. در همه درخت های پوشای کمینه هدف، به حداقل رساندن وزن است با این وجود گاهی محدودیت های دیگری نیز بر این درخت ها تحمیل می شود. با توجه به این محدودیت های اضافه مسئله درخت پوشای کمینه محدود شده مطرح می شود که کاربردهای فراوانی دارد.از انواع درخت های پوشای کمینه محدود شده که کاربردهای فراوانی در مسائل مختلف مربوط به شبکه دارند، می توان درخت پوشای کمینه با تاخیر محدود را نام برد که از مسائل بغرنج می باشد متاسفانه الگوریتم های قطعی برای حل این مسائل در شبکه های پویا مناسب نیستند، زیرا یک الگوریتم خوب باید بتواند توازنیبین هزینه درخت، زمان اجرا و نیازمندی های حافظه در شبکه های پویا برقرار کند. به همین دلیل روش های تقریبی که بتوانند درخت های نزدیک به بهینه را تولید کنند اهمیت فراوانی دارند. تحقیقات نشان داده اند که از میان روش های تقریبی اتوماتای یادگیر در حل این مسائل نتایج بهتری نسبت به سایر روش های تقریبی دارد. از این روی، در این مقاله الگوریتمی مبتنی بر اتوماتای یادگیر برای حل مسائل درخت پوشای کمینه محدود شده پیشنهاد شده است که نتایج به دست آمده کارایی الگوریتم پیشنهادی را از لحاظ بهینگی جواب های تولید شده و همچنین زمان اجرای الگوریتم نشان می دهد

Keywords:

درخت پوشای کمینه , درخت پوشای کمینه محدود شده , اتوماتای یادگیر