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.