logo标签列表

这个多源多目的地算法是否是 NP 难问题？

algorithm
4
我有一张城市地图（2D），上面标有随机点。其中一些随机点是游客可以下车的地方。从这些下车点开始，我需要着色所有离先前访问过的点超过X长度（如英里）的点，使游客无法到达。从下车点出发，只要它们在X距离内通过每个跳跃足够接近，就可以链接所有点。同样，所有随机源和目的地都没有建立方向图。
但是，我觉得这可能是NP-Hard问题。这正确吗？
我不仅仅想找最短路径，因此我觉得这将消除Dijkstra算法以及我可以使用的某些不同图形算法选项。
明显，带有各种修剪的暴力BFS搜索无法深入。当随机点数量超过一定数量时，生成所有潜在邻居显然过于复杂。我正在考虑使用Floyd-Warshall算法或其变体，并在计算过程中标记与我的源节点不可达的点，但是由于这些点互相没有连接，因此这也将花费大量时间和内存来计算每个相关节点的所有可能邻居。
我是否过于复杂化了复杂性？也许反转问题的方式可以帮助-从所有随机节点遍历到源节点作为“目的地”？
2
只要没有负权边，Dijkstra算法应该可以正常工作；但需要对所有源运行它。有趣的是，如果一个节点的距离太远，似乎不能访问它，这实际上意味着你得到的一条边是无效的，不应该考虑在这次搜索中。 - AndyG
我以为会有，但一开始没有边缘。它们必须被生成。当存在成千上万个潜在的边缘时，它很快就会累加起来。我在想是否有某种可以使用的差异。 - user99999991
在任何具有n个顶点的简单图中，最多有n(n-1)/2条边。这并不多。至少还不足以称之为NP难问题。 - Juan Lopes
1
@JuanLopes，顶点数量并不能告诉你问题是否是NP难题。毕竟，在旅行商问题中只有(n^2 - n)/2个顶点，但它是NP难的。 - Jim Mischel
2个回答
2
我建议使用一个由宽度为R*R的正方形桶组成的网格，其中R是给定的常量距离。

将所有点放入这些桶中，然后您可以通过简单地检查以该点为中心的3*3桶数组来非常快速地回答“查找与我的当前点距离为R的所有点”的查询。

然后，您可以使用BFS来着色所有在源点范围内的点，但由于桶应该意味着您需要在每个阶段考虑更少的潜在邻居，因此速度应该更快。

（顺便说一下，您原始的方法也是多项式时间，因此此问题不是NP-hard。）

这个有名字吗？那似乎是一种迭代生成邻居的好方法，但你说的“把所有这些点放进这些桶里”是什么意思？ - user99999991
例如，假设我们通过为每个桶设置一个链表来实现这一点。当您将一个点放入桶中时，这意味着将该点添加到该位置的链表中。 - Peter de Rivaz
1

请看下面的优化

我认为您过于复杂化了。暴力方法会将每个点与其他每个点进行比较。最坏情况是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_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)
        {
            // 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推荐的“分箱”优化方法，您可以在预期情况下降低复杂度。这通过将搜索限制在相邻的箱子内来限制每个前沿点需要检查的点数：未知点可能到达的唯一位置。基本上，您创建一个网格来覆盖所有随机点。例如：

       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())
{
    // there are unreachable points
}

获取相邻的垃圾箱很容易：

：

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
}
我看到你更新了你的答案，我本来想回复说我尝试过一种标记未知/已知点的原地方法（而不是队列，但实际上仍然相同），但那还不够快。我会尝试一下相邻的箱子建议，我最初对箱子如何构建感到困惑，但你解决了这个问题。 - user99999991
1
@user999999928：原地标记仍需要查看每个点以查看是否已经被标记。您不必每次进行距离计算，但仍需查看该点。在预期情况下，队列将更有效率。但是，嗯...箱子应该会更好。 - Jim Mischel
优化更有意义。我还没有尝试过，但是使用您提出的二维设置来放置箱子（X和Y键）与使用1个键（以某种方式哈希的X＆Y）是否有特定原因？我一直在阅读不同类型的分箱，但我不知道何时应该使用其中之一。我还读到，根据随机点彼此之间的紧密程度（或相距多远），尽管我们正在寻找恒定的X单位，但我们需要更紧密的箱距离。这是否与2D分箱有关？ - user99999991
1
这些箱子在一个二维网格中，所以我是这样引用它们的。代码如何哈希键是实现细节。如果您使用数组来存储箱子，则会使用两个坐标。如果您使用稀疏数据结构，则会使用某种哈希。无论您如何实现，都不应实质性地影响运行时间。正如我所说，如果您的点是稀疏的 - 有很多空箱子 - 使用稀疏数据结构。否则，请使用数组。 - Jim Mischel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接