Python - Classes d'algorithmes

Les algorithmes sont des étapes sans ambiguïté qui devraient nous donner une sortie 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 gourmands tentent de trouver une solution optimale localisée, qui peut éventuellement conduire à des solutions optimisées globalement. Cependant, les algorithmes généralement gourmands ne fournissent pas de solutions globalement optimisées.

Les algorithmes gourmands recherchent donc une solution simple à ce moment-là sans tenir compte de son impact sur les étapes futures. C'est similaire à la façon dont les humains résolvent les problèmes sans passer par les détails complets des entré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 de vendeur itinérant
• Algorithme d'arbre couvrant minimal de Prim
• Algorithme d'arbre couvrant minimal de Kruskal
• Algorithme minimal Spanning Tree de Dijkstra

Diviser et conquérir

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

Les exemples importants d'algorithmes de division et de conquête sont:

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

Programmation dynamique

La programmation dynamique implique de diviser le plus gros problème en plus petits, mais contrairement à diviser pour vaincre, elle n'implique pas de résoudre chaque sous-problème indépendamment. Les résultats de sous-problèmes plus petits sont plutôt mémorisés et utilisés pour des sous-problèmes similaires ou se chevauchant. La plupart du temps, ces algorithmes sont utilisés pour l'optimisation. Avant de résoudre le sous-problème en cours, l'algorithme dynamique essaiera d'examiner les résultats des sous-problèmes précédemment résolus.

les algorithmes dynamiques sont motivés pour une optimisation globale du problème et non pour l'optimisation locale.

Les exemples importants d'algorithmes de programmation dynamique sont:

• Série de numéros de Fibonacci
• Problème de sac à dos
• La tour de Hanoi