注意没有控制中心！
#1 楼
假设您的环境是加权图。每条边的权重表示距离。边缘（$ E $）可能是道路，节点（$ V $）可能是路口。让我们进一步假设每个机器人的速度为$ v $。您说每个“点”需要每$ h $小时进行一次测量。我认为这意味着城市中的每个点，也就是每个道路和路口的每个点。由于这是一座城市，因此我们也可以假设该图已连接。就是将路口中的一个点作为图形节点，并将从道路边缘到该点的距离添加到该道路权重（道路长度）中。这意味着没有时间在节点上，而所有时间都花在了边缘上。
下界
首先，让我们找到一个限制机器人数量的下限。如果我们对边缘的权重求和，则得出需要移动的总距离。所需的最少机器人数量为：
$ N_ {min} = \ bigg \ lceil \ dfrac {\ sum_ {i \ in E} w_i} {h \ times v} \ bigg \ rceil $
如果机器人可以在每条道路上不重复移动边缘的情况，则此下限是实际所需的数量。这样想吧。想象一下这个城市是这样的：
X----------X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
想象每个边缘为1Km，机器人的速度（$ v $）为0.7Km / h。想象一下$ h $是两个小时。每个机器人在这两个小时内可以行驶$ h \ times v = 2 \ times 0.7 = 1.4Km $。现在，如果您按规则的时间间隔将机器人放置在循环中，并且它们全部沿顺时针方向移动，那么就像一个点的2小时限制即将到期时，另一个机器人应该到达该点。这意味着应该以1.4Km的间隔放置机器人。只需将环的周长除以1.4（并取上限）即可获得所需的机器人数量。
注意：欧拉图本质上是一个扭曲的回路，对于此类图，上面的公式给出了所需机器人的确切数量。不幸的是，一个城市距离欧拉图还很远。
上界
这是一个更困难的问题。但是，这是一个主意。
首先，让我们为另一个简单的情况解决问题。想象一下，图形只是一条线：
X--------X------------------X-------X----X-----------X
然后，机器人无法再转圈了，但他们必须“巡逻”。这意味着他们必须将一半的时间用于一种方式，而另一半则要回来。换句话说，所需的机器人数量变为：
$ N_ {min} = \ bigg \ lceil \ dfrac {\ sum_ {i \ in E} w_i} {（h / 2）\ times v} \ bigg \ rceil $
另一观点可能是机器人通过走到一端然后回到另一端来循环这条路径，在这种情况下，机器人的数量为：
$ N_ {min} = \ bigg \ lceil \ dfrac {2 \ times \ sum_ {i \ in E} w_i} {h \ times v} \ bigg \ rceil $
与在路径上巡逻完全相同。
，这是一个算法，可为所需的机器人数量设定上限。
1. do
2. G' = G with marked edges removed
3. if loop L exists in G'
4. put robots looping in L
5. mark edges of L
6. else
7. find a random unexpandable path P in G'
8. find the shortest path P' in G that connects both ends of P
9. create a loop L by combining P and P'
10. N1 = number of robots needed to patrol P
11. N2 = number of robots needed to loop in L
12. if N1 < N2
13. put robots patrolling P
14. mark edges of P
15. else
16. put robots looping in L
17. mark edges of L
18. while unvisited edges remain
注释：
在3，我们尝试从知道最佳答案的图形中提取欧拉环。
在7，我们尝试以获得尽可能长的路径，并让机器人巡逻它们。确保路径尽可能扩展。也就是说，如果在路径的任何一端都连接有未标记的边缘，则只需用该边缘扩展路径即可。
8和9的目的是让机器人巡逻找到的路径可能是远非最佳。实际上，如果我们允许机器人通过可能已经标记的边缘从路径的一端移动到另一端，那么也许我们会发现一个导致机器人数量减少的循环。 10和11计算两种情况下的机器人数量，而12决定哪种机器人更好。
这是一个例子。想象一下下图：
X----------X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
首先，我们找到一个循环并将其标记。想象一下，这是顶部循环：
X**********X
* *
* *
* *
X X
* *
* *
* *
X**********X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
现在我们走了这条路：
X X
/ \
/ \
/ \
X X
\ /
\ /
\ /
X----------X
我们可以使用更多数量的机器人巡逻路径，也可以使用先前访问过的边沿进行循环，并让更少的机器人行驶。最后，最好有两个循环。
算法也可以找到不同的解决方案。例如，第一个循环可能是外部循环：
X**********X
* *
* *
* *
X X
* *
* *
* *
X----------X
* *
* *
* *
X X
* *
* *
* *
X**********X
之后，我们将中心边缘作为路径放置：
X----------X
显然，让机器人巡逻比在访问的边缘之外创建一个很大的循环要好。
有趣的是，在这种情况下，上述算法中最短的路径
P'实际上就是该路径本身。结果，该循环本质上是在此路径两端之间循环的机器人（而不是仅巡逻其特定路径部分）。无论哪种方式，机器人的最佳数量都与前面提到的相同。最佳数量
我真的不知道。
有可能（但我还没有证明）这个问题甚至不属于$ P $，所以可能根本没有任何有用的解决方案（再次，我可能是错的）。
如果您发现“上限”算法不能提供足够少的机器人，例如，您自己检查图形并找到明显的优化方法，则还可以始终尝试使用优化算法（例如遗传算法）。
请注意，这里没有控制中心！
提醒您，我的解决方案是计算每个机器人所需的路径离线圈入（或巡逻），然后对机器人进行编程，使其永远保持原路。这不能解决诸如机器人损坏以及其他必须掩盖之类的问题。