dynamic-programming
Résolution de problèmes graphiques à l'aide de la programmation dynamique

Algorithme Floyd-Warshall

L'algorithme de Floyd-Warshall permet de trouver les chemins les plus courts dans un graphique pondéré avec des poids de bord positifs ou négatifs. Une seule exécution de l'algorithme trouvera les longueurs (poids additionnés) des plus courts chemins entre toutes les paires de sommets. Avec une petite variation, il peut imprimer le chemin le plus court et détecter les cycles négatifs dans un graphique. Floyd-Warshall est un algorithme de programmation dynamique.

Regardons un exemple. Nous allons appliquer l'algorithme de Floyd-Warshall sur ce graphique:

La première chose à faire est de prendre deux matrices 2D. Ce sont des matrices d'adjacence . La taille des matrices va être le nombre total de sommets. Pour notre graphique, nous prendrons 4 * 4 matrices. La distance Matrix va stocker la distance minimale trouvée entre deux sommets. Au début, pour les arêtes, s'il y a un bord entre uv et la distance / poids est w , nous allons stocker: distance[u][v] = w . Pour tous les bords qui n'existent pas, nous allons mettre l' infini . La matrice de chemin sert à régénérer le chemin de distance minimum entre deux sommets. Donc, au départ, s'il y a un chemin entre u et v , nous allons mettre le path[u][v] = u . Cela signifie que la meilleure façon d’arriver à vertex-v à partir de vertex-u est d’utiliser l’arête qui connecte v avec u . S'il n'y a pas de chemin entre deux sommets, nous allons y mettre N indiquant qu'il n'y a pas de chemin disponible maintenant. Les deux tableaux de notre graphique ressembleront à:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Comme il n'y a pas de boucle, les diagonales sont définies sur N. Et la distance du sommet lui-même est 0 .

Pour appliquer l'algorithme de Floyd-Warshall, nous allons sélectionner un sommet médian k . Ensuite, pour chaque sommet i , nous allons vérifier si nous pouvons aller de i à k , puis de k à j , où j est un autre sommet et minimiser le coût de passer de i à j . Si la distance actuelle [i] [j] est supérieure à la distance [i] [k] + distance [k] [j] , nous allons mettre la distance [i] [j] égale à la somme de ces deux distances . Et le chemin [i] [j] sera mis au chemin [k] [j] , car il vaut mieux aller de i à k , puis k à j . Tous les sommets seront sélectionnés comme k . Nous aurons 3 boucles imbriquées: pour k allant de 1 à 4, je passe de 1 à 4 et j va de 1 à 4. Nous allons vérifier:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Donc, ce que nous vérifions en fait, c'est que pour chaque paire de sommets, la distance est-elle plus courte en passant par un autre sommet? Le nombre total d'opérations pour notre graphique sera 4 * 4 * 4 = 64 . Cela signifie que nous allons faire cette vérification 64 fois. Regardons quelques-unes d'entre elles:

Lorsque k = 1 , i = 2 et j = 3 , la distance [i] [j] est -2 , ce qui n’est pas supérieur à la distance [i] [k] + distance [k] [j] = -2 + 0 = -2 . Donc, il restera inchangé. Là encore, lorsque k = 1 , i = 4 et j = 2 , la distance [i] [j] = infini , qui est supérieure à la distance [i] [k] + distance [k] [j] = 1 + 3 = 4 . On met donc la distance [i] [j] = 4 et on met le chemin [i] [j] = chemin [k] [j] = 1 . Cela signifie que pour aller du sommet 4 au sommet 2 , le chemin 4-> 1> 2 est plus court que le chemin existant. C'est ainsi que nous remplissons les deux matrices. Le calcul pour chaque étape est indiqué ici . Après avoir apporté les modifications nécessaires, nos matrices ressembleront à ceci:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

C'est notre matrice de distance la plus courte. Par exemple, la distance la plus courte entre 1 et 4 est 3 et la distance la plus courte entre 4 et 3 est 2 . Notre pseudo-code sera:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Imprimer le chemin:

Pour imprimer le chemin, nous allons vérifier la matrice Path . Pour imprimer le chemin de u à v , nous allons commencer par le chemin [u] [v] . Nous allons continuer à changer v = path [u] [v] jusqu'à ce que nous trouvions le chemin [u] [v] = u et poussez toutes les valeurs du chemin [u] [v] dans une pile. Après avoir trouvé u , nous allons imprimer u et commencer à extraire des éléments de la pile et les imprimer. Cela fonctionne parce que la matrice de chemin stocke la valeur du sommet qui partage le plus court chemin vers v depuis n'importe quel autre nœud. Le pseudo-code sera:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Trouver un cycle de bord négatif:

Pour savoir s'il existe un cycle de front négatif, nous devons vérifier la diagonale principale de la matrice de distance . Si une valeur sur la diagonale est négative, cela signifie qu'il y a un cycle négatif dans le graphique.

