Mathématiques 2: Géométrie
Les graphes
L'optimisation par les graphes
Heuristique d'arête croissante
1. Heuristque d'arête croissante
L'heuristique d'arête croissante consiste à :
• Trier les arêtes par longueur croissante (ou
decroissante selon le contexte),
• Parcourir la liste triée des arêtes
en sélectionnant les arêtes de manière à :
Ne pas fermer le cycle pendant cette séléction (créer un court-circuit), et de
Ne pas considérer les sommets de degré 3
(créeer une fouche)
• Continuer, en considérant tous les sommets, jusqu'à ce qu'on puisse revenir au sommet de départ
pour compléter un cycle. C,est donc un cycle
hamiltonien.
Autrement dit :
• Trier les arêtes par longueur croissante (ou
decroissante),
• Tant que la tournée n'est pas complète,
Prendre la première arête non considérée de la liste
Si elle ne crée ni cycle, ni fourche avec les arêtes précédemment sélectionnées, la retenir.
2. Exemple
Voici une grenouille qui fait un cycle AA en
sautant d'un nénuphar à l'autre.
Les distances sont évaluées en m.
Le 1er choix est AE = 1, et le 2ème est BD = 1,
Le 3ème est AB = 2, et le 4ème est CD = 2
Ainsi le AD, le AC, et le DE sont éliminés puisqu'ils
formeront des fourches.
BE est éliminé puisqu'il formera un cycle.
CB est éliminé puisqu'il formera un cycle et une fouche.
Au sommet, il ne reste qu'un seul choix, c'est CE.
Tout les sommets ont été considérés, durant la sélection,
il n'y avait pas de fouche ni de court-circuit. On
a donc
AE + EC + CD + DB + BA =
1 + 7 + 2 + 1 + 2 = 13
C'est le cycle de valeur minimale cherché.
Le cycle de sauts de la grenouille es de 13 mètres.
