سال انتشار: ۱۳۸۹

محل انتشار: سومین همایش ملی مهندسی کامپیوتر و فناوری اطلاعات

تعداد صفحات: ۷

نویسنده(ها):

زهرا معزکریمی – دانشکده مهندسی کامپیوتر و فناوری اطلاعات دانشگاه صنعتی امیرکبیر
علیرضا باقری –

چکیده:

مساله بیدارسازی n ربات خواب توسط یک ربات بیدار اولیه Freeze Tag Problem (FTP) است تاکنون راه حلهای متعددی برای این مساله ارائه شده است دراین مقاله ابتدا راه حلهای ارائه شده برای مساله FTP مرور می گردد و سپس FTP در حالت گسترش یافته مورد بررسی قرار م یگیرد فرض می کنیم به جای یک ربات بیدار اولیه k ربات بیدار اولیه داریم این مساله حالت گسترش یافته FTP است مساله جدید را k-FTP می نامیم مجموعه ای از n ربات خاموش خواب وجود داردو هدف بیدارسازی فعالسازی این ربات ها در خواب با داشتن k ربات بیدار اولیه در کمترین زمان ممکن است با این تعریف در واقع FTP حالت خاصی از k-FTP می باشد که در آن K=1 می باشد دراین مقاله k-FTP برای حالتی که K=2 است بررسی شده و یک الگوریتم با فاکتور تقریب ثابت و زمان اجرای O(nlogn) برای ۲-FTP در محیطهای هندسی اقلیدسی ارائه می گردد.