Алгоритм графика: Подобно TSP

Question

Я хочу решить проблему, похожую на TSP (проблема с продавцом).

У меня есть N (N> 0, N < 20) узлов, и я должен посетить все узлы.

Стоимость между узлами равна.

Я могу посетить узел неограниченное количество раз.

Я хочу найти более одного пути, и стоимость не имеет ограничений.

Скажите, пожалуйста, какие-нибудь эффективные алгоритмы об этой проблеме?

Answer 1

Почему бы не просто запустить DFS? O(V + E)

Несколько путей можно получить, запустив алгоритм из разных корней.

bool[] visited; 
List<int> path; 
void Visit(int u) 
{ 
    if (visited[u]) return; // only visit each node once 
    visited[u] = true; 
    path.Add(u); // add initially to path 
    int pathSize = path.Count; 
    foreach(int v in nbs[u]) { 
     Visit(v); 
     if(path.Count > pathSize) 
     { 
      // if another node was visited, add this node again 
      // so we can move to the next unvisited subtree 
      path.Add(u); 
      pathSize = path.Count; 
     } 
    } 
} 

• Начиная с 1: 1> 2> 1> 3> 4> 3> 1
• Начиная от 2: 2> 1> 3> 4> 3> 1> 2

Вы также можете обновить алгоритм, он заканчивается в тот момент, посещают последний узел.