Stratégies de conception d'algorithmes courantes :
1. Diviser pour régner
L'idée de conception de diviser pour régner La méthode consiste à diviser un grand problème difficile à résoudre directement en k sous-problèmes plus petits. Ces sous-problèmes sont indépendants les uns des autres et identiques au problème d'origine, puis chacun est décomposé pour diviser et conquérir. .
La méthode diviser pour régner est souvent utilisée en combinaison avec la récursivité : en appliquant à plusieurs reprises la méthode diviser pour régner, le sous-problème peut être rendu cohérent avec le type de problème d'origine et l'échelle est continuellement réduite. Finalement, le sous-problème est réduit au point où il est facile de trouver sa solution. Cela conduit naturellement à des algorithmes récursifs.
2. Programmation dynamique
La méthode de programmation dynamique est similaire à la méthode diviser pour régner, et son idée de base est de décomposer le problème d'origine en plusieurs sous -des problèmes. Contrairement à la méthode diviser pour régner, les sous-problèmes décomposés ne sont souvent pas indépendants les uns des autres. Dans ce cas, l’utilisation de la méthode diviser pour régner résoudra plusieurs fois certains sous-problèmes, ce qui est évidemment inutile. La méthode de programmation dynamique enregistre les réponses à tous les sous-problèmes résolus pendant le processus de résolution, évitant ainsi des résolutions répétées de sous-problèmes.
La programmation dynamique est souvent utilisée pour résoudre des problèmes d'optimisation. La possibilité d'appliquer la méthode de programmation dynamique à un problème d'optimisation dépend du fait que le problème possède les deux propriétés suivantes :
Propriétés de la sous-structure optimale :
Lorsque la solution optimale du problème contient sa sous-structure problèmes Lorsque la solution optimale de , le problème est dit avoir des propriétés de sous-structure optimales.
La nature chevauchante des sous-problèmes :
La nature chevauchante des sous-problèmes signifie que les sous-problèmes décomposés du problème d'origine ne sont pas indépendants les uns des autres et se chevauchent.
3. Gourmand
Lorsqu'un problème a des propriétés de sous-structure optimales, il peut être résolu par programmation dynamique. Mais il existe parfois un algorithme plus simple, plus direct et plus efficace que la programmation dynamique : la méthode gloutonne. La méthode gloutonne fait toujours le meilleur choix pour le moment, ce qui signifie qu'elle ne prend pas en compte le choix optimal global. Le choix qu'elle fait n'est qu'un choix optimal local dans un certain sens.
4. Backtracking
La méthode de backtracking consiste à effectuer d'abord une recherche en profondeur sur l'arborescence de l'espace de solution du problème, mais avant d'effectuer DFS sur chaque nœud, le Le nœud doit être jugé en premier. Est-il possible de contenir une solution au problème. S'il n'est définitivement pas inclus, ignorez la recherche du sous-arbre enraciné à ce nœud et revenez à ses nœuds ancêtres couche par couche. S'il est possible de le contenir, entrez le sous-arbre et effectuez DFS.
5. Branche et lié
La stratégie de recherche de la méthode branche et liée consiste à générer d'abord tous ses nœuds enfants (branche) au nœud actuel, et pour Chaque nœud enfant qui satisfait aux conditions de contrainte calcule une valeur de fonction (liée), puis tous les nœuds enfants qui satisfont aux conditions de contrainte sont ajoutés à la file d'attente prioritaire des nœuds actifs de l'arborescence de l'espace de solution. Sélectionnez ensuite le nœud avec la priorité la plus élevée dans la file d'attente de priorité des nœuds actifs actuelle (la priorité du nœud est déterminée par la valeur de sa fonction limite) comme nouveau nœud actuel. Ce processus est répété jusqu'à ce qu'un nœud feuille soit atteint. Le nœud feuille atteint est 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!