Optimisations pour le problème de chemin le plus long dans le graphe cyclique

Question

Quelles optimisations existent pour essayer de trouver le chemin le plus long dans un graphe cyclique?

Le plus long chemin dans les graphes cycliques est connu pour être NP-complet. Quelles optimisations ou heuristiques peuvent vous permettre de trouver le chemin le plus long plus rapidement que DFS le graphique entier? Y a-t-il des approches probabilistes?

J'ai un graphique avec des qualités spécifiques, mais je cherche une réponse à cela dans le cas général. Lier aux papiers serait fantastique. Voici une réponse partielle:

1. Confirmez qu'il est cyclique. Le plus long chemin dans les graphes acycliques est facilement calculé en utilisant la programmation dynamique. Déterminez si le graphe est planaire (quel est le meilleur algorithme?). Si c'est le cas, vous pouvez voir s'il s'agit d'un graphe de blocs, d'un graphe ptolemaic ou d'un graphique de cactus et appliquer les méthodes trouvées dans this paper. Pour connaître le nombre de cycles simples, utilisez Donald B Johnson's algorithm (Java implementation). Vous pouvez transformer n'importe quel graphique cyclique en un graphique acyclique en supprimant un bord dans un cycle simple. Vous pouvez ensuite exécuter la solution de programmation dynamique trouvée sur the Wikipedia page. Pour être complet, vous devez faire N fois pour chaque cycle, où N est la longueur du cycle. Ainsi, pour un graphe entier, le nombre de fois que vous devez exécuter la solution DP est égal au produit des longueurs de tous les cycles.

2. Si vous devez DFS le graphe entier, vous pouvez élaguer certains chemins en calculant à l'avance l '"atteignabilité" de chaque noeud. Cette accessibilité, qui est principalement applicable aux graphes orientés, est le nombre de nœuds que chaque nœud peut atteindre sans répétitions. C'est le maximum que le plus long chemin de ce nœud pourrait être. Avec cette information, si votre chemin actuel plus l'accessibilité du nœud enfant est inférieur au plus long que vous avez déjà trouvé, il est inutile de prendre cette branche car il est impossible que vous trouviez un chemin plus long.

Answer 1

Voici un O (n * 2^n) approche de programmation dynamique qui devrait être possible jusqu'à dire 20 sommets:

m(b, U) = la longueur maximale d'un chemin qui se termine à b et visiter seulement (certains des) sommets dans U. Pour commencer, définissez m(b, {b}) = 0.

Ensuite, m(b, U) = valeur maximale de m(x, U - x) + d(x, b) sur tous x dans U tels que x n'est pas b et un bord (x, b) existe. Prenez le maximum de ces valeurs pour tous les points d'extrémité b, avec U = V (l'ensemble complet des sommets). Ce sera la longueur maximale de n'importe quel chemin.

Le code C suivant suppose une matrice de distance au d[N][N]. Si votre graphique n'est pas pondéré, vous pouvez modifier chaque accès en lecture de ce tableau à la constante 1. Un retraçage montrant une séquence optimale de sommets (il peut y en avoir plus d'un) est également calculé dans le tableau 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; 
} 

Sur mon PC, cela résout un graphe complet de 20x20 avec des poids de pointe choisis au hasard dans l'intervalle [0, 1000) dans environ 7 s et a besoin d'environ 160 Mo (la moitié est de la trace prédécesseur).

(S'il vous plaît, pas de commentaires sur l'utilisation de tableaux de taille fixe. Utilisez malloc() (ou mieux encore, C++ vector<int>) dans un programme réel. Je viens d'écrire cette façon si les choses seraient plus claires.)