Discussion :

[Lok'TaR]

Bonjour,

Je tente désespérément d’écrire un algorithme d’optimisation mais je piétine…
Je vous expose le problème :
Je considère p personnages et n points :
J’ai un tableau de structure de n lignes avec dans chaque ligne un tableau de p couples constitués d’une distance (un réel) et d’un booléen (plus quelques autres infos comme les coordonnées du point)
Le booléen détermine si le point est accessible pour la personne considérée.
Je joins quelques lignes de code c++ pour préciser ma pensée :

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#define n 10 
#define p 100 
 
struct couple 
{ 
    bool accessible; 
    float distance; 
}; 
 
struct point 
{ 
    couple m_couple[n]; 
    float x; 
    float y; 
    float z; 
    bool attribue; 
} ; 
 
point m_point[p] ;

Tout en sachant qu’un point ne peut être pris pour cible que par une personne et qu’il n’est pas sur que toutes les personnes aient une destination comment faire pour maximiser le nombre de personnes ayant une destination en minimisant la distance totale à parcourir ?
Voilà j’espère ne pas m’être trop embrouillé dans mon exposé.

En vous remerciant d’avance.

Bien cordialement

[acx01b]

salut, ça ressemble à un problème d'affectation basique en rajoutant des poids infinis à ta matrice n x p pour qu'elle soit carré

on peut utiliser alors l'algorithme hongrois

tiens ici ils parlent de la même chose
http://www.developpez.net/forums/d40...ice-non-carre/

[Lok'TaR]

Merci!
Je n’avais pas vu le problème sous cet angle.
Ca devrait donner de meilleurs résultats que la méthode à base de permutations que j’ai fini par adopter…
Seul petit bémol: mon n oscille entre 3 et 10 mon p lui est de l'ordre de 500!
Ca fait quand meme une grosse matrice avec pas beaucoup d'info dedans...

[acx01b]

salut,

il y a d'autres algos qui généralisent l'algorithme hongrois, en particulier celui où tu exprimes ton problème d'affection de poids min par un problème de flot max de coût minimum où tu pourras tirer partie de la forme "non carré" de ta matrice (oulala d'autres personnes sur le forum pourront sûrement détailler plus que moi sur le sujet)

le principe reste neanmoins le même a priori