Enumerar * todos * caminos hamiltonianos

Question

Sé que esto se ha preguntado antes, pero no encontré su respuesta en ninguna de las publicaciones. ¿Puede alguien sugerirme un algoritmo que enumera TODOS los caminos hamiltonianos en un gráfico?

Un poco de historia: Estoy trabajando en un problema en el que tengo que enumerar cada ruta hamiltoniana, hacer un análisis y devolver el resultado. Para eso, necesito poder enumerar todos los posibles caminos hamiltonianos.

Gracias.

Answer 1

Utilice BFS/DFS según lo sugerido pero no se detenga en la primera solución. El uso primario de BFS/DFS (en este caso) será encontrar toda la solución, debe ponerle una condición para detenerse en la primera.

Answer 2

Mi código Java: (absolutamente basado en el método recursivo)

algoritmo:

+ comienzan en 1 punto conectarse a otro punto que se puede ver (para formar un camino).

+ eliminar la ruta y encontrar recursivamente una nueva ruta en el punto más nuevo hasta conectar todos los puntos del gráfico.

+ eliminar la ruta y retroceder a la gráfica inicial si no puede formar ruta Hamilton desde el más reciente punto de

public class HamiltonPath { 
public static void main(String[] args){ 
    HamiltonPath obj = new HamiltonPath(); 

    int[][]x = {{0,1,0,1,0}, //Represent the graphs in the adjacent matrix forms 
       {1,0,0,0,1}, 
       {0,0,0,1,0}, 
       {1,0,1,0,1}, 
       {0,1,0,1,0}}; 

    int[][]y = {{0,1,0,0,0,1}, 
       {1,0,1,0,0,1}, 
       {0,1,0,1,1,0}, 
       {0,0,1,0,0,0}, 
       {0,0,1,0,0,1}, 
       {1,1,0,0,1,0}}; 

    int[][]z = {{0,1,1,0,0,1}, 
       {1,0,1,0,0,0}, 
       {1,1,0,1,0,1}, 
       {0,0,1,0,1,0}, 
       {0,0,0,1,0,1}, 
       {1,0,1,0,1,0}}; 

    obj.allHamiltonPath(y); //list all Hamiltonian paths of graph 
    //obj.HamiltonPath(z,1); //list all Hamiltonian paths start at point 1 


} 

static int len; 
static int[]path; 
static int count = 0;  

public void allHamiltonPath(int[][]x){ //List all possible Hamilton path in the graph 
    len = x.length; 
    path = new int[len]; 
    int i; 
    for(i = 0;i<len;i++){ //Go through column(of matrix) 
     path[0]=i+1; 
     findHamiltonpath(x,0,i,0); 
    } 
} 

public void HamiltonPath(int[][]x, int start){ //List all possible Hamilton path with fixed starting point 
    len = x.length; 
    path = new int[len]; 
    int i; 
    for(i = start-1;i<start;i++){ //Go through row(with given column) 
     path[0]=i+1; 
     findHamiltonpath(x,0,i,0); 
    } 
} 

private void findHamiltonpath(int[][]M,int x,int y,int l){ 

    int i; 
     for(i=x;i<len;i++){   //Go through row 

      if(M[i][y]!=0){  //2 point connect 

       if(detect(path,i+1))// if detect a point that already in the path => duplicate 
        continue; 

       l++;   //Increase path length due to 1 new point is connected 
       path[l]=i+1; //correspond to the array that start at 0, graph that start at point 1 
       if(l==len-1){//Except initial point already count =>success connect all point 
        count++; 
        if (count ==1) 
       System.out.println("Hamilton path of graph: "); 
        display(path); 
        l--; 
        continue; 
       } 

       M[i][y]=M[y][i]=0; //remove the path that has been get and 
       findHamiltonpath(M,0,i,l); //recursively start to find new path at new end point 
       l--;    // reduce path length due to the failure to find new path   
       M[i][y] = M[y][i]=1; //and tranform back to the inital form of adjacent matrix(graph) 
      } 
    }path[l+1]=0; //disconnect two point correspond the failure to find the.. 
}      //possible hamilton path at new point(ignore newest point try another one)   

public void display(int[]x){ 

    System.out.print(count+" : "); 
    for(int i:x){ 
     System.out.print(i+" "); 
    } 
     System.out.println(); 
} 

private boolean detect(int[]x,int target){ //Detect duplicate point in Halmilton path 
    boolean t=false;       
    for(int i:x){ 
     if(i==target){ 
      t = true; 
      break; 
     } 
    } 
    return t; 
} 

}

Answer 3

Una búsqueda exhaustiva primero en profundidad que da la respuesta. Acabo de terminar un reportaje sobre una aplicación Java para este problema (con el código):

http://puzzledraccoon.wordpress.com/2012/06/07/how-to-cool-a-data-center/

Answer 4

Solución en python3:

def hamiltonians(G, vis = []): 
    if not vis: 
     for n in G: 
      for p in hamiltonians(G, [n]): 
       yield p 
    else: 
     dests = set(G[vis[-1]]) - set(vis) 
     if not dests and len(vis) == len(G): 
      yield vis 
     for n in dests: 
      for p in hamiltonians(G, vis + [n]): 
       yield p 
G = {'a' : 'bc', 'b' : 'ad', 'c' : 'b', 'd' : 'ac'} 
print(list(hamiltonians(G)))