الگوریتمهایی با پیچیدگی زمانی چندجملهای برای حل مسائل بازی امنیتی مجموع صفر و مجموع ناصفر | ||
| علوم و فناوریهای پدافند نوین | ||
| مقاله 3، دوره 13، شماره 1 - شماره پیاپی 47، بهار 1401، صفحه 23-34 اصل مقاله (1.22 M) | ||
| نوع مقاله: مقاله پژوهشی | ||
| نویسندگان | ||
| سمانه اسماعیلی1؛ حسن حسن پور* 2؛ حمید بیگدلی3 | ||
| 1دانشجوی دکتری، گروه ریاضی، دانشگاه بیرجند،ایران | ||
| 2دانشیار دانشکده علوم ریاضی وآمار، دانشگاه بیرجند، ایران | ||
| 3استادیار پژوهشکده عالی جنگ، تهران، ایران | ||
| چکیده | ||
| با توجه به اهمیت مسئله امنیت، تخصیص بهینه نیرو از موضوعات مورد توجه پژوهشگران است. در دو دهه گذشته، شاخه جدیدی از نظریه بازی به نام بازی امنیتی برای محاسبه سیاست دفاعی بهینه با موفقیت برای مسائل امنیتی بهکار گرفته شده است. در این بازیها علاوه بر محدودیت منابع، عکسالعمل منطقی مهاجم به هر راهبرد مدافع نیز درنظر گرفته میشود. پیش از این با تحلیل نظریه بازی، مسائلی بهینهسازی بهمنظور تخصیص بهینه نیرو ارائه شده و الگوریتمهایی نیز پیشنهاد شدهاند که برای هر نوع بازی امنیتی و در هر شرایطی کارایی ندارند. در این مقاله الگوریتمی با زمان اجرای چندجملهای برای محاسبه میزان پوشش بهینه اهداف ارائه شده است. اساس کار الگوریتم، گسترش مجموعه اهدافی موسوم به مجموعه حمله است که در مجموعه بهترین پاسخهای مهاجم قرار میگیرند؛ و درنهایت محدود کردن این مجموعه به هدفی با بیشینه عایدی مدافع است. در ادامه، بازی امنیتی مجموع صفر معرفی شده است که در آن با انتخاب هر راهبرد مدافع، مجموع عایدی مدافع و مهاجم صفر است. ثابت میشود که برای محاسبه جواب بهینه در این بازی، کافی است بزرگترین مجموعه حمله محاسبه شود. بر این اساس، الگوریتمی زمان چندجملهای برای این نوع بازی نیز ارائه شده است. | ||
| کلیدواژهها | ||
| تخصیص بهینه نیرو؛ بازی امنیتی؛ بازی مجموع ناصفر؛ بازی مجموع صفر؛ الگوریتم زمان چندجملهای | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 496 تعداد دریافت فایل اصل مقاله: 326 |
||