Arbre couvrant minimum

Version imprimable

Bonjour,

J'ai actuellement un projet en C ou je dois réaliser un arbre couvrant minimal pour des points possédant une coordonnée x et y.

N'ayant jamais vu rien de proche en cours, j'ai essayé de trouver par moi même un algorithme. Celui-ci est très proche de la solution car dans la plupart des cas j'atteint le bon résultat. Néanmoins, il semblerait que dans de (rares) cas je n'obtienne pas la solution attendue. N'ayant pas accès aux Input des tests, je ne peux pas savoir ce qui pose problème. Donc il faut que je reprenne mon algo & que j'essaye de voir ce qui plante.

Voici l'algo auquel j'avais pensé.

1/ On calcule la matrice d'adjacence entre les sommets
2/ On trie cette matrice par poids (en gardant a disposition les infos des arbres à relier)
3/ En sachant que si il y a n nœuds dans l'arbre, il y à n-1 liaisons, on cherche les n-1 liaisons de poids le plus faible qui ne forment pas de cycle
4/ Et on retourne la somme des poids des ces n-1 liaisons.

Déjà, est ce que cet algo est correct?

Si oui, voici son implémentation, il faudra que je trouve l'erreur. Je suis conscient que mon algorithme n'est pas tout à fait optimisé. Par exemple il n'était pas nécessaire d'utiliser une matrice d'adjacence complète puisque les liaisons sont pas orientés. Cela dit, la complexité de mon implémentation semble assez faible donc ça doit rester correct.

Fonction principale

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int main(int argc, char** argv)
{
    int i,j;
    int nbIles;
 
    scanf("%d", &nbIles);
    vector2 iles[nbIles];
    cost costMatrix[nbIles*nbIles]; ///Implémentée sur un tableau simple
    for(i=0;i<nbIles ;++i)          /// On saisit les coordonnées des îles
        scanf("%d %d",&(iles[i].x),&(iles[i].y));
 
    for(i=0;i<nbIles;++i) /// On marque les coûts d'accès entre les sommets.
        for(j=0;j<nbIles;++j)
            if(i!=j)
            {
                costMatrix[i * nbIles + j].cost = sqrt( (iles[i].x-iles[j].x)*(iles[i].x-iles[j].x) +(iles[i].y-iles[j].y)*(iles[i].y-iles[j].y)); ///Distance en norme 2 classique.
                costMatrix[i * nbIles + j].from = i;
                costMatrix[i * nbIles + j].to = j;
            }
            else
                costMatrix[i * nbIles + j].cost = INT_MAX; /// On ne veux pas que ces valeurs apparaissent (INT_MAX simule l'infini).
 
    Sort(costMatrix,0,nbIles*nbIles-1);/// Puis on trie les coûts
 
    int nbArcs = 0;
    i=0;
    list* FinalNodes = calloc(nbIles,sizeof(list));
    double Weight =0;
    while (nbArcs < nbIles - 1) ///Ca c'est un algo bien déguelasse comme on les aime !
    {
        if(!FindCycle(FinalNodes,nbIles,costMatrix[i].from,costMatrix[i].to))
        {
            AddItem(&(FinalNodes[costMatrix[i].from]),costMatrix[i].to);///On ajoute les noeuds à la matrice d'adjacence
            AddItem(&(FinalNodes[costMatrix[i].to]),costMatrix[i].from);///On ajoute les noeuds à la matrice d'adjacence
            ++nbArcs; /// 1 arc de plus
            Weight += costMatrix[i].cost; /// On met à jour le poids.
        }
            i+=2; /// Deux valeurs sont égales à chaque fois car on a pris une matrice d'adjacence compléte. On avance donc de 2.
    }
    printf("%d", (int)Weight);
    return 0;
}

Structure utilisées

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct cell
{
    int to;
    struct cell* next;
};
typedef struct cell cell;
typedef cell* list;
 
void AddItem(list* l, int to)
{
    cell* c = malloc(sizeof(cell));
    c->next = NULL;
    c->to = to;
    list tmp = *l;
    *l = c;
    (*l)->next = tmp;
}
 
struct vector2
{
    int x,y;
};
typedef struct vector2 vector2;
struct cost
{
    int from,to;
    double cost;
};
typedef struct cost cost;

