不明白的“算法设计手册”最近对启发式(Don't understand closest pa

有几乎一模一样的问题。但我还是不明白，这是怎么启发式的工作和所传递何种顺序顶点。也有是在一本书的图片：

这表明最近-neghbor启发式的比较我相信这是一个最接近，对启发。从图像I可以假设在顶部图片，0点是第一次选择，但在底部的图片有选择最左边或最右边的一个。因为没有什么说一下第一点选择（也是最接近，对启发式并不做任何动作），我可以假设任何算法结果再好它，如果它不不会给你底部的图片考虑入手点什么。

现在我只是想知道，什么步骤最接近，对启发式品牌。类似于底部用一个与解释沿着每个迭代相关联的数字的图像，将不胜感激。

这里是链接到从后所采取的书。

Answer 1:

我没有这本书，但它显示的最近邻居启发式对这些数据的最佳解决方案的对比。这里示出的数据是（-21，-5，-1，0，1，3，11）。

这种混乱可能是一个“局部”贪心算法和“全局”贪心算法（因为缺乏更好的词）之间。上面显示的最近的邻居是严格的地方。 “机器人”从0开始选择去1，因为它是最接近的路径。机器人为1，并发现下一个最接近的点是-1。然后机器人是在-1和下一个最接近的点是3，等等。

最近对更加全球化。这是一次看着都最佳的边缘。所以，该算法开始于0，并发现4是恰好1个单位间隔（0，1），（1,0），（-1,0）和（0，-1）。这将增加两个不同的对创建的曲线图（-1，0,1）。这可能是因为存在定向或不定向。

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

所不同的是，在最近的邻居情况下，机器人只能看看它当前所处的邻居。在最近的对的情况下，你可以看看所有边缘选择最小的一个。

Answer 2:

我同意这是不是在书（这是一个有点令人沮丧的是，读者遇到它的时候了 - 第7页在我的版本）很清楚。

我觉得这里的困难是不是在最近，对启发式本身。关键是注意到，启发式本身不应该是解决问题的办法！只有始终不完全书中所描述的算法的一部分（可以说是最重要的部分）（可能是因为这是打算作为一个错误的算法）。通过启发式，你得到的对应连接顶点，但不是在它们应该被连接的顺序 。为此，需要更多的讨论。

为了完整起见，这里是一本书的问题陈述

问题：机器人之旅优化
输入：在飞机上的n个点集合S
输出：什么是访问的每个点集合S中周期最短游

现在， 最接近-pair策略 ，如在书中定义并引用在这里，只给你连接的一组/列表，而不是旅游本身，所以不要求的解决方案。为了获得旅游你就必须做更多的事情。使用这种策略看起来像一个整体（！有缺陷的）解决方案：

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