Quels sont les cinq algorithmes informatiques classiques ?

Cinq algorithmes informatiques classiques : 1. Méthode diviser pour mieux régner, qui divise un problème complexe en deux ou plusieurs sous-problèmes identiques ou similaires ; 2. Méthode de programmation dynamique 3. Algorithme gourmand 4. Méthode de retour en arrière, une recherche optimale ; la méthode recherche vers l'avant selon les conditions optimales pour atteindre l'objectif 5. Méthode de branchement et de liaison.

L'environnement d'exploitation de ce tutoriel : système Windows 10, ordinateur Dell G3.

Je suis sur le point de commencer à déposer des CV et à chercher des stages. Je ne sais toujours pas comment faire, donc je panique. A partir d'aujourd'hui, je vais brosser plus de 2 leetcodes chaque jour et ensuite les résumer, et résumer les points de connaissance de diverses questions d'entretien, je les passerai fréquemment en revue à l'avenir.

Quand je brossais leetcode, j'ai souvent vu des gens parler de DP. Ensuite, je suis allé sur Baidu pour découvrir ce qu'est DP, puis j'ai réalisé que DP est l'un des cinq algorithmes classiques. Aujourd'hui, je vais résumer les cinq algorithmes classiques. .

Les cinq algorithmes classiques sont divisés en

1. Méthode diviser pour mieux régner : diviser un problème complexe en deux ou plusieurs sous-problèmes identiques ou similaires, puis diviser les sous-problèmes en sous-problèmes plus petits. .. Jusqu'à la fin, les sous-problèmes peuvent être résolus simplement et directement, et la solution au problème initial est la fusion des solutions aux sous-problèmes.

2. Méthode de programmation dynamique : Chaque décision dépend de l'état actuel et provoque immédiatement une transition d'état. Une séquence de décision est générée dans un état changeant, c'est pourquoi ce processus de prise de décision d'optimisation en plusieurs étapes pour résoudre les problèmes est appelé programmation dynamique.

3. Algorithme gourmand : Lorsque vous résolvez un problème, faites toujours le meilleur choix du moment. En d’autres termes, sans considérer la solution optimale globale, ce qu’il a fait n’était qu’une solution optimale locale dans un certain sens. Les algorithmes gloutons courants incluent : l'algorithme Prim et l'algorithme Kruskal (tous deux recherchent des arbres couvrant minimum).

Idée de base : Décomposer le problème en plusieurs petits problèmes, obtenir progressivement la solution optimale locale de chaque sous-problème, et enfin la fusionner dans la solution du problème d'origine.

4. Méthode de backtracking : L'algorithme de backtracking est en fait un processus de tentative de recherche de type énumération. Il recherche principalement la solution au problème lors de la tentative de recherche. Lorsqu'il s'avère que les conditions de solution ne sont plus remplies, il " revenir en arrière" et revenir pour essayer autre chose. chemin. Priorité en profondeur ; la méthode rétrospective est une méthode de recherche par sélection, qui recherche vers l'avant en fonction des conditions de sélection 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 ».

5. Méthode Branch andbound : Semblable à la méthode backtracking, c'est aussi un algorithme qui recherche la solution au problème sur l'arbre de l'espace de solution T du problème. Cependant, en général, les objectifs de solution de la méthode branch andbound et de la méthode backtracking sont différents. Le but de la solution de la méthode de backtracking est de trouver toutes les solutions dans T qui satisfont aux conditions de contrainte, tandis que le but de la méthode de branchement et de liaison est de trouver une solution qui satisfait les conditions de contrainte, ou de trouver une solution qui satisfait la contrainte. conditions pour qu'un certain objectif La valeur de la fonction atteigne la solution maximale ou minimale, qui est la solution optimale dans un certain sens.

1. Méthode Diviser pour régner 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 dans une certaine mesure

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

3) Les solutions aux sous-problèmes décomposés par ce problème peuvent être combinées dans la solution de ce problème


4) Les sous-problèmes décomposés à partir de ce problème sont indépendants les uns des autres, c'est-à-dire les sous-problèmes ; ne contiennent pas de sous-problèmes communs.

Si vous ne possédez pas la troisième caractéristique, vous pouvez envisager d'utiliser la programmation dynamique (DP) ou la méthode gourmande.

