* all * hamiltonian 경로를 열거하십시오.

Question

이전에 질문을 받았지만 모든 게시물에서 답변을 찾지 못했습니다. 누군가 제발 나를 그래프에있는 모든 해밀턴 경로를 열거하는 알고리즘을 제안 해 주시겠습니까?

약간의 배경 : 각 해밀턴 경로를 나열하고 몇 가지 분석을하고 결과를 반환해야하는 문제에 대해 연구하고 있습니다. 이를 위해 가능한 모든 해밀턴 경로를 열거 할 수 있어야합니다.

감사합니다.

Answer 1

제안 된대로 BFS/DFS를 사용하지만 첫 번째 해결 방법에서는 중단하지 마십시오. BFS/DFS 기본 사용 (이 경우)은 모든 솔루션을 찾을 수 있습니다. 첫 번째 옵션에서 중지하려면 조건을 입력해야합니다.

Answer 2

내 자바 코드 (절대 재귀 법에 의한)

알고리즘 :

+가 볼 수있는 다른 지점에 연결 한 시점에서 시작 (경로를 형성한다).

+ 그래프의 모든 점을 연결할 때까지 경로를 제거하고 재귀 적으로 새로운 점에서 새 경로를 찾습니다. 캔트 최신 포인트

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

에서 해밀턴 경로를 형성하는 경우

+ 경로를 제거하고 초기 그래프에 철수.

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

Answer 4

솔루션 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)))