Quels sont les cinq algorithmes les plus couramment utilisés ?

Les algorithmes couramment utilisés sont : 1. La méthode diviser pour mieux régner ; 2. L'algorithme gourmand, une technologie de conception plus simple et plus rapide pour certains problèmes de solution optimale ; 3. L'algorithme de programmation dynamique ; méthode de recherche ; 5. Méthode de branchement et de liaison.

Les cinq algorithmes les plus couramment utilisés sont : la méthode diviser pour régner, l'algorithme glouton, l'algorithme de programmation dynamique, la méthode de retour en arrière et la méthode de branchement et de liaison.

Qu'est-ce qu'un algorithme ?

L'algorithme fait référence à une description précise et complète d'une solution de résolution de problèmes. Il s'agit d'une série d'instructions claires pour résoudre des problèmes. L'algorithme représente une méthode systématique pour décrire le mécanisme stratégique de résolution. problèmes.

On peut comprendre qu'un algorithme est une série d'étapes utilisées pour résoudre un problème spécifique ; l'algorithme doit avoir les trois caractéristiques importantes suivantes :

1. Après avoir exécuté un nombre fini d’étapes, l’algorithme doit se terminer.

2. Précision. Chaque étape de l'algorithme doit être définie avec précision.

3. Faisabilité. Un algorithme spécifique doit être capable de résoudre un problème spécifique dans un laps de temps spécifique.

Les cinq algorithmes les plus couramment utilisés

Méthode Diviser pour régner

La méthode diviser pour régner La méthode consiste à diviser un Un problème complexe est divisé en deux ou plusieurs sous-problèmes identiques ou similaires, puis les sous-problèmes sont divisés en sous-problèmes plus petits... jusqu'à ce que finalement les sous-problèmes puissent être résolus simplement et directement, et la solution au problème initial est la fusion des solutions aux sous-problèmes.

Les problèmes qui peuvent être résolus par la méthode diviser pour régner ont généralement les caractéristiques suivantes :

1). Le problème peut être facilement résolu lorsque l'ampleur du problème est réduite à un. dans une certaine mesure ;

2). Ce problème peut être décomposé en plusieurs problèmes identiques plus petits, c'est-à-dire que le problème a des propriétés de sous-structure optimales

3). le problème peut être combiné en La solution à ce problème ;

4), chaque sous-problème décomposé par ce problème est indépendant les uns des autres, c'est-à-dire qu'il n'y a pas de sous-sous-problèmes communs entre les sous-problèmes. problèmes.

Algorithme glouton

L'algorithme glouton est une technologie de conception plus simple et plus rapide pour certains problèmes de solution optimale.

L'algorithme de conception de méthode glouton se caractérise par le fait de procéder étape par étape. Il fait souvent des choix optimaux en fonction de la situation actuelle et sur la base d'une mesure d'optimisation, sans considérer diverses situations globales possibles. La solution optimale doit passer beaucoup de temps à épuiser toutes les possibilités. Elle utilise des méthodes descendantes et itératives pour faire des choix gourmands successifs. Chaque fois qu'un choix gourmand est fait, le problème souhaité est simplifié en un sous-ensemble plus petit. sélection glouton à chaque étape, une solution optimale au problème peut être obtenue. Bien qu'il soit garanti d'obtenir une solution optimale locale à chaque étape, la solution globale résultante n'est parfois pas nécessairement optimale, donc l'algorithme glouton ne fait pas de Backtrace.

Algorithme de programmation dynamique

La programmation dynamique est une méthode utilisée en mathématiques et en informatique pour résoudre des problèmes d'optimisation contenant des sous-problèmes qui se chevauchent. L'idée de base est de décomposer le problème initial en sous-problèmes similaires et, dans le processus de résolution du problème, la solution du problème initial est obtenue grâce aux solutions des sous-problèmes. L'idée de programmation dynamique est à la base de nombreux algorithmes et est largement utilisée dans les domaines de l'informatique et de l'ingénierie.

Les méthodes de programmation dynamique sont généralement utilisées pour résoudre des problèmes d'optimisation. Ce type de problème peut avoir de nombreuses solutions possibles. Chaque solution a une valeur. Trouver la solution avec la valeur optimale est appelé une solution optimale au problème. de la solution optimale, il peut y avoir plusieurs solutions qui atteignent toutes la valeur optimale.

Étapes de la conception d'un algorithme de programmation dynamique :

1), caractériser les caractéristiques structurelles d'une solution optimale

2), définir récursivement la valeur de la solution optimale

3), calculer la valeur de la solution optimale, généralement en utilisant la méthode ascendante

4), utiliser les informations calculées pour construire une solution optimale

Programmation dynamique et diviser Méthode "-et-conquérir" Semblable à la solution du problème original, les solutions des sous-problèmes sont combinées pour résoudre la solution du problème original. La différence avec la méthode diviser pour régner est que les sous-problèmes du problème initial sont combinés. La méthode diviser pour régner existe indépendamment les unes des autres, tandis que la programmation dynamique est appliquée lorsque les sous-problèmes se chevauchent.

Méthode de backtracking

La méthode de backtracking (méthode d'exploration et de backtracking) est une méthode de recherche d'optimisation, qui recherche en avant en fonction des conditions d'optimisation pour atteindre l'objectif. Mais lorsque vous atteignez une certaine étape de l'exploration et constatez que le choix initial n'est pas optimal ou ne peut pas atteindre l'objectif, vous prendrez du recul et ferez un autre choix. Cette technique consistant à revenir en arrière et à réessayer quand cela ne fonctionne pas. est la méthode de retour en arrière, et le point dans un certain état qui satisfait aux conditions de retour en arrière est appelé « point de retour en arrière ».

L'idée de base est d'explorer en profondeur l'arbre de l'espace de solutions en commençant par le nœud racine selon la stratégie de recherche en profondeur d'abord dans l'arbre de l'espace de solutions contenant toutes les solutions au problème. Lorsqu'un nœud est exploré, il est nécessaire de déterminer d'abord si le nœud contient la solution au problème. Si c'est le cas, continuez l'exploration à partir de ce nœud. Si le nœud ne contient pas la solution au problème, procédez couche par couche. ancêtres.

Méthode de branchement et de liaison

La méthode de branchement et de liaison est un algorithme très largement utilisé. L'utilisation de cet algorithme est très habile et différents types de solutions de problèmes ont. méthodes différentes. Pas la même chose.

L'idée de base de la méthode branch-and-bound est de rechercher l'espace de toutes les solutions réalisables (un nombre limité) au problème d'optimisation avec contraintes. Lorsque l'algorithme est spécifiquement exécuté, l'ensemble de l'espace de solutions réalisables est continuellement divisé en sous-ensembles de plus en plus petits (appelés branches), et une limite inférieure ou supérieure (appelée délimitation) est calculée pour la valeur de la solution dans chaque sous-ensemble). Après chaque branchement, aucune autre branche ne sera effectuée vers les sous-ensembles dont les limites dépassent la valeur de solution réalisable connue. De cette manière, de nombreux sous-ensembles de la solution (c'est-à-dire de nombreux nœuds sur l'arbre de recherche) peuvent être ignorés, réduisant ainsi la recherche. portée. Ce processus se poursuit jusqu'à ce qu'une solution réalisable soit trouvée dont la valeur ne dépasse pas les limites de tout sous-ensemble. Par conséquent, cet algorithme peut généralement obtenir la solution optimale.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!