请看下面的优化
我认为您过于复杂化了。暴力方法会将每个点与其他每个点进行比较。最坏情况是O(r*(s+r)),其中r是随机点的数量,s是起始点的数量。
您可以使用队列来降低预期情况下的复杂度,其中所有(或大多数)点都是可达的。思路是一旦确定了一个点是可达的,就不必再次检查它是否从其他点可达。但是,您必须检查其他点是否可以从它到达。
当您开始时,所有随机点都处于“未知状态”。也就是说,它们从未被访问过。但是一旦访问了一个点,它就不再是未知的:我们知道它是可以到达的。因此,当您第一次访问一个点时,将其从未知状态移动到前沿。然后您遍历前沿,寻找在范围内的未知点。
总体思路是:
unknown = list of random points
frontier = new queue()
add all source cells to frontier
while (!unknown.isEmpty() && !frontier.isEmpty())
{
point = frontier.dequeue()
for each unknown_point
{
if (dist(point, unknown_point) < distance)
{
remove unknown_point from unknown list,
and add to frontier queue
}
}
}
if (!unknown.IsEmpty())
{
}
最坏情况下,该算法将测试每个起始点与每个随机点以及每个随机点与其他每个随机点,因此复杂度为O(r*(s + r)),其中r是随机点的数量,s是起始点的数量。需要注意的是,最坏情况只会出现在非常稀疏的图形中,或者当大量点无法到达时。
请注意,“从未知列表中删除unknown_point”本身可能是一个O(r)操作,如果
unknown
是一个常见的列表数据结构或数组。一个有用的优化是将
unknown
变成一个队列,并像这样修改内部循环:
point = frontier.dequeue()
unknown_count = unknown.count()
while (unknown_count > 0)
{
unknown_point = unknown.dequeue()
--unknown_count
if (dist(point, unknown_point) < distance)
{
frontier.enqueue(unknown_point)
}
else
{
unqnown.enqueue(unknown_point)
}
}
优化
通过采用Peter de Rivaz推荐的“分箱”优化方法,您可以在预期情况下降低复杂度。这通过将搜索限制在相邻的箱子内来限制每个前沿点需要检查的点数:未知点可能到达的唯一位置。基本上,您创建一个网格来覆盖所有随机点。例如:
0 1 2 3 4 5
-------------------------------------------------------
| .. | | . . | | | |
A | . . | | . . | . | | . . |
| . | | . | . . | | . |
-------------------------------------------------------
| | . .| | . . . | |. |
B | | . | . | . . | | |
| | . | | . | | .|
-------------------------------------------------------
| . . | | . | | | . |
C | . | | . | | | . |
| | | . | | | . |
-------------------------------------------------------
| . | | . . | . | . . | . . |
D | | | . | . | . | . . . |
| . | | . | | . | . |
-------------------------------------------------------
| |. . | . . | | | |
E | | . | . | | | |
| | . | . . | | | |
-------------------------------------------------------
| | . | | . . | . . | . . |
F | | . | | . . | . . | . . |
| | . . | | . | . | . |
-------------------------------------------------------
如果你的距离阈值是
dist
,那么每个网格正方形的边长都是
dist
单位。
因此,我们知道B3网格中的一个点只能与相邻的九个网格中的点之间距离小于
dist
单位。所以我们不需要测试F5网格中的点。请注意,并非A3中的所有点都一定可以从B3中的某个点到达,但它们
可能会。实际上,我们无法保证B3中的每个点都与B3中的每个其他点相邻。考虑一个仅包含两个点的网格:一个在极端左上角,另一个在极端右下角。这两个点之间的距离将大于
dist
。
根据您的点密度,您可能需要一种稀疏数据结构来存储网格。
首先,您需要对随机点进行分组。遍历随机点以查找最上方和最左侧的坐标。这就成为了您的原点。A0网格的左上角位于(topmost,leftmost)。然后,您可以遍历所有随机点并将它们添加到网格中。
之后,算法将专注于网格,而不是随机点数组:
frontier = new queue()
add source points to frontier
while (!allBinsAreEmpty() && !frontier.IsEmpty())
{
point = frontier.dequeue()
sourceBin = determine bin that point is in
adjacentBins = getAdjacentBins(sourceBin.x, sourceBin.y)
for each adjacent bin
{
for each binPoint in bin
{
if distance(point, binPoint) <= dist
{
frontier.enqueue(binPoint)
bin.Remove(binPoint)
}
}
if (bin is empty)
remove bin
}
}
if (!allBinsAreEmpty())
{
}
获取相邻的垃圾箱很容易:
:
getAdjacentBins(binx, biny)
{
adjacentBins[] = [bins[binx, biny]]
if (bins[binx-1, biny-1] != null) adjacentBins += bin[binx-1, biny-1]
if (bins[binx-1, biny] != null) adjacentBins += bin[binx-1, biny]
if (bins[binx-1, biny+1] != null) adjacentBins += bin[binx-1, biny+1]
if (bins[binx, biny+1] != null) adjacentBins += bin[binx, biny+1]
....
return adjacentBins
}
(n^2 - n)/2
个顶点,但它是NP难的。 - Jim Mischel