یک الگوریتم تقریبی با فاکتور تقریب ثابت و زمان اجرای خطی برای مساله ی freez_tag اقلیدسی
محل انتشار: شانزدهمین کنفرانس سالانه انجمن کامپیوتر ایران
سال انتشار: 1389
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 896
فایل این مقاله در 5 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
CSICC16_130
تاریخ نمایه سازی: 28 بهمن 1390
چکیده مقاله:
مساله بیدارسازی مجموعه ای از رباتهای خواب توسط یک ربات بیدار اولیه Freeze-Tag Problem (FTP) نام دارد در FTP هدف بیدراسازی کلیه رباتها در کمترین زمان ممکن است این مساله در حالت کلی NP-Hard و درحالت اقلیدسی از جمله مسائل باز OPEN به شمار می رود دراین مقاله الگوریتمهای تقریبی برای fTP درمحیط اقلیدسی مدنظر قرارم یگیرند ابتدا یک الگوریتم تقریبی بافاکتور تقریب O(1 و زمان اجرای O(nlogn که توسط آرکین وهمکارانش ارایه شده است معرفی می گردد و سپس یک الگوریتم با فاکتور تقریب بهتر و زمان اجرای خطی برای مساله ارایه میشود.
کلیدواژه ها:
نویسندگان
زهرا معز کریمی
دانشجوی کارشناسی ارشد ،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دان
علیرضا باقری
استادیار،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دانشگاه صنعتی ام
احسان یزدی
دانشجوی کارشناسی ارشد ،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دان
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :