algorithm - 用最少的简单路径覆盖无向图的所有边

Question

给定一个无向图 G，我想用最少的简单路径覆盖所有边。

例如，对于这样的图，

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

A--C--D--F--G, B--C--D--F--E 是最优解，而 A--C --D--F--G 、 B--C 、 E--F 不是。

有什么算法吗？

Answer 1

正如@RafalDowgird 在评论中所说，查找一条路径是否足够是 Hamiltonian Path Problem ，即 NP-Hard ，并且对于这些问题没有已知的多项式算法。

这给您留下了 2 个选择:

1. 使用可能未优化的启发式解决方案。 [附示例算法]
2. 使用指数解，例如backtracking

对于选项一，您可以尝试贪婪的解决方案:

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

对于选项二，一个朴素的回溯解决方案是

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!))，因此虽然它是最优的，但并不实用。