انجمن کامپیوتر ایران

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