Classes d'algorithmes

Les algorithmes sont des étapes non ambiguës qui doivent nous donner une réponse bien définie en traitant zéro ou plusieurs entrées. Cela conduit à de nombreuses approches dans la conception et l'écriture des algorithmes. Il a été observé que la plupart des algorithmes peuvent être classés dans les catégories suivantes.

Algorithmes gourmands

Les algorithmes avides tentent de trouver une solution optimale localisée, ce qui peut éventuellement conduire à des solutions optimisées au niveau mondial. Cependant, les algorithmes avides ne fournissent généralement pas de solutions optimisées au niveau mondial.

Les algorithmes avides recherchent donc une solution facile à ce moment précis sans tenir compte de son impact sur les étapes futures. C'est similaire à la façon dont les humains résolvent des problèmes sans examiner en détail les données fournies.

La plupart des algorithmes de mise en réseau utilisent l'approche gourmande. Voici une liste de quelques-uns d'entre eux :

• Problème du voyageur de commerce
• Algorithme de l'arbre à portée minimale de Prim
• Algorithme de l'arbre à portée minimale de Kruskal
• Algorithme de l'arbre à portée minimale de Dijkstra

Diviser pour mieux régner

Cette classe d'algorithmes consiste à diviser le problème donné en sous-problèmes plus petits, puis à résoudre chacun de ces sous-problèmes indépendamment. Lorsque le problème ne peut plus être divisé, nous commençons à fusionner la solution de chacun des sous-problèmes pour arriver à la solution du plus gros problème.

Les exemples importants d'algorithmes de type diviser pour régner sont :

• Tri par fusion
• Tri rapide
• Algorithme de l'arbre d'expansion minimal de Kruskal
• Recherche binaire

Programmation dynamique