Mathématiques 514

 

Algorithme du voisin le plus proche

  1. On va imposer un sommet de départ

  2. À partir de ce sommet, on va considérer la valeur la plus petite ou la plus grande, selon l'énoncé du problème, pour toutes les arêtes qui touche ce sommet .

  3. Il faut s'assurer que tous les sommets ont été atteints une seule fois (cycle simple en passant par tous les sommets).

 

Exemple: Je veux le cycle le plus long en partant du sommet C.

Démarche

Sommet C: j'ai le choix entre les valeurs 3, 6, 7 et 11.  Je vais prendre la plus grande valeur qui est 11.  Donc je pars de C et je me rend au sommet A.

Sommet A: j'ai le choix entre les valeurs 9, 10 et 12.  Je laisse tomber la valeur 11 qui mène à C car ce sommet a déjà été considéré.  Je vais prendre la plus grande valeur qui est 12.  Donc je pars de A et je me rend au sommet D.

Sommet D: j'ai le choix entre les valeurs 3, 4 et 7 car 12 a été considéré.  Je vais prendre la plus grande valeur qui est 7.  Donc je pars de D et je me rend au sommet B.

Sommet B: je n'ai pas d'autre choix que le sommet E car les trois autres chemins ont déjà été considérés.  Je vais prendre la valeur 8.  Donc je pars de B et je me rend au sommet E.

Sommet E: Tous les sommets ont été visités alors on revient au point de départ pour compléter le cycle. On se rend donc au sommet C avec la valeur 7.

Le cycle sera C-A-D-B-E-C et la valeur sera 11+12+7+8+7= 45

Exercice:

  1. Trouver le cycle le plus court à partir du sommet C

  2. Trouver le cycle le plus long à partir du sommet E

  3. Trouver le cycle le plus court à partir du sommet A

  4. Trouver le cycle le plus long à partir du sommet B

Réponse:

 

 

Algorithme d'arête croissante

Il faut trouver la valeur minimale ou maximale selon le problème.

1- Il faut dresser une liste des arêtes dans l'ordre croissant ou décroissant (selon le cas)

2- Choisi l'arête la plus satisfaisante (de la plus petite à la plus grande ou l'inverse

    selon le cas).  Il faut faire attention de ne pas refermer le cycle lorsque l'on choisi

    une arête.  On doit toucher à tous les sommets et chaque sommet doit être de degré 2.

    (Il faut donc bâtir un cycle hamiltonien)

 

Exemple 1: On veut trouver un cycle de valeur maximale.

On doit donc classer les arêtes en ordre décroissant

Arête AD AC AE AB BE CE BD BC DE CD
Valeur 12 11 10 9 8 7 7 6 4 3

Le premier choix est AD car il vaut 12. Le deuxième choix est AC car il vaut 11.  Par la suite, on ne peut pas prendre AE car le sommet A serait de degré 3.  Même chose pour AB. Alors, nous devons prendre BE avec la valeur de 8. L'arête CE serait la suivante avec une valeur de 7.  Il ne nous reste que l'arête BD pour fermer le cycle avec une valeur de 7.

Le cycle sera donc A-D-B-E-C-A pour une valeur maximale de 45.

Réponse:

 

Exemple 2: On veut trouver un cycle de valeur minimale.

On doit donc classer les arêtes en ordre croissant.

Prenons la table des valeurs de l'exemple 1 et commençons par la fin.

Prenons CD avec la valeur 3. Ensuite, prenons DE avec la valeur 4. Allons-y avec l'arête BC et une valeur de 6. Il ne nous reste que l'arête AB et AE pour fermer le cycle.

Voici le cycle A-B-C-D-E-A pour une valeur minimale de 32.

 

  

Dernière mise à jour effectuée le 23 décembre 2005