1

我有一个宽度为 w 和高度为 h 的对象。对象需要找到最快的路径以在最短的时间内覆盖整个区域。可以把它想象成一个机械臂，需要将化学物质喷洒到整个表面。黑色区域是不能横穿的区域。

物体在一个区域内移动

在上图中，w x h 对象正在穿过一个区域（它后面的深灰色区域是已经被覆盖的区域）。如果物体以速度 v 移动并需要 t 秒转 90 度（或每转 1 度需要 t/90），我需要制定一个算法来确定覆盖整个区域的最快路径。物体可以移动到指定区域之外。

目标应该是最小化转弯次数并最大化线性运动。假设我对所有东西都进行了测量，我将如何开始编写可以确定这条路径的东西？

4

1 回答 1

1

[编辑答案] 对不起，我错了。

对我来说，最好的解决方案是一个看起来像这样的算法：

1. what is the smallest rectangle that covers the all area
2. compute the time to 'paint it' from your starting position:
    2.1 as you can go outside, just
        2.1.1 calculate time  if browsing by rows
        2.1.2 if by column
        2.1.3 if turning from outer to center
        2.1.4 if turning from outer to center
    2.2 decide what is the most efficient solution
3. store this result
4. subdivise the area in 2 smaller rectangles
5. redo the same thing for the 2 and test various combination for the travel from rectangle 1 to 2 (obviously the starting pos on 2 is free) Always keep track that anything bigger than the cost of the first solution can be ignored

如果我能给出一个简单的猜测，这在数学上并不是最快的，但一个好的解决方案是大多数 AOI 所做的，只做最大的矩形。

这个问题在数学上取决于很多变量，如果 t 很重要（通常对机器人来说是正确的），那么简单的解决方案可能接近解决方案 a，因为它是最小转弯的解决方案。

已经找到矩形的最佳解决方案是好的。然后是图的问题（矩形图，图之间的连接是另一个问题）

抱歉，我帮不上忙。

于 2013-09-04T20:38:45.990 回答