Union Найти, чтобы решить Traveling Salesman

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

насчет отслеживания размера каждого из множеств?

Затем, когда выполняется объединение, если корень обоих одинаковый (то есть цикл), а размер корня равен сумме всех точек в вашей проблеме, включите этот край и остановите, в противном случае продолжайте, как обычно ,

Предупреждение:

Обратите внимание, что простая реализация союзной Найти, вероятно, закончится вас с minimum spanning tree, а не hamiltonian cycle. Вам нужно убедиться, что вы выбрали подходящие края - я предполагаю, что вы это поняли, или, если нет, я оставлю это вам.

Разработка:

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 

(правильное слияние (для эффективности) немного сложнее - вы должны сравнить глубины и выбрать самый глубокий из них как родительский, см. Википедию).

Теперь мое предложение:

Создать 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), таким образом, мы возвращает истину (добавить край), и мы установили флаг, указывающий, что мы закончили.