Покройте все ребра неориентированного графа с наименьшим количеством простых путей

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 в комментариях, обнаружение, что одного пути достаточно, - это проблема гамильтоновых путей , которая равна NP-Hard , и для них не существует известного алгоритма полиномовпроблемы.

Это дает вам 2 варианта:

1. Используйте эвристическое решение, которое не может быть оптимизировано.[пример алгоритма прилагается]
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

для второго варианта наивное решение о возврате будет

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!)), поэтому, хотя оно оптимально, оно не практично.