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

محل انتشار: نوزدهمین کنفرانس مهندسی برق ایران

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

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

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

چکیده:

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