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