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
Algorithme et heuristique





1. Algorithme

Lorsqu’on a affaire à des petits graphes, c'est à dire contenant peu de sommets et d'arêtes, on utilise un algorithme.

Un algorithme est une suite finie et ordonnée d'instructions
(ou d'opérations) permettant de résoudre un problème.



2. Heuristique

Lorsqu’on a des gros graphes ou qu'on désire obtenir des solutions très rapidement, on utilise une heuristique.

Une heuristique est une procédure qui fournit des solutions de qualité raisonnable en des temps raisonnables. IL utilise des approches successives en éliminant progressivement les alternatives et en ne conservant que des solutions menant à celle qui est optimale.

En théorie des graphes, une heuristique utilisée peut être améliorée en rajoutant à la fin une procédure de post-optimisation. Celle-ci consiste à vérifier s’il existe une paire d’arêtes sur le cycle qui peut être remplacée par une autre paire d’arêtes tout en diminuant la distance totale parcourue.

On note qu'il n’y a qu’un remplacement possible par paire d’arêtes.








  


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


© Scientificsentence 2010. All rights reserved.