단순 경로 수가 가장 적은 무향 그래프의 모든 가장자리를 덮으십시오.

Question

무향 그래프 G가 주어지면 모든 가장자리를 간단한 경로로 최소화하고 싶습니다. A--C--D--F--G , B--C , E--F없는 반면 예

이 같은 그래프,

B  E 
    |  | 
A--C--D--F--G 

A--C--D--F--G, B--C--D--F--E, 최적의 솔루션이다.

모든 알고리즘은 무엇입니까?

Answer 1

@RafalDowgird가 설명한 바와 같이 한 경로가 충분하면 Hamiltonian Path Problem 인 NP-Hard이며 이러한 문제에 대한 알려진 다항식 알고리즘은 없습니다.

1. 사용 heuristical 솔루션, 최적화되지 않을 수 있습니다

   이 2 옵션을 남긴다.

   while (graph is not covered): 
       pick arbitrary 2 connected not covered vertices v1,v2 
       if there are none matching: 
        choose an arbitrary not covered vertex 
        add an arbitrary path starting from this vertex 
       else: 
        choose the longest simple path from v1 to v2 [can be found with BFS/DFS] 
        add this path 
   

   옵션이의 순진 되돌아 솔루션

   될 것입니다 : 당신이 욕심이 솔루션을 시도해 볼 수도 있습니다, [예 알고리즘은 첨부]
2. 사용 지수 솔루션 등 backtracking 옵션 하나

로

1. find P={all possible paths} 
2. create S=2^P //the power set of P 
3. chose s in S such that for each s' in S: |s| <= |s'| and both s,s' cover all vertices. 

이 솔루션은 O(2^(n!))이므로 최적화 된 것이지만 실용적이지 않습니다.