26

几乎完全相同的问题。但我仍然不明白，这种启发式方法是如何工作的，以及顶点以什么顺序通过。书中还有一张图：在此处输入图像描述

这显示了最近邻启发式和我认为是最近对启发式的比较。从图中我可以假设在上图中，首先选择了 0 点，但在下图中，选择了最左边或最右边的点。因为没有任何关于第一个点选择的说明（最近对启发式也没有做任何动作），我可能会假设任何算法的结果无论多么好它都不会给你底部的图片，如果它没有考虑一下，从什么开始。

现在我只想知道，最近对启发式的步骤是什么。一张类似于底部的图片，带有与每次迭代相关的数字以及解释，将不胜感激。

这是从该帖子中获取的书的链接。

4

4 回答 4

17

我没有这本书，但它显示了最近邻启发式与该数据的最佳解决方案的比较。此处显示的数据为 (-21, -5, -1, 0, 1, 3, 11)。

混淆可能在“局部”贪心算法和“全局”贪心算法之间（因为没有更好的词）。上面显示的最近邻居是严格本地的。“机器人”从 0 开始，选择走到 1，因为它是最近的路径。机器人在 1，并找到下一个最近点是 -1。然后机器人在-1，下一个最近的点是3，依此类推。

最接近的对更具全局性。它同时查看所有最佳边缘。因此，该算法从 0 开始，并找到四个恰好相隔 1 个单位的 (0, 1)、(1, 0)、(-1, 0) 和 (0, -1)。它将添加两个不同的对来创建图形 (-1, 0, 1)。这可以是定向的或非定向的。

然后它会重复，并注意到 (1, 3) 是下一个最小的边，依此类推，直到它到达最优解。

不同之处在于，在最近邻的情况下，机器人只能查看其当前所在位置的邻居。在最近对的情况下，您可以查看所有边以选择最小的边。

于 2012-07-12T20:06:01.903 回答
15

我同意这在书中不是很清楚（这有点令人沮丧，因为读者马上就会遇到它——我的版本中的第 7 页）。

我认为这里的困难不在于最近对启发式本身。关键是要注意启发式方法本身并不是问题的解决方案！只有算法的一部分（可以说是最重要的部分）在书中从未完全描述过（可能是因为这是一个错误的算法）。使用启发式，您可以获得应该连接的顶点对，但不是它们应该连接的顺序。为此，需要更多的东西。

为了完整起见，这是书中的问题陈述

问题：机器人漫游优化

输入：平面上n个点的集合S

输出：访问集合S中每个点的最短循环旅行是多少

现在，最接近对启发式，如书中定义并在此处引用，只为您提供一组连接/列表，而不是游览本身，因此不是所需的解决方案。要获得游览，您将不得不做更多的事情。使用此策略的整体（有缺陷！）解决方案如下所示：

1) Initialize the output list of vertexes to visit as the empty list (call it RET).
2) Obtain the list of connections (vertex pairs) given by ClosestPair (let it be L)
3) If L is empty, jump to 12
4) Remove an arbitrary connection from L (call it C1).
5) Choose an arbitrary vertex from C1 (call it V1)
6) Append V1 to RET
7) Remove from L the other connection that contains V1 (call it C2)
8) Choose the other vertex from that connection (call it V2)
9) append V2 to RET
10) Set V1=V2
11) If L is not empty, jump back to 7
12) return RET

或者在伪代码中

Alg(P): # P is the input set of points
    RET = []
    L = ClosestPairs(P)
    if(L.empty()):
        return RET
    C1 = L.getAndRemoveRandomElement()
    V1 = C1.getRandomVertex()
    RET.append(V1)
    while(!L.empty()):
        C2 = L.getAndRemoveElementContaining(V1)
        V2 = C2.getTheOtherVertex(V1)
        RET.append(V2)
        V1 = V2
    return RET
于 2014-11-23T20:26:35.070 回答
3

我在理解这个启发式时遇到了同样的问题，我的回答可能会帮助其他面临同样问题的人。

机器人需要的是一个封闭的路径，它访问所有的点并循环回到它的原始位置。有一个声明提到过早终止，它坚持认为路径应该是完整的（访问所有点，即我们不应该加入一些顶点对，这样它们会创建一个更小的封闭路径）。

现在通过下面的例子

图 1.3

在这里，通过使用最近对启发式，我们将找到一条连接一条线上所有点的路径，然后将剩余的端点相互连接（-21，11）。因此，无论机器人从 0 还是 -21 或 11 开始，它都将行进相同的距离（它将绕回其起始位置进行下一次迭代）。这个距离将是最佳距离。

但上述方法在以下情况下失败

图 1.4

这里最接近的对路径原来是左边的图像，而最佳路径应该是右边的图像，因此启发式无法给出正确的解决方案。

于 2019-01-07T02:59:38.770 回答
2

TL; DR - 据我了解，“坏”方法将越来越远的未访问点直接相互连接，在多个弧中浪费更多焊料，并最终将最后一个点连接回第一个点“0”。

“更好”的方法一次从中心向外移动 1 点在任一方向上，因此仍然来回移动，但仅在沿“数字线”的直接相邻点之间铺设焊料。

单个静态图像中的插图和解释确实不清楚。他没有解释虚线的含义（它是焊接的吗？只是运动吗？似乎不一致）。同意在本应是“清晰”的算法书中这么早遇到这令人沮丧......

“最近的邻居”和“最近的对”示例似乎都在点 0 上来回“跳房子”，这是第一种方法不好的原因。他甚至说第二种方法也应该左右交替，那怎么更好呢？因为您只将相邻的点直接连接起来，逐步构建完整的线。

“坏”的例子（据我所知）：

1. 0 connects to 1
2. 1 jumps over 0 & connects to -1
3. -1 jumps over 0 & connects to 3
4. 3 jumps over 0 & connects to -5
5. -5 jumps over 0 & connects to 11
6. 11 jumps over 0 & connects to -21
7. -21 connects back to 0, completing the cycle.

这些“跳房子”来回超过0，但不要将点连接在一条直线上。你结束了 w/6 不同的焊接连接“线”。

“更好”的最接近配对示例：

1. 0 connects to 1.
2. 0 connects to -1
3. 1 connects to 3
4. -1 connects to -5
5. 3 connects to 11
6. -5 connects to -21
7. -21 connects to 11 
8. Unstated, the robot arm apparently travels back to 0 afterward?

这些也可以在 0 上来回移动，但在每一步将现有直线一次递增地延伸一个点。而不是 6 弧焊料，大部分都有一条线，然后是最外端点的第二个连接。

于 2019-12-30T13:54:59.093 回答