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

سیده لیلی شاهمرادی¹

1) شاهمرادی

محل انتشار : سومین کنفرانس بین المللی پژوهش در علوم و تکنولوژی(3rstconf.com)
چکیده :
در اين مقاله يك الگوريتم مبتني بر اتوماتاهاي يادگير براي يافتن درخت پوشاي مينيمم در يك گراف تصادفي (درختي پوشا با كمترين هزينه مورد انتظار) پيشنهاد ميشود. فرض بر اين است كه تابع توزيع وزن يالها از قبل شناخته شده نيست و فقط به نمونه هاي توزيع يالها دسترسي داريم. هدف الگوريتم يافتن درخت پوشاي مينيمم با حداقل تعداد نمونه گيري از يالهاي گراف مي باشد. در الگوريتم پيشنهادي در هر تكرار اتوماتاي يادگير يالي از گراف را براي نمونه گيري نامزد مي كند و سپس بر اساس كمي تجزيه و تحليل آماري مشخص مي شود كه آيا از آن يال بايد نمونه گرفته شود يا نه. با انتخاب مناسب پارامترهاي اتوماتاهاي يادگير، الگوريتم پيشنهادي قادر است كه درخت پوشاي مينيمم را با احتمالي نزديك 1 پيدا كند. به منظور ارزيابي الگوريتم پيشنهادي، تعداد نمونه هاي گرفته شده توسط الگوريتم با تعداد نمونه هاي مورد نياز به روش نمونه گيري استاندارد مقايسه شده است. نتايج آزمايشي نشان داده كه تعداد نمونه هاي گرفته شده توسط الگوريتم پيشنهادي به مراتب كمتر از تعداد نمونه هاي گرفته شده به روش نمونه گيري استاندارد مي باشد.
کلمات کلیدی : گراف تصادفي درخت پوشاي مينيمم اتوماتاهاي يادگير .