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

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

کلیدواژه ها:

گراف تصادفی ، درخت پوشای مینیمم ، اتوماتای یادگیری