Changes between Version 19 and Version 20 of CaoCourseTme8

Timestamp:

May 1, 2007, 12:06:50 PM (18 years ago)

Author:

alain

Comment:

--

CaoCourseTme8

@@ -1 +1 @@
 {{{
 #!html
-<h1>TME 8 : Méthode de partitionnement de graphe  Min-Cut</h1>
+<h1>TME 8 : Méthode de partitionnement de graphe : Min-Cut</h1>
 }}}
 [[PageOutline]]
@@ -43 +43 @@
 = B) Algorithme !MinCut glouton = 
 
-On défini comme suit la fonction de coût du problème d'optimisation !MinCut:
+On défini comme suit la fonction de coût du problème d'optimisation !MinCut,
+dont la valeur dépend du nombre d'arcs qui traversent la frontière :
 {{{
 FC = Somme  Aij * Kij
@@ -73 +74 @@
 appartenant à R).
 
-On transfère la première cellule Ci de la liste ordonnée GAIN_L vers R,
-on met à jour les gains des cellules adjacentes à Ci, ainsi que l'ordre des
-listes GAIN_L et GAIN_R. La cellule Ci transférée dans R n'est pas rangée
+Un mouvement élémentaire consiste à échanger deux cellules i et j :
+ * une cellule i appartenant à l'ensemble R passe dans l'ensemble L
+ * une cellule j appartenant à l'ensemble L passe dans l'ensemble R
+
+La variation de la fonction de coût résultant du mouvement des cellules i et j
+peut être calculée de la façon suivante:
+{{{
+DFC(i<->j) = G(i) + G(j) - 2Aij
+}}}
+
+L'algorithme d'optimisation proposé est "glouton", car il n'y a pas de retour en arrière:
+Lorsqu'un mouvement a été accepté, les deux cellules déplacées i et j ne sont plus autorisées à bouger:
+
+On prend la cellule i appartenant à R possédant le gain G(i) maximum, et la cellule j appartenant à L possédant le gain G(j) maximum.
+On calcule la variation de la fonction de coût associé à l'échange i <-> j, et on accepte le mouvement
+tant que celui-ci n'entraîne une augmentation de la fonction de coût.
+
+Accepter un mouvement consiste à effectuer les actions suivantes:
+ * On transfère la première cellule i de la liste ordonnée GAIN_R vers L, on met à jour les gains des cellules adjacentes à i, ainsi que l'ordre des listes GAIN_L et GAIN_R. La cellule i transférée dans L n'est pas rangée
+dans GAIN_L, car elle n'est plus autorisée à bouger.
+ * On transfère la première cellule j de la liste ordonnée GAIN_L vers R, on met à jour les gains des cellules adjacentes à j, ainsi que l'ordre des listes GAIN_L et GAIN_R. La cellule j transférée dans R n'est pas rangée
 dans GAIN_R, car elle n'est plus autorisée à bouger.
-
-On transfère la première cellule Ci de la liste ordonnée GAIN_R vers L,
-on met à jour les gains des cellules adjacentes à Ci, ainsi que l'ordre des
-listes GAIN_L et GAIN_R. La cellule Ci transférée dans L n'est pas rangée
-dans GAIN_L, car elle n'est plus autorisée à bouger.
-
-On recommence les deux étapes ci-dessus tant que cet échange entraîne une
-diminution de la fonction de coût.
 
 = C) Structures de données =
@@ -275 +286 @@
 
  '''2. Ecriture de l'algorithme !MinCut glouton'''::
-       Complétez le programme main() en ajoutant
+       Complétez le programme main() en ajoutant la fonction mincut()
        la boucle réalisant les transferts de cellules tant que le transfert 
        d'une paire de cellules améliore la fonction de coût FC.