联合发现解决旅游推销员问题

Question

我不得不用联合查找算法来解决旅行商问题。除了我刚刚发现的一个问题外，我几乎把它做好了。当它处理每个边缘时，它将检查是否有一个循环，这是用整个父数组来完成的。问题是，当它到达最后一个边时，我需要添加来完成这个问题，因为它在技术上是一个循环，它没有添加边缘，所以路径不能完成。我如何区分无用的循环和我们已经完成的循环？

这是我到目前为止得到的代码

private int[] parent; //parent of each vertex
private int[] connection; //number of edges coming from a given vertex
private int[] subsize; //size of each subtree
boolean donepath;

public void GreedyAlgo(){
    ArrayList<Edge> newedges = new ArrayList<Edge>();
    for(int i = 0; i<graph.realedge.size();i++){
        if(donepath) break;
        Edge e= graph.realedge.get(i);
        int x = e.in1;
        int y = e.in2;


        if(unionFind(x,y) && !thirdEdge(x,y)){

            newedges.add(e);



        }

        else{

        }

    }
}


 public int findParent(int i){
    if (parent[i] != i)
       return findParent(parent[i]);
    return parent[i];

}

public boolean unionFind(int x, int y){
     int xx = findParent(x);
     int yy = findParent(y);

    if(xx == yy){

            if(subsize[xx]== n){
                donepath = true;
                return true;
            }
            return false;
    }
     else{

        if( subsize[xx] < subsize[yy]){
             parent[xx] = yy;
                              subsize[yy]+=subsize[xx];
         }
        else if( subsize[xx] >  subsize[yy]){
             parent[yy] = xx;  subsize[xx]+=subsize[yy];
         }
         else{
             parent[yy] = xx;
             subsize[xx]+=subsize[yy];
         } 
        connection[x]++;
        connection[y]++;

     }


    return true;


}

public boolean makesCycle(int x, int y){
        int xx = findParent(x);
        int yy = findParent(y);

        if(xx == yy){

            return true;
        }

    return false;
}

这是按顺序排列的边缘。

0-0,
1-1,
2-2,
3-3,
4-4,
0-4 should get added,
2-3 should get added,
3-2,
4-0,
0-1 should get added,
0-2 ,
0-3,
1-0,
1-4,
2-0,
3-0,
4-1,
1-3 should get added,
3-1,
2-4 should get added......but doesnt,
3-4,
4-2,
4-3,
1-2,
2-1,

Answer 1

跟踪每一组的大小如何？

然后，当进行合并时，如果两者的根是相同的(即一个循环)，并且根的大小等于问题中所有点的和，则包含该边和停止，否则就像往常一样继续。

警告：

请注意，简单的Union-Find实现可能会以最小生成树而不是哈密顿循环结束。你需要确保你选择合适的边缘--我假设你已经弄清楚了，或者，如果没有，我就留给你。

精化：

解决问题的Union应该如下所示：(从维基百科派生)

(返回false或true以指示是否应该添加边缘)

boolean Union(x, y)
   xRoot = Find(x)
   yRoot = Find(y)
   if xRoot == yRoot
      return false
   // merge xRoot and yRoot
   xRoot.parent = yRoot
   return true

(正确的合并(为了提高效率)要复杂一些--您应该比较深度，并选择最深的一个作为父级，详细信息请参见维基百科。

现在，我的建议：

为每个节点创建一个size变量，初始化为1，然后创建Union函数：

boolean Union(x, y)
   xRoot = Find(x)
   yRoot = Find(y)

   if xRoot == yRoot
      // check if it's the last node
      if xRoot.size == pointCount
         done = true
         return true
      else
         return false

   // merge xRoot and yRoot
   xRoot.parent = yRoot
   yRoot.size += xRoot.size
   return true

示例：

点数：

1---2
|\  |
| \ |
|  \|
4---3

有4点，因此pointCount = 4

开始：(size出现在节点下)

1  2  3  4
1  1  1  1

联合1和2

1  3  4
2  1  1
|
2
1

联合3和2

3  4
3  1
|
1
2
|
2
1

联合3和1

常见的根是3 (因此xRoot == yRoot为true)和xRoot.size(3) != pointCount(4)，因此我们返回false (不要添加边缘)。

联合3和4

4
4
|
3
3
|
1
2
|
2
1

联合4和1

常见的根是4 (因此xRoot == yRoot是真)和xRoot.size(4) == pointCount(4)，因此我们返回true (添加边缘)，并设置标志来表示我们完成了。