à quoi correspond les * dans cet algorithme ?

Question

Bonjour tout le monde,

J'ai un algorithme ci-dessous qui n'est pas très compliqué mais je ne comprends pas à quoi correspond l'* que l'on retrouve dans ce dernier :

POUR TOUT i ALLANT DE 1 A N FAIRE
  Rechercher j*, pour lequel Ci,j* est minimal dans la ligne i
  SI Ci,j* > 0 ALORS
    e = Ci,j*
    POUR TOUT j ALLANT DE 1 A N FAIRE
      Ci,j = Ci,j - e
    FIN POUR j
  FIN SI
FIN POUR i
POUR TOUT j ALLANT DE 1 A N FAIRE
  Rechercher i*, pour lequel Ci*,j est minimal dans la colonne j
  e = Ci*,j
  POUR TOUT i ALLANT DE 1 A N FAIRE
    Ci,j = Ci,j - e
  FIN POUR i
FIN POUR j

Merci d'avance pour votre aide.

beegees

cs_Jack · Answer

Salut
Faudrait poser la question à l'auteur de ce document.
Cela ne correspond pas à une notation liée à un langage.
Voir si, en bas du document, il n'y aurait pas une étoile avec un rappel ou une annotation. Peut-être que l'auteur précise le type de variable à utiliser ou ses limites ... 

Vala
Jack, MVP VB
NB : Je ne répondrai pas aux messages privés

<hr />Le savoir est la seule matière qui s'accroit quand on la partage (Socrate)

beegeezzz · Answer

Salut Jack, Merci pour ta réponse. J'ai demandé à un ami qui est avec moi en classe, voici sa réponse : je crois qu'il s'agit de la valeur plafond ou alors de la valeur Optimale Optimum est défini par *(Optimum) Voici l'énoncé complet mais je ne pense pas que le * soit informatif : Minimisation des coûts d'affectation dans le cadre d'une bijection Données initiales

On dispose de N unités de traitement : Ui : unité i, où i >= 1 et i <= N

On dispose du même nombre de postes à pourvoir : Pj : poste j , où j > = 1 et j <= N

On connaît également les coûts d'affectation des unités aux différents postes : Ci,j : coût d'affectation de l'unité i au poste j , où i > = 1 et i <= N, j >= 1 et j <= N et où Ci,j >= 0

Structure du fichier N U1 . . . Ui . . . UN P1 . . . Pj . . . PN C1,1 ... C1,j ... C1,N . . . . . . . . . Ci,1 ... Ci,j ... Ci,N . . . . . . . . . CN,1 ... CN,j ... CN,N Problème Il faut arriver à affecter une et une seule unité à chaque poste, et un et un seul poste à chaque unité, en minimisant les coûts d'affectation :

Soit Xi,j, une variable booléenne indiquant si l'on affecte ou non l'unité i au poste j , où i > = 1 et i <= N, j >= 1 et j <= N, et où Xi,j € {0,1}

Contraintes d'affectation des unités : Pour tout i € {1..N} : Somme(j € {1..N} | Xi,j) = 1

Contraintes d'affectation des postes : Pour tout j € {1..N} : Somme(i € {1..N} | Xi,j) = 1

Fonction d'optimisation : Min(X | Somme(i € {1..N}, j € {1..N} | Ci,j . Xi,j) )

Méthode

Création initiale de zérosPOUR TOUT i ALLANT DE 1 A N FAIRE Rechercher j*, pour lequel Ci,j* est minimal dans la ligne i SI Ci,j* > 0 ALORS e = Ci,j* POUR TOUT j ALLANT DE 1 A N FAIRE Ci,j = Ci,j - e FIN POUR j FIN SI FIN POUR i POUR TOUT j ALLANT DE 1 A N FAIRE Rechercher i*, pour lequel Ci*,j est minimal dans la colonne j e = Ci*,j POUR TOUT i ALLANT DE 1 A N FAIRE Ci,j = Ci,j - e FIN POUR i FIN POUR j

Recherche d'affectation Soit AUi un indicateur booléen (0,1) d'affectation de l'unité i, et APj un indicateur booléen (0,1) d'affectation du poste j. Soit NA le nombre d'affectations réalisées, A un indicateur booléen pour savoir si au moins une affectation a été réalisée. Soit HIi et HJj le marquage booléen des lignes et colonnes du tableau C selon «l'Algorithme Hongrois». TANT QUE la solution optimale n'est pas trouvée FAIRE Marquer toute affectation à zéro : Xi,j = 0 AUi = 0 APj = 0 NA = 0 REPETER A = 0 POUR TOUT i ALLANT DE 1 A N FAIRE SI AUi = 0 ALORS Rechercher j*, pour lequel Ci,j* 0, APj* 0 et pour lequel, pour tout j € {1..N} et j <> j* et APj = 0, Ci,j <> 0 SI j* existe ALORS AUi = 1 APj* = 1 Xi,j* = 1 NA = NA + 1 A = 1 FIN SI FIN SI FIN POUR i POUR TOUT j ALLANT DE 1 A N FAIRE SI APj = 0 ALORS Rechercher i*, pour lequel Ci*,j 0, AUi* 0 et pour lequel, pour tout i € {1..N} et i <> i* et AUi = 0, Ci,j <> 0 SI i* existe ALORS AUi* = 1 APj = 1 Xi*,j = 1 NA = NA + 1 A = 1 FIN SI FIN SI FIN POUR j JUSQU'A CE QUE (NA N) OU (A 0) SI NA = N ALORS X est la solution optimale SINON Appliquer «l'Algorithme Hongrois» pour déterminer les HIi et HJj en fonction de Ci,j, Xi,j et AUi Rechercher e, tel que e Min(i € {1..N}, j € {1..N} : HIi 0 et HJj = 0 | Ci,j) POUR i ALLANT DE 1 A N FAIRE POUR j ALLANT DE 1 A N FAIRE SI (HIi 0) ET (HJj 0) ALORS Ci,j = Ci,j - e SINON SI (HIi 1) ET (HJj 1) ALORS Ci,j = Ci,j + e FIN SI FIN POUR j FIN POUR i FIN SI FIN TANT QUE

Algortihme HongroisAucun marquage au départ : HIi = 0 HJj = 0 POUR TOUT i ALLANT DE 1 A N FAIRE SI AUi = 0 ALORS HIi = 1 FIN SI FIN POUR i REPETER Marquage = FAUX POUR TOUT j ALLANT DE 1 A N FAIRE SI HJj = 0 ALORS Rechercher i*, tel que Ci*,j 0 et HIi* 1 SI i* existe ALORS HJj = 1 Marquage = VRAI FIN SI FIN SI FIN POUR j POUR TOUT i ALLANT DE 1 A N FAIRE SI HIi = 0 ALORS Rechercher j*, tel que Xi,j* = 1 SI (j* existe) ET (HJj* = 1) ALORS HIi = 1 Marquage = VRAI FIN SI FIN SI FIN POUR i JUSQU'A CE QUE Marquage = FAUX Inverser le marquage des lignes : HIi = 1 - HIi

Merci beegees

Renfield · Answer

fais tes devoirs

à quoi correspond les * dans cet algorithme ?

3 réponses

Votre réponse

Discussions similaires