Optimisation    
 
  Graphes résume   
 
  Euler & Hamilton   
 
  Algorithme & heuristique   
 
  Units   
 
  home  
 
  ask us  
 

 

Mathématiques
2







© The scientific sentence. 2010


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.








  


chimie labs
|
Physics and Measurements
|
Probability & Statistics
|
Combinatorics - Probability
|
Chimie
|
Optics
|
contact
|


© Scientificsentence 2010. All rights reserved.