یک الگوریتم تقریبی برای بیدار سازی روبات ها در فضای اقلیدسی

یک مسأله بهینه سازی در زمینه روباتیک گروهی است که با یک مجموعه از روبات ها که در صفحه اقلیدسی قرار دارند شروع می شود. همه روبات ها بجز یک روبات خواب هستند. وقتی که یک روبات که در مجاورت یک روبات دیگر قرار گیرد آن را بیدار می کند. روبات بیدار شده می تواند حرکت کند و دیگر روبات ها را بیدار کند. FTP در حالت کلی NP-Hard و در حالت اقلیدسی از جمله مسائل باز است. در این مقاله یک الگوریتم تقریبی به صورت بازگشتی برای FTP در محیط اقلیدسی ارائه خواهیم داد که فاکتور تقریب آن ثابت و پیچیدگی زمانی آن خطی است.

کلیدواژه ها:

الگوریتم بازگشتی ، Freeze Tag Problem ، بهینه سازی ، روباتیک گروهی ، هندسه محاسباتی