à quoi correspond les * dans cet algorithme ?

Signaler
Messages postés
152
Date d'inscription
mardi 4 novembre 2008
Statut
Membre
Dernière intervention
10 avril 2017
-
Messages postés
17286
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
23 décembre 2019
-
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

3 réponses

Messages postés
14008
Date d'inscription
samedi 29 décembre 2001
Statut
Modérateur
Dernière intervention
28 août 2015
75
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)
Messages postés
152
Date d'inscription
mardi 4 novembre 2008
Statut
Membre
Dernière intervention
10 avril 2017
1
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
<li>On dispose de N unités de traitement :
Ui : unité i, où i >= 1 et i <= N</li><li>On dispose du même nombre de postes à pourvoir :
Pj : poste j , où j > = 1 et j <= N</li><li>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 </li>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
:

<li>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} </li><li>Contraintes d'affectation des unités :
Pour tout i € {1..N} : Somme(j € {1..N} | Xi,j) = 1 </li><li>Contraintes d'affectation des postes :
Pour tout j € {1..N} : Somme(i € {1..N} | Xi,j) = 1</li><li>Fonction d'optimisation :
Min(X | Somme(i € {1..N}, j € {1..N} | Ci,j . Xi,j) )</li>Méthode
<li>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

</li><li>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

</li><li>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

</li>

Merci
beegees
Messages postés
17286
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
23 décembre 2019
69
fais tes devoirs