Complexité:

La complexité de l'algorithme de Floyd-Warshall est O (V³) et la complexité de l'espace est: O (V²) .

Couverture minimum de vertex

Minimum Vertex Cover est un problème graphique classique. Disons que dans une ville, nous avons quelques routes reliant quelques points. Représentons les routes en utilisant les arêtes et les points en utilisant des nœuds. Prenons deux exemples de graphiques:

Nous voulons placer des gardiens sur certains points. Un gardien peut garder toutes les routes reliées au point. Le problème est le suivant: quel est le nombre minimum de gardiens nécessaires pour couvrir toutes les routes? Si nous installons des gardes aux nœuds A , B , H , I et J , nous pouvons couvrir toutes les routes.

C'est notre solution optimale. Nous avons besoin d'au moins 5 gardiens pour garder la ville entière. Comment déterminer cela?

Au début, nous devons comprendre qu'il s'agit d'un problème NP-difficile , c'est-à-dire que le problème n'a pas de solution temporelle polynomiale. Mais si le graphe était un arbre , cela signifie que s'il avait (n-1) nœuds où n est le nombre d'arêtes et qu'il n'y a pas de cycle dans le graphe, nous pouvons le résoudre en utilisant la programmation dynamique.

Pour construire une solution DP, nous devons suivre deux stratégies:

1. S'il n'y a pas de gardien dans un nœud, tous les nœuds qui y sont connectés doivent avoir un gardien ou toutes les routes ne seront pas couvertes. Si u et v sont connectés et u n'a pas de gardien, alors v doit avoir un gardien.
2. S'il y a un gardien dans un nœud, un autre nœud connecté peut ou non avoir un gardien. Cela signifie qu'il n'est pas nécessaire d'avoir un gardien, mais cela peut être bénéfique. Si u et v sont connectés et que vous avez un veilleur, nous allons vérifier et trouver ce qui est bénéfique pour nous:
   • Réglage du gardien dans v .
   • Ne pas placer de gardien dans le v .

Définissons une fonction récursive avec l'état étant le nœud actuel dans lequel nous sommes et si elle a un gardien ou non. Ici:

F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.

La fonction retournera le nombre de gardien dans les nœuds restants.

Prenons un exemple d'arbre:

Nous pouvons facilement dire que si nous ne mettons pas de gardien sur le nœud- A , nous devrons placer des gardiens sur le nœud B , C et D. Nous pouvons en déduire:

F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0

Il nous renvoie le nombre de gardiens nécessaires si nous ne mettons pas de gardien dans le nœud- A . Nous avons ajouté 0 à la fin parce que nous n'avons défini aucun gardien dans notre nœud actuel.

Maintenant, F(A,1) signifie que nous avons placé le gardien dans le nœud- A . Pour cela, nous pouvons soit définir des surveillants dans tous les nœuds connectés, soit nous ne le faisons pas. Nous prendrons celui qui nous fournit le nombre minimum de gardiens.

F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1

Nous vérifions en définissant et en ne définissant pas de gardien sur chaque nœud et en prenant la valeur optimale.

Une chose que nous devons faire attention, une fois que nous allons au nœud enfant, nous ne reviendrons jamais sur le nœud parent. De l'exemple ci-dessus, nous sommes passés à B de A , donc parent [B] = A. Donc, nous ne retournerons pas à A de B.

Pour déterminer le cas de base, nous pouvons remarquer que si nous ne pouvons pas accéder à un autre nouveau nœud depuis un nœud, nous retournerons 1 s'il y a un gardien dans notre nœud actuel, 0 s'il n'y a pas de gardien dans notre courant. nœud.

Il est préférable d'avoir une liste de contiguïté pour notre arbre. Laissez la liste être notée par le bord . Nous aurons un tableau dp [n] [2] , où n désigne le nombre de nœuds pour stocker les valeurs calculées et l'initialiser avec -1 . Nous aurons également un tableau parent [n] pour désigner la relation parent-enfant entre les nœuds. Notre pseudo-code ressemblera à:

Procedure f(u, isGuarded):
if edge[u].size is equal to 0                    //node doesn't have any new edge
    Return isGuarded
else if dp[u][isGuarded] is not equal to -1      //already calculated
    Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
    v := edge[u][i]
    if v is not equal to parent[u]               //not a parent
        parent[v] := u
        if isGuarded equals to 0                 //not guarded, must set a watchman
            sum := sum + f(v,1)
        else                                     //guarded, check both
            sum := sum + min(f(v,1), f(v,0)
        end if
    end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]

Si nous notons le nœud- A comme racine, nous appellerons la fonction par: min(f(A,1), f(A,0)) . Cela signifie que nous vérifierons également s'il est optimal de définir ou non le gardien dans le nœud racine. C'est notre solution DP. Ce problème peut également être résolu en utilisant l'algorithme de correspondance maximale ou max-flow.