Cinq algorithmes couramment utilisés

Cinq algorithmes couramment utilisés

1. Algorithme gourmand

L'algorithme glouton peut obtenir la solution optimale locale au problème, mais n'obtient pas nécessairement la solution optimale globale. En même temps, la qualité de l'obtention de la solution optimale dépend du choix de la stratégie glouton. La caractéristique est qu’il est simple et permet d’obtenir des solutions optimales locales. Tout comme la méthode du bâton battant le chien, le niveau de Hong Qigong et de Lu Youjia est très différent pour le même ensemble de méthodes du bâton. Par conséquent, il s'agit également d'un algorithme gourmand, et différentes stratégies gourmandes conduiront à des résultats très différents.

2. Algorithme de programmation dynamique

Lorsque le problème d'optimisation comporte des sous-problèmes répétés et des sous-structures optimales, il est temps que la programmation dynamique apparaisse. Le cœur de l'algorithme de programmation dynamique est de fournir une mémoire pour mettre en cache les résultats des sous-problèmes répétés, évitant ainsi un grand nombre de calculs répétés dans le processus récursif. La difficulté de l’algorithme de programmation dynamique est de savoir comment transformer le problème en un problème pouvant être résolu par un algorithme de programmation dynamique. Lorsque le nombre de sous-problèmes répétés est relativement faible, l’effet de la programmation dynamique sera faible. Si le problème comporte un grand nombre de sous-problèmes répétés, alors la programmation dynamique est très mauvaise pour améliorer l'efficacité. Tout comme les arts martiaux, si l’adversaire est fort, il sera plus fort ; si l’adversaire est plus fort, il sera plus faible.

3. Algorithme Diviser pour régner

La logique de l'algorithme Diviser pour régner est plus simple, il ne s'agit que d'un seul mot, diviser pour régner. L'algorithme diviser pour régner divise un grand problème en plusieurs sous-problèmes, puis continue de diviser les sous-problèmes vers le bas, jusqu'aux cas de base, en résolvant les cas de base, étape par étape, jusqu'à l'original. le gros problème est enfin résolu. L'algorithme diviser pour régner est une application typique de la récursivité.

4. Algorithme de retour en arrière

L'algorithme de retour en arrière est une application typique de la stratégie de profondeur d'abord. L'algorithme de retour en arrière suit un chemin si le chemin est différent. puis revenez en arrière. Allez sur la route bifurquée

précédente, choisissez un chemin à parcourir et continuez à répéter ainsi jusqu'à ce que tous les chemins soient parcourus. Le problème des huit reines est un problème classique d'algorithme de retour en arrière, et un autre scénario d'application classique est le problème du labyrinthe.

5. Algorithme de branchement et de liaison

L'algorithme de retour en arrière est axé sur la profondeur, donc la méthode de branchement et de liaison est un exemple classique de largeur d'abord. . De manière générale, la méthode de backtracking parcourt tout l'espace de solutions pour obtenir toutes les solutions au problème, tandis que la méthode de branchement et de liaison consiste à obtenir une solution (d'une manière générale, à obtenir la solution optimale).

Tutoriel recommandé : "Tutoriel PHP"

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!