Algorithme de tri (ici quicksort), je crois qu'il est correct

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void swap ( cost* a, cost* b )
{
    int t = a->from;
    a->from = b->from;
    b->from = t;
 
    t = a->to;
    a->to = b->to;
    b->to = t;
 
    double td = a->cost;
    a->cost = b->cost;
    b->cost = td;
}
 
int partition (cost costs[], int l, int h)
{
    int x = costs[h].cost;
    int i = (l - 1);
    int j;
    for (j = l; j <= h- 1; j++)
    {
        if (costs[j].cost <= x)
        {
            i++;
            swap (&costs[i], &costs[j]);
        }
    }
    swap (&costs[i + 1], &costs[h]);
    return (i + 1);
}
 
void Sort(cost costs[], int l, int h)
{
    int stack[ h - l + 1 ];
    int top = -1;
    stack[ ++top ] = l;
    stack[ ++top ] = h;
 
    while ( top >= 0 )
    {
        h = stack[ top-- ];
        l = stack[ top-- ];
        int p = partition( costs, l, h );
        if ( p-1 > l )
        {
            stack[ ++top ] = l;
            stack[ ++top ] = p - 1;
        }
        if ( p+1 < h )
        {
            stack[ ++top ] = p + 1;
            stack[ ++top ] = h;
        }
    }
}

Et fonction de recherche de cycle

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool FindCycle(list* finalNodes, int nbIles, int from, int to)
{
    bool* EstParcouru = calloc(nbIles,sizeof(bool));
    list stack = NULL;
    AddItem(&stack,from);
    while (stack != NULL)
    {
        list tmp = stack;
        int cell = stack->to;
        stack = stack->next;
        free(tmp);
        list nexts = finalNodes[cell];
        while(nexts)
        {
            if(nexts->to == to)  ///On a atteint le début du cycle
                return true;
            else if(!EstParcouru[nexts->to])
            {
                AddItem(&stack,nexts->to);
                EstParcouru[nexts->to] = true;
            }
            nexts = nexts->next;
        }
    }
    return false;
}

Outre les problèmes d'optimisation (qui sont un autre problème pour l'instant) voyez vous des problèmes plus importants pouvant conduire à des résultats faux?

Je vous remercie pour votre aide,

Maxime.

21/12/2015, 11h29
stendhal666

Il y a un petit problème dans l'explication de ton algorithme :)

Tu dis:

Citation:

3/ En sachant que si il y a n nœuds dans l'arbre, il y à n-1 liaisons, on cherche les n-1 liaisons de poids le plus faible qui ne forment pas de cycle

Mais ce point 3 est justement la définition de l'arbre couvrant minimum, donc je n'ai pas trop l'impression que tu aies expliqué ton algorithme!

Je pense que tu es sur la voie de l'algorithme de Kruskal:
- on fait une liste des arêtes du graphe
- on la trie
- tant que l'arbre créé ne couvre pas le graphe: on ajoute la prochaine plus petite arrête si ses sommets ne sont pas déjà connectés dans l'arbre

La difficulté que tu rencontres à mon avis est liée au fait que l'algorithme utilisé est un algorithme glouton: il part d'optimum locaux qui donnent une bonne solution mais n'aboutissent pas nécessairement à l'optimum global. C'est le cas de la plupart des algorithmes existants (tu peux faire des recherches pour en trouver un parfait mais tu vas à mon avis excéder la portée du cours). Différents algorithmes peuvent donc arriver à un résultat différent.

Enfin, et c'est peut-être le cas comme tu ne connais pas les inputs, si tous les poids sont égaux, tout arbre couvrant est un arbre minimum...

Mais ne pourrais tu pas ajouter quelques fonctions de log à ton programme pour reconstituer l'input?
21/12/2015, 21h40
emixam16
Comme je n'avais jamais vu des algorithmes j'ai tenté "d'improviser" ça from scratch. Cela dit, mon algo me semble effectivement proche de celui de Kruskal, en tout cas dans l'idée de départ.

Citation:

La difficulté que tu rencontres à mon avis est liée au fait que l'algorithme utilisé est un algorithme glouton: il part d'optimum locaux qui donnent une bonne solution mais n'aboutissent pas nécessairement à l'optimum global. C'est le cas de la plupart des algorithmes existants (tu peux faire des recherches pour en trouver un parfait mais tu vas à mon avis excéder la portée du cours). Différents algorithmes peuvent donc arriver à un résultat différent.

(C'est bien j'apprends plein de notions). J'avais réfléchi à ça mais je ne vois pas comment la solution donnée par l'algorithme peut ne pas être optimale. Pour moi un arbre couvrant minimum est juste la somme des "arrêtes avec le plus petit poids et qui ne forment pas un cycle", non?

Citation:

Mais ne pourrais tu pas ajouter quelques fonctions de log à ton programme pour reconstituer l'input?

Le code n'est pas executé sur ma machine, et de toute façon je ne pense pas avoir le droit de récupérer les inputs.

Deux possibilités peuvent expliquer mon résultat faux
- Soit mon algorithme (et Kruskal) ne donnent pas forcément le meilleur poids local (mais je ne vois pas comment c'est possible)
- Soit j'ai fait une erreur dans mon implémentation, et dans ce cas, elle vient très probablement de la fonction FindCycle.
Si quelqu'un à une idée d'où peut venir mon problème, je serais ravi de l'entendre!

Merci d'avance :)
22/12/2015, 10h28
stendhal666

Oui, en l'occurrence tu as raison, bien que l'algorithme soit glouton par sa méthode il donne l'optimum global quoiqu'il arrive, à cause de (grâce à) la définition du problème particulier.

C'est donc qu'il y a soit un problème dans ton code, soit dans la correction. En penchant pour le premier, une réflexion: il y a 9 variables dans ta fonction, dont plusieurs sont des structures de données complexes... J'ai essayé de suivre le code en le regardant pour trouver l'erreur mais bon, je ne suis pas un ordinateur!

Regarde le pseudo-code donné sur Wikipedia:

Citation:

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3 MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5 if FIND-SET(u) ≠ FIND-SET(v):
6 A = A ∪ {(u, v)} // je rajouterais: if size(A) == N-1 return A
7 UNION(u, v)
8 return A

C'est tout de suite beaucoup plus clair! Il faut arriver à ce genre de résultat, même et surtout en écrivant en C. La structure derrière ces fonctions est un disjoint-set, c'est-à-dire grosso-modo une liste chaînée d'ensembles (pas de doublon dans un ensemble, hein?). Les ensembles peuvent aussi eux-mêmes être représentés comme des listes chaînées; le nom de l'ensemble (la valeur de retour de FIND-SET est le premier élément de la liste.

Donc après la boucle aux lignes 2-3 on a un disjoint set du genre:

{ s1 } -> { s2 } -> ... -> { sN }

Un cycle existe dès que les deux sommets d'une arrête rajoutée appartiennent au même ensemble. Si pas de cycle on ajoute le sommet à l'arbre couvrant minimal et on fusionne les ensembles contenant chacun des sommets; sinon on passe.

Donc mon conseil, qui ne te plaira peut-être pas: implémente le disjoint-set (quelques fonctions de 5 lignes et 3 variables max, faciles à tester séparément) puis fais une fonction find-cycle facile à comprendre car elle sera beaucoup plus pénible à tester!
22/12/2015, 10h31
stendhal666

Au fait, comme l'erreur arrive souvent où on ne l'attend pas, tu devrais utiliser le qsort de la librairie C pour voir si le problème ne vient pas de ton algorithme de tri -sinon tu peux remettre ta propre fonction
23/12/2015, 13h49
sambia39
Bonjour.
Enlevez-moi un doute, mais je pense que l’algorithme en question (du primo postant) n’est pas au point ( et non dans l’explication de l'algorithme ) et d’un autre côté plusieurs éléments n’ont pas été pris en compte.

Dans votre exemple de code source que vous avez posté, vous utiliser une structure de données complexe. Par conséquent, il faut concevoir votre algorithme de façon robuste afin qu’il puisse résoudre le problème tout en tenons compte de la complexité en question. Dans le cas contraire, c'est-à-dire si votre algorithme n'est pas capable de résoudre le problème, il faut utilisé un autre algorithme capable de résoudre le problème avec la complexité correspondante par exemple Prim ou Sollin.

"Du moins", vous essayez d’utiliser et d'implémenter un algorithme qui consiste à compléter au fur et à mesure un arbre avec les arêtes de poids les plus faibles en vérifiant que l’ajout de l’arête ne forme pas de cycle ce qui ressemble effectivement de l’algorithme de Kruskal, ce qui est juste et qui est tout à fait normal, car on doit respecter certaines règles préalables. Essayent de comprendre un peu.

Un graphe non orienté (pour l’exemple ici que j’appelle AC) est un arbre s'il est connexe et sans cycle, c'est-à-dire qu’il n’existe aucun chemin relié à un sommet AC permettant ainsi de revenir sur ce même sommet respectant, les règles élémentaires suivantes :
- Si l'on enlève une arête d’AC alors AC n’est plus connexe.
- Si on ajoute une arête à AC il forme un cycle de par ces règles on en conclut que si AC possède "X" sommet il existe uniquement que "X-1" relation dans AC.
Donc pour un graphe "G" il existe au moins un arbre couvrant "AC" mais il s’agit juste d’un arbre partiel qui possède les mêmes sommets que "G" et dont l’ensemble des relations est inclus dans celui des relations de "G". "AC" étant un arbre car cela est dû au fait que "G" soit connexe. Et comme "G" est pondéré c'est-à-dire qu’il a un coût on peut en déduire que le coût du graphe "AC" est inférieur ou égal au coût du graphe "G" donc si AC est un arbre couvrant de "G" dont la somme des pondérations de ces arrête est la plus petite valeur par rapport à celle des autres arbres couvrant du graphe "G" alors "AC" est bien un arbre couvrant de poids minimum de "G" noté le plus souvent ACM et donc, il est possible de retrouver un ACM, car il suffit de rechercher pour chaque arbre couvrant de "G" celui qui possède le plus bas coût possible, mais en procédant ainsi le coût de la recherche est largement très coûteux en temps. et en vue de votre structure complexe, je doute comme vous l’avez stipulé "que votre algorithme soit simple" dans ce genre de situation il est préférable de construire heuristiquement l’arbre plutôt que de les rechercher.

En vue de votre fonction de trie sans même rentré plus en détaille , l’algorithme., (je pense) n’est utilisable et applicable à condition de ne pas adopter une structure complexe de données. En revanche si vous vous penchez un peu plus en détail dans votre algorithme, vous arriverez peut-être à l’algorithme de Kruskal , c'est-à-dire :
- Etablir une liste des arêtes classée par valeurs croissantes.
- Choisir l’arête de valeur minimale. Puis successivement au fur et à mesure de la construction de l’arbre inclure l’arête suivante dans la liste si elle ne forme pas de cycles avec les arêtes incluses jusque-là
- S’arrêter lorsque tous les sommets du graphe sont connectés (à ce stade nous avant X-1 arrêtent.)
Mais comme je l’ai mentionné un peu avant cela à un coût en temps ( sur un graphe G=( X, A)) rien que l’initialisation à un temps d'O(X) et un temps de tri de l’ordre d'O( A log A) et de plus cet algorithme dépend de l’implémentation de la structure de données d’ensemble disjoint. Bref, mon conseil est de revoir l'algorithme ou de sen inspire afin de réaliser une variante qui répondra à vos attentes. Il également possible d’essayer d'autres algorithmes comme celui de Sollin ou de Prim qui ressemble un peu à l’algorithme de Dijkstra.
Exemple
1 -> Marquer un sommet arbitrairement
2 -> Tant qu'il existe un sommet non marqué faire
- A -> Choisir une arête de valuation minimale ayant l'une de ses extrémités marquées et l'autre non marquée et l'inclure dans l'arbre en construction.
- B -> Marquer cette autre extrémité
3 -> Fin lorsque tous les sommets sont marqués.

à bientôt
23/12/2015, 18h37
stendhal666

Tiens, voilà qui explique tout:
https://en.wikipedia.org/wiki/Minimu...e_multiplicity
27/12/2015, 20h33
emixam16

Merci de vos réponses, grâce à vous, j'ai réussi à voir des endroits où rendre mon code plus propre.

Comme j'ai passé longtemps sans trouver l'erreur, j'ai recommencé en utilisant l'algorithme de Prim. Ça marche très bien, et la complexité rete en O(n log n). Je ne poste pas le code car je pense qu'on peut trouver facilement une implémentation sur internet.