0

我必须使用联合查找算法来解决旅行商问题。除了我刚刚发现的一个问题外，我几乎完成了它。当它处理每条边时，它会检查一个循环，这是对整个父数组的事情完成的。问题是，当它到达我需要添加的最后一条边才能完成问题时，由于技术上是一个循环，它不会添加边，因此无法完成路径。我如何区分无用的循环和表明我们已经完成的循环？

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

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,
4

1 回答 1

1

如何跟踪每个集合的大小？

然后，在进行联合时，如果两者的根相同（即循环）并且根的大小等于问题中所有点的总和，则包括该边并停止，否则照常继续。

警告：

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

阐述：

您的Union问题应该类似于：（源自Wikipedia）
（返回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

（正确的合并（为了提高效率）有点复杂 - 你应该比较深度并选择最深的作为父级，有关详细信息，请参阅 Wikipedia）

现在，我的建议：

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为真）和xRoot.size(3)!= pointCount(4)，因此我们返回假（不添加边）。

联合3和4：

4
4
|
3
3
|
1
2
|
2
1

联合4和1：

公共根是4（因此xRoot == yRoot为真）和xRoot.size(4)== pointCount(4)，因此我们返回真（添加边）并设置标志以指示我们完成了。

于 2013-10-13T17:55:16.127 回答