Optimizaciones para el problema de ruta más larga en el gráfico cíclico

Question

¿Qué optimizaciones existen para tratar de encontrar la ruta más larga en un gráfico cíclico?

La ruta más larga en los gráficos cíclicos se sabe que es NP-completa. ¿Qué optimizaciones o heurística pueden hacer que encontrar el camino más largo sea más rápido que DFSing el gráfico completo? ¿Hay algún enfoque probabilístico?

Tengo un gráfico con cualidades específicas, pero estoy buscando una respuesta a esto en el caso general. Vincular a los documentos sería fantástico. Aquí hay una respuesta parcial:

1. Confirmar que es cíclica. La ruta más larga en gráficos acíclicos se calcula fácilmente mediante programación dinámica.

2. Averiguar si el gráfico es plano (¿qué algoritmo es el mejor?). Si es así, puede ver si se trata de un gráfico de bloques, un gráfico ptolemaico o un gráfico de cactus y aplicar los métodos que se encuentran en this paper.

3. Descubre cuántos ciclos simples hay usando Donald B Johnson's algorithm (Java implementation). Puede cambiar cualquier gráfico cíclico en uno acíclico eliminando un borde en un ciclo simple. A continuación, puede ejecutar la solución de programación dinámica que se encuentra en the Wikipedia page. Para completar, tendrías que hacer esto N veces para cada ciclo, donde N es la duración del ciclo. Por lo tanto, para un gráfico completo, el número de veces que tiene que ejecutar la solución DP es igual al producto de las longitudes de todos los ciclos.

4. Si tiene que DFS todo el gráfico, puede podar algunas rutas calculando la "accesibilidad" de cada nodo de antemano. Esta accesibilidad, que se aplica principalmente a los gráficos dirigidos, es la cantidad de nodos que cada nodo puede alcanzar sin repeticiones. Es el máximo que puede ser el camino más largo desde ese nodo. Con esta información, si su ruta actual más la accesibilidad del nodo hijo es menor que la más larga que haya encontrado, no tiene sentido tomar esa rama ya que es imposible que encuentre una ruta más larga.

Answer 1

Aquí es un O (n * 2^n) enfoque de programación dinámica que debe ser factible para hasta decir 20 vértices:

m(b, U) = la longitud máxima de cualquier ruta que termina en b y visitar solamente (algunos de) los vértices en U.

Inicialmente, configure m(b, {b}) = 0.

Entonces, m(b, U) = valor máximo de m(x, U - x) + d(x, b) sobre toda x en U tal que x no es b y un borde (x, b) existe. Tome el máximo de estos valores para todos los puntos finales b, con U = V (el conjunto completo de vértices). Esa será la longitud máxima de cualquier camino.

El siguiente código C supone una matriz de distancia en d[N][N]. Si su gráfico no está ponderado, puede cambiar cada acceso de lectura a esta matriz a la constante 1. Una traza que muestra una secuencia óptima de vértices (puede haber más de uno) también se calcula en la matriz p[N][NBITS].

#define N 20 
#define NBITS (1 << N) 

int d[N][N];  /* Assumed to be populated earlier. -1 means "no edge". */ 
int m[N][NBITS]; /* DP matrix. -2 means "unknown". */ 
int p[N][NBITS]; /* DP predecessor traceback matrix. */ 

/* Maximum distance for a path ending at vertex b, visiting only 
    vertices in visited. */ 
int subsolve(int b, unsigned visited) { 
    if (visited == (1 << b)) { 
     /* A single vertex */ 
     p[b][visited] = -1; 
     return 0; 
    } 

    if (m[b][visited] == -2) { 
     /* Haven't solved this subproblem yet */ 
     int best = -1, bestPred = -1; 
     unsigned i; 
     for (i = 0; i < N; ++i) { 
      if (i != b && ((visited >> i) & 1) && d[i][b] != -1) { 
       int x = subsolve(i, visited & ~(1 << b)); 
       if (x != -1) { 
        x += d[i][b]; 
        if (x > best) { 
         best = x; 
         bestPred = i; 
        } 
       } 
      } 
     } 

     m[b][visited] = best; 
     p[b][visited] = bestPred; 
    } 

    return m[b][visited]; 
} 

/* Maximum path length for d[][]. 
    n must be <= N. 
    *last will contain the last vertex in the path; use p[][] to trace back. */ 
int solve(int n, int *last) { 
    int b, i; 
    int best = -1; 

    /* Need to blank the DP and predecessor matrices */ 
    for (b = 0; b < N; ++b) { 
     for (i = 0; i < NBITS; ++i) { 
      m[b][i] = -2; 
      p[b][i] = -2; 
     } 
    } 

    for (b = 0; b < n; ++b) { 
     int x = subsolve(b, (1 << n) - 1); 
     if (x > best) { 
      best = x; 
      *last = b; 
     } 
    } 

    return best; 
} 

En mi PC, esto resuelve un gráfico completo 20x20 con pesos de las aristas elegidas aleatoriamente en el intervalo [0, 1000) en aproximadamente 7S y necesita alrededor de 160 MB (medio de que es para la traza predecesor).

(Por favor, no hay comentarios acerca de la utilización de matrices de tamaño fijo. Utilice malloc() (o mejor aún, C++ vector<int>) en un programa real. Acabo de escribir de esta manera para que las cosas serían más claro.)