Qu’est-ce qu’une bonne heuristique ?

• Fournir un gain
• Complexité limitée

• Global optimization – Trouver le chemin minimum qui passe par tous les sommets
• Greedy approximation – Trouver une série de sous-chemins minimum (le suivant, les 2 suivants, etc.)

Vitesse et exactitude

• Si trouver une solution approximative prend autant de temps que trouver la solution exacte, eh bien…
• Comparer l’estimation avec des solutions connues ou des petites instances

• Parfois, les problèmes sont trop difficiles à résoudre

• Des solutions approximatives peuvent être trouvées en moins de temps en alternative

• Les approches gloutonnes peuvent fournir de bonnes solutions approximatives

• Les heuristiques codent une intuition, par exemple, ce qu’il faut minimiser dans un algorithme glouton

• Une bonne heuristique doit fournir un gain et avoir une complexité limitée