从"算法设计手册"中不了解最近对启发式

Question

几乎完全相同的问题.但是我仍然不明白,这种启发式工作原理是什么以及顶点通过的顺序是什么.书中还有一张图片:

这显示了最近neghbor启发式和我认为是最近对启发式的比较.从图片中我可以假设在顶部图片上,首先选择了0点,但是在底部图片上选择了最左边或最右边的一个.因为没有任何关于第一点选择的说法(也是最近对启发式没有做任何动作),我可以假设任何算法结果都不错,如果没有,它将不会给你底部图片考虑一下,从什么开始.

现在我只想知道,最近对启发式的步骤是什么.将理解类似于底部的图片,其具有与每次迭代相关联的数字以及解释.

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

Answer 1

我没有这本书,但它显示了最近邻启发法与该数据最优解的比较.此处显示的数据为(-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)是下一个最小边缘,依此类推,直到它到达最优解.

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

Answer 2

我同意这一点在书中不是很清楚(因为读者在我的版本中第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