مشاهده مشخصات مقاله
يک الگوريتم تقريبي با فاکتور تقريب ثابت و زمان اجراي خطي براي مسأله‌ي Freeze-Tag اقليدسي
|
Authors |
-
زهرا معزکریمی
-
علیرضا باقری
|
|
Conference |
شانزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران |
|
Abstract |
مسأله‌ي بيدارسازي مجموعه‌اي از ربات‌هاي خواب توسط يک ربات بيدار اوليه، Freeze-Tag Problem (FTP) نام دارد. در FTP هدف، بيدارسازي کليه ربات‌ها در کمترين زمان ممکن است. اين مسأله در حالت کلي NP-Hard و در حالت اقليدسي از جمله مسائل باز (Open) به شمار مي‌رود. در اين مقاله الگوريتم‌هاي تقريبي براي FTP در محيط اقليدسي مد نظر قرار مي‌گيرند. ابتدا يک الگوريتم تقريبي با فاکتور تقريب O(1) و زمان اجراي O(n logn) که توسط آرکين و همکارانش ارائه شده‌است، معرفي مي‌گردد و سپس يک الگوريتم با فاکتور تقريب بهتر و زمان اجراي خطي براي مسأله ارائه مي‌شود. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}