我有一张城市 map (2D)和整个城市的随机点。其中一些随机点是游客可以下车的地方。从这些下车点，我需要为游客无法到达的所有其他点上色，这些点距离先前访问过的点 X 长度(例如英里)内。因此，只要在 X 距离内的每一跳中距离足够近，就可以链接来自 dropoff 的点。同样，所有随机源和目的地，因此没有既定的方向图。
但是，我觉得它可能是 NP-Hard。这样对吗？
我不想要最短路径，所以我觉得这消除了 Dijkstra 和我可以使用的一些不同的图形算法选项。
带有各种修剪的蛮力 BFS 搜索显然不会走多远。通过一定数量的随机点生成所有潜在邻居太复杂了。我正在考虑 Floyd-Warshall 或一些变体，并标记点从我的来源中无法触及，但由于这些点彼此之间没有联系，这也将花费大量的时间和内存来计算所有可能的每个相关节点的邻居。
我是否将复杂性过度复杂化？也许以某种方式反转问题可能会有所帮助 - 从所有随机节点遍历作为“目的地”的源节点？
最佳答案
请参阅下面的优化
我认为你把事情复杂化了。蛮力方法会将每个点与其他点进行比较。最坏的情况是 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())
{
// there are still points in the unknown,
// which means that not all points are reachable.
}
在最坏的情况下，该算法将针对每个随机点测试每个起点，针对每个其他随机点测试每个随机点，因此复杂度为 O(r*(s + r))，其中 r 是随机点的数量，s是起点的数量。但是，请理解最坏的情况只会出现在非常稀疏的图中，或者无法到达大块点时。
请注意，如果
unknown 是常见的列表数据结构或数组，则“从未知列表中删除 unknown_point”本身可以是 O(r) 操作。一个有用的优化是使 unknown 成为一个队列，并像这样修改你的内部循环: point = frontier.dequeue()
unknown_count = unknown.count()
while (unknown_count > 0)
{
unknown_point = unknown.dequeue()
--unknown_count
if (dist(point, unknown_point) < distance)
{
// within range, add to frontier
frontier.enqueue(unknown_point)
}
else
{
// not reachable. Put it back in the unknown.
unqnown.enqueue(unknown_point)
}
}
优化
您可以通过合并 Peter de Rivaz 推荐的“分箱”优化来降低预期情况下的复杂性。这通过将搜索限制到相邻的 bin 来限制您必须为每个边界点检查的点数:唯一可能到达未知点的地方。基本上，您创建网格来覆盖所有随机点。就像是:
0 1 2 3 4 5
-------------------------------------------------------
| .. | | . . | | | |
A | . . | | . . | . | | . . |
| . | | . | . . | | . |
-------------------------------------------------------
| | . .| | . . . | |. |
B | | . | . | . . | | |
| | . | | . | | .|
-------------------------------------------------------
| . . | | . | | | . |
C | . | | . | | | . |
| | | . | | | . |
-------------------------------------------------------
| . | | . . | . | . . | . . |
D | | | . | . | . | . . . |
| . | | . | | . | . |
-------------------------------------------------------
| |. . | . . | | | |
E | | . | . | | | |
| | . | . . | | | |
-------------------------------------------------------
| | . | | . . | . . | . . |
F | | . | | . . | . . | . . |
| | . . | | . | . | . |
-------------------------------------------------------
如果您的距离阈值是
dist ，那么每个网格方块的每一边都是 dist 单位。我们知道，网格 B3 中的一个点只能在
dist 单元内的点的 9 个相邻方格中。所以我们不必针对网格 F5 中的点进行测试。请注意，并非 A3 中的所有点都一定可以从 B3 中的点到达，但它们可以。实际上，我们不能保证 B3 中的每个点都与 B3 中的每个其他点相邻。考虑一个只包含两个点的网格:一个在最左上角，一个在最右下角。这两点之间的距离将大于 dist 。根据点的密度，您可能需要某种类型的稀疏数据结构用于 bin。
您要做的第一件事是将随机点装箱。遍历随机点以找到最顶部和最左侧的坐标。那成为你的原点。 Bin A0 的左上角在 (topmost, leftmost)。然后，您可以遍历所有随机点并将它们添加到箱中。
之后，算法将重点放在 bin 上，而不是随机点数组上:
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())
{
// there are unreachable points
}
获取相邻的 bin 非常简单:
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
}
关于algorithm - 这是多源多目的地算法 NP 难吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44779099/