排序方式: 共有1条查询结果,搜索用时 0 毫秒
1
1.
Sztainberg M.O. Arkin E.M. Bender M.A. Mitchell J.S.B. 《Robotics, IEEE Transactions on》2004,20(4):691-701
In the "freeze-tag" problem, we are given a swarm of n sleeping (frozen or inactive) robots and a single awake (active) robot. The goal is to awaken all robots in the shortest possible time. A robot is awakened when an active robot "touches" it. The goal is to compute an optimal awakening schedule such that all robots are awake by time t/sup */, for the smallest possible value of t/sup */. We devise and test a variety of heuristic strategies on geometric and network datasets. Our experiments show that all of the strategies perform acceptably well, with the simple greedy strategy performing particularly well. A theoretical analysis of the greedy strategy gives a tight approximation bound of /spl Theta/(/spl radic/logn) for points in the plane. We show more generally a tight performance bound of /spl Theta/((logn)/sup 1-1/d/) in d dimensions. The geometric case contrasts with the case of general metric spaces, where greedy is known to have a /spl Theta/(logn) approximation factor, and no method is known to achieve an approximation factor of o(logn). 相似文献
1