Si vous ne possédez pas la quatrième caractéristique, vous pouvez envisager d'utiliser la programmation dynamique.

Étapes de base de la méthode diviser pour mieux régner :

Décomposition Étape 1 : Décomposer le problème d'origine en plusieurs sous-problèmes plus petits et indépendants ayant la même forme que le problème d'origine :

Solution Étape 2 : Si le sous-problème est petit en ; taille et facile à résoudre, puis résolvez directement, sinon résolvez chaque sous-problème de manière récursive

Étape 3 Fusionner : Combinez les solutions de chaque sous-problème dans la solution du problème d'origine.

2. La plus grande différence entre la méthode de programmation dynamique
et la méthode diviser pour régner est que pour les problèmes qui peuvent être résolus par la méthode de programmation dynamique, les sous-problèmes obtenus après décomposition ne sont souvent pas indépendants les uns des autres (c'est-à-dire le sous-problème suivant. La solution de chaque étape est basée sur la solution de la sous-étape précédente pour une solution ultérieure).

Conditions applicables :

Les problèmes pouvant être résolus par programmation dynamique ont généralement trois propriétés :

(1) Principe d'optimisation : Si la solution au sous-problème contenu dans la solution optimale du problème est également optimale, Le On dit que le problème a une sous-structure optimale, c’est-à-dire qu’il satisfait au principe d’optimisation.

(2) Aucune séquelle : c'est-à-dire qu'une fois l'état d'une certaine étape déterminé, il ne sera pas affecté par les décisions ultérieures dans cet état. En d’autres termes, le processus après un certain état n’affectera pas l’état précédent, mais est uniquement lié à l’état actuel.

(3) Il existe des sous-problèmes qui se chevauchent : c'est-à-dire que les sous-problèmes ne sont pas indépendants et qu'un sous-problème peut être utilisé plusieurs fois lors de l'étape suivante de la prise de décision. (Cette propriété n'est pas une condition nécessaire à l'application de la programmation dynamique, mais sans cette propriété, l'algorithme de programmation dynamique n'aura pas d'avantages par rapport aux autres algorithmes)

Cas :

Il y a n marches, et une personne en monte une niveau à chaque fois Ou deux marches, demandez combien de façons il y a pour monter n marches.
Analyse : la clé de la mise en œuvre de la programmation dynamique réside dans la question de savoir si la table de programmation dynamique peut être utilisée avec précision et raisonnablement pour résumer des problèmes pratiques. Dans ce problème, soit f(n) représente le nombre de façons de monter n marches.

Alors quand n vaut 1, f(n) = 1, quand n vaut 2, f(n) =2, c'est-à-dire quand il n'y a qu'une seule étape, le nombre de méthodes est un, et il y a deux étapes. À l'heure actuelle, le nombre de méthodes est de 2. Ainsi, lorsque nous voulons monter n marches, nous devons faire un pas sur n-1 marches ou deux pas sur n-2 marches, donc le nombre de façons d'atteindre n marches doit être la méthode pour atteindre n-1 marches, plus la somme du nombre de façons d'atteindre n-2 étapes. Autrement dit, f(n) = f(n-1)+f(n-2), nous utilisons dp[n] pour représenter la table de programmation dynamique, dp[i],i>0,i<=n, indiquant atteindre le niveau i Le nombre d'étapes.

int fun(int n){  
    if (n==1||n==2)  
        return n;  
    /*判断n-1的状态有没有被计算过*/  
    if (!dp[n-1])  
        dp[n-1] = fun(n-1);  
    if(!dp[n-2])  
        dp[n-2]=fun(n-2);  
    return dp[n-1]+dp[n-2];  
}

3. Algorithme gourmand

L'algorithme gourmand signifie que lorsque vous résolvez un problème, faites toujours le meilleur choix du moment. En d’autres termes, nous ne considérons pas la solution optimale globale, mais élaborons uniquement une solution optimale locale dans un certain sens. L'algorithme glouton n'obtient pas la solution globale optimale pour tous les problèmes.La clé est la sélection de la stratégie gloutonne. La stratégie glouton sélectionnée ne doit pas avoir de séquelles, c'est-à-dire que le processus précédent d'un certain état n'affectera pas l'état suivant et. est uniquement lié à l’état actuel.
Les étapes générales pour résoudre les problèmes sont :
1. Établir un modèle mathématique pour décrire le problème ;
2. Diviser le problème à résoudre en plusieurs sous-problèmes ;
3. Résoudre chaque sous-problème et obtenir la solution optimale locale ; du sous-problème ;

4. Combiner la solution optimale locale du sous-problème en une solution au problème original.

Exemple : Problème de change d'argent

Ce problème est plus courant dans notre vie quotidienne. Supposons qu’il existe des billets c0, c1, c2, c3, c4, c5 et c6 de 1 yuan, 2 yuans, 5 yuans, 10 yuans, 20 yuans, 50 yuans et 100 yuans respectivement. Maintenant, pour utiliser cet argent pour payer K yuans, combien de billets faut-il utiliser au moins ? En utilisant l'idée d'un algorithme glouton, il est évident que chaque étape ne peut utiliser que des billets de grande valeur nominale. Nous faisons naturellement cela dans notre vie quotidienne. Les valeurs ont été classées par ordre croissant dans le programme.

public class charge {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
    	int res = charge(84);
    	System.out.println(res);
    }
 
   private static int charge(int money) {
	   int count = 0;
       int value[] = {50,20,10,5,2,1};
       while(money>0){
       	int length = value.length;
       	for(int i=0;i=value[i]){
       			money=money-value[i];
       			count++;
       			//System.out.println(money);
       		}
       	}
       }
       return count;
	}     
}

4. Méthode de backtracking 

 La méthode de backtracking est une méthode de recherche systématique de solutions aux problèmes. Pendant le processus de recherche, essayez de trouver la solution au problème. Si vous constatez que vous ne la trouvez pas, prenez du recul et remontez (le processus d'élagage). Le retour en arrière peut être utilisé pour de nombreux problèmes complexes et à grande échelle. 
 L'idée de base de la méthode de backtracking est de suivre la stratégie de recherche en profondeur et de commencer la recherche à partir du nœud racine. Lorsque vous atteignez un certain nœud, il est nécessaire de déterminer s'il contient la solution au problème. inclus, continuez la recherche à partir de ce nœud. S'il n'est pas inclus, recherchez à partir de ce nœud. Si la méthode de backtracking est utilisée pour trouver toutes les solutions au problème, elle doit être retracée jusqu'à la racine et tous les sous-arbres réalisables du nœud racine doivent avoir été recherchés avant de se terminer. Et si vous utilisez la méthode du retour en arrière pour trouver une solution, vous pouvez terminer tant que vous trouvez une solution au problème. 

      Fonctions d'élagage couramment utilisées dans la méthode de backtracking : (1) Fonction de contrainte : soustraire les sous-arbres qui ne satisfont pas aux contraintes au niveau du nœud. (2) Fonction limite : soustraire les sous-arbres qui ne peuvent pas obtenir la solution optimale. 
Étapes générales : 
1. Pour le problème donné, déterminez l'espace de solution du problème 
2. Utilisez des méthodes adaptées à la recherche pour organiser l'espace de solution 
3. Utilisez d'abord la profondeur pour rechercher l'espace de solution 

4. Utilisation pendant le processus de recherche Les fonctions d'élagage évitent les recherches invalides. 
 5. La méthode Branch andbound 
 est similaire à la méthode de backtracking C'est aussi un algorithme qui recherche la solution du problème sur l'arbre de l'espace de solution T du problème. Cependant, en général, les objectifs de solution de la méthode branch andbound et de la méthode backtracking sont différents. Le but de la solution de la méthode de backtracking est de trouver toutes les solutions dans T qui satisfont aux conditions de contrainte, tandis que le but de la méthode de branchement et de liaison est de trouver une solution qui satisfait les conditions de contrainte, ou de trouver une solution qui satisfait la contrainte. conditions pour qu'un certain objectif La valeur de la fonction atteigne la solution maximale ou minimale, qui est la solution optimale dans un certain sens. 
(1) Algorithme de recherche de branche
 La soi-disant « branche » consiste à utiliser la stratégie de largeur d'abord pour rechercher toutes les branches du nœud E en séquence, c'est-à-dire tous les nœuds adjacents, éliminer les nœuds qui ne le font pas. respecter les contraintes et les nœuds restants Cliquez pour rejoindre la table des nœuds coulants. Sélectionnez ensuite un nœud dans le tableau comme prochain nœud E et poursuivez la recherche. 
 Selon la manière de sélectionner le prochain nœud E, il y aura plusieurs méthodes de recherche de branche différentes. 
 1) Recherche FIFO 
 2) Recherche LIFO 
 3) Recherche de file d'attente prioritaire 
 (2) Algorithme de recherche de branchement et de liaison 
 Le processus général de la méthode de branchement et de liaison 
 En raison des différents objectifs de solution, la méthode de branchement et de liaison et la méthode de retour en arrière ont des méthodes de recherche différentes sur l'arbre de l'espace de solution T. La méthode de retour en arrière recherche l'arbre d'espace de solutions T d'une manière en profondeur d'abord, tandis que la méthode de branchement et de liaison recherche l'arbre d'espace de solutions T d'abord en largeur ou d'une manière au moindre coût. 
 La stratégie de recherche de la méthode branch andbound est la suivante : au niveau du nœud d'expansion, générez d'abord tous ses nœuds enfants (branche), puis sélectionnez le point de paire d'expansion suivant dans la table des nœuds actifs actuelle. Afin de sélectionner efficacement le nœud d'expansion suivant et d'accélérer le processus de recherche, au niveau de chaque nœud actif, une valeur de fonction (liée) est calculée, et sur la base de ces valeurs de fonction calculées, une meilleure valeur est sélectionnée dans la table de nœuds actifs actuelle. Les nœuds favorables servent de nœuds d'expansion pour faire avancer la recherche vers la branche présentant la solution optimale sur l'arbre de l'espace de solutions, de manière à trouver une solution optimale le plus rapidement possible. 
 La méthode branch andbound recherche souvent l'arbre d'espace de solution du problème d'une manière première en largeur ou au coût minimum (bénéfice maximum). L'arbre de l'espace de solution d'un problème est un arbre ordonné qui représente l'espace de solution du problème. Les arbres les plus courants incluent les arbres de sous-ensembles et les arbres de permutation. Lors de la recherche dans l'arborescence de l'espace de solutions d'un problème, la méthode de branchement et de liaison et la méthode de retour en arrière utilisent des méthodes d'expansion différentes pour le nœud d'expansion actuel. Dans la méthode branch-and-bound, chaque nœud actif n'a qu'une seule chance de devenir un nœud d'extension. Une fois qu'un nœud actif devient un nœud d'extension, tous ses nœuds enfants sont générés en même temps. Parmi ces nœuds enfants, ceux qui conduisent à des solutions irréalisables ou à des solutions non optimales sont ignorés et les nœuds enfants restants sont ajoutés à la liste des nœuds actifs. Par la suite, un nœud est extrait de la table des nœuds actifs pour devenir le nœud d'expansion actuel, et le processus d'expansion de nœud ci-dessus est répété. Ce processus se poursuit jusqu'à ce que la solution souhaitée soit trouvée ou que la table liveknot soit vide. 
Quelques différences entre la méthode de retour en arrière et la méthode de branchement et de liaison

 Certains problèmes peuvent en fait être bien résolus en utilisant soit la méthode de retour en arrière, soit la méthode de branchement et de liaison, mais d'autres ne le sont pas. Peut-être avons-nous besoin d'une analyse plus spécifique : quand utiliser branch andbound et quand utiliser le backtracking ? 
Quelques différences entre la méthode de backtracking et la méthode de branchement et de liaison : 
 La méthode de recherche de la méthode pour l'arbre de l'espace de solution Structures de données communes pour le stockage des nœuds Applications courantes des fonctionnalités de stockage des nœuds 
 La méthode de backtracking recherche d'abord en profondeur tous les sous-marins possibles -nœuds du nœud actif de la pile Une fois les points parcourus, ils sont extraits de la pile pour découvrir toutes les solutions qui satisfont aux contraintes
 Méthode de branchement et de liaison Largeur d'attente première ou consommation minimale file d'attente de recherche prioritaire, file d'attente prioritaire Chaque nœud n'a que une chance de devenir un nœud actif pour découvrir qui satisfait aux contraintes Une solution ou la solution optimale dans un sens spécifique
Pour plus de connaissances connexes, veuillez visiter la colonne FAQ ! 
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!