Comment programmer pour trouver le nombre de paires ordonnées ou le nombre de paires inversées d'un ensemble de données ?
Comparez chaque nombre avec le nombre qui le suit pour voir combien sont plus petits que lui. Nous enregistrons le nombre de nombres inférieurs à k. De cette façon, après avoir examiné chaque nombre, nous résumons les valeurs k correspondant à chaque nombre. La somme finale obtenue est le nombre de paires dans l'ordre inverse. Cependant, la complexité temporelle de cette opération est O(n^2).
Nous pouvons diviser le tableau en deux moitiés, A1 et A2, calculer respectivement le nombre de paires d'ordre inverse K1 et K2 de A1 et A2, puis calculer le nombre de paires d'ordre inverse K3 entre A1 et A2. Alors le nombre de paires d’ordre inverse dans le tableau A est égal à K1+K2+K3. Avec l'aide de l'algorithme de tri par fusion
Est-il nécessaire de trier les fichiers de commande de 10 Go par montant ?
Nous pouvons d'abord scanner la commande et diviser le fichier de 10 Go en plusieurs tranches de montant en fonction du montant de la commande. Par exemple, le montant de la commande entre 1 et 100 yuans est placé dans un petit fichier, le montant de la commande entre 101 et 200 est placé dans un autre fichier, et ainsi de suite. De cette manière, chaque petit fichier peut être chargé dans la mémoire pour être trié séparément, et finalement ces petits fichiers ordonnés sont fusionnés pour obtenir les données de commande finales commandées de 10 Go.
Algorithme de retour en arrière
Scénarios d'application : recherche en profondeur, correspondance d'expressions régulières, analyse syntaxique dans les principes de compilation. De nombreux problèmes mathématiques classiques peuvent être résolus à l'aide de l'algorithme de backtracking, tels que le Sudoku, les huit dames, le sac à dos 0-1, la coloration des graphiques, le problème du voyageur de commerce, la permutation totale, etc.
L'idée de traitement du retour en arrière est quelque peu similaire à la recherche par énumération. Nous énumérons toutes les solutions et trouvons celle qui répond à nos attentes. Afin d'énumérer régulièrement toutes les solutions possibles et d'éviter les omissions et les duplications, nous divisons le processus de résolution de problèmes en plusieurs étapes. A chaque étape, nous serons confrontés à une bifurcation. Nous choisissons d'abord un chemin au hasard. Lorsque nous constatons que ce chemin ne fonctionne pas (ne répond pas à la solution attendue), nous revenons à la bifurcation précédente et. choisissez un autre chemin. Continuez à marcher.
Problème des huit reines
Nous avons un échiquier 8x8 et nous voulons y placer 8 pièces d'échecs (reines). Chaque pièce d'échecs ne peut pas avoir une autre pièce d'échecs dans la rangée, la colonne ou la diagonale.
Sac à dos 1.0-1
De nombreux scénarios peuvent être résumés dans ce modèle de problème. La solution classique à ce problème est la programmation dynamique, mais il existe également une solution simple mais moins efficace, qui est l’algorithme de backtracking dont nous parlons aujourd’hui.
Nous avons un sac à dos et le poids total du sac à dos est de Wkg. Nous avons maintenant n éléments, chacun ayant un poids différent et étant indivisible. Nous souhaitons maintenant sélectionner quelques éléments et les charger dans notre sac à dos. Comment maximiser le poids total des objets dans un sac à dos sans dépasser le poids que le sac à dos peut supporter ?
Pour chaque article, il y a deux options, le mettre dans le sac à dos ou ne pas le mettre dans le sac à dos. Pour n éléments, il existe 2 ^ n façons de les installer. Supprimez ceux dont le poids total dépasse Wkg et sélectionnez celui dont le poids total est le plus proche de Wkg parmi les méthodes d'installation restantes. Mais comment énumérer de manière exhaustive ces 2^n manières de faire semblant, sans répétition ?
Méthode de retour en arrière : Nous pouvons organiser les éléments dans l'ordre, et l'ensemble du problème est décomposé en n étapes, et chaque étape correspond à la façon de choisir un élément. Traitez d'abord le premier élément, choisissez de le charger ou non, puis traitez les éléments restants de manière récursive.
Programmation dynamique
La programmation dynamique est plus adaptée pour résoudre des problèmes optimaux, tels que trouver des valeurs maximales, des valeurs minimales, etc. Cela peut réduire considérablement la complexité du temps et améliorer l’efficacité de l’exécution du code.
Problème de sac à dos 0-1
Pour un ensemble d'articles indivisibles de poids différents, nous devons en sélectionner quelques-uns à mettre dans le sac à dos. En partant du principe que la limite de poids maximum du sac à dos est respectée, quel est le poids total maximum des articles dans le sac à dos ?
Pensée :
(1) Divisez l'ensemble du processus de résolution en n étapes, et chaque étape décidera s'il faut mettre un article dans le sac à dos. Une fois que chaque article a été décidé (à mettre dans le sac à dos ou à ne pas mettre dans le sac à dos), le poids des articles dans le sac à dos aura de nombreuses situations, c'est-à-dire qu'il atteindra de nombreux états différents, qui correspondent à l'arbre récursif, c'est-à-dire qu'il existe de nombreux nœuds différents.
(2) Nous fusionnons les états répétés (nœuds) de chaque couche, enregistrons uniquement les différents états, puis dérivons l'ensemble d'états de la couche suivante en fonction de l'ensemble d'états de la couche précédente. Nous pouvons fusionner les états répétés de chaque couche pour garantir que le nombre d'états différents dans chaque couche ne dépassera pas w (w représente le poids transporté par le sac à dos), qui est de 9 dans l'exemple.
Divisez n étapes. Chaque étape est dérivée en fonction de l'étape précédente et avance dynamiquement pour éviter les calculs répétés.
La complexité temporelle de l'utilisation de l'algorithme de retour en arrière pour résoudre ce problème est O(2^n), qui est exponentielle. Alors, quelle est la complexité temporelle de la solution de programmation dynamique ?
La partie la plus longue est la boucle for à deux niveaux dans le code, donc la complexité temporelle est O(n*w). n représente le nombre d'articles et w représente le poids total que le sac à dos peut supporter. Nous devons demander un tableau bidimensionnel supplémentaire de n fois w+1, ce qui consomme beaucoup d'espace. On dira donc parfois que la programmation dynamique est une solution qui échange de l’espace contre du temps.
0-1 Version améliorée du problème du sac à dos
Pour un ensemble d'articles indivisibles de poids et de valeurs différents, nous choisissons de mettre certains articles dans un sac à dos en partant du principe que la limite de poids maximale du sac à dos est respectée, quelle est la valeur totale maximale des articles qui peuvent être. chargé dans le sac à dos ?
Quels types de problèmes peuvent être résolus par la programmation dynamique ?
Trois caractéristiques d'un seul modèle
Un modèle : modèle de solution optimale de prise de décision en plusieurs étapes
Trois fonctionnalités :
Sous-structure optimale, la solution optimale du problème contient la solution optimale du sous-problème
Aucune séquelle, le premier sens est que lors de la dérivation du statut des étapes ultérieures, nous ne nous soucions que des étapes précédentes La valeur d'état de , ne se soucie pas de la façon dont cet état est dérivé étape par étape. Le deuxième sens est qu’une fois que le statut d’une certaine étape est déterminé, il ne sera pas affecté par les décisions des étapes ultérieures. (Ce dernier n'affecte pas le précédent.)
Des sous-problèmes répétés, des séquences de décision différentes, peuvent produire des états répétés lorsqu'ils atteignent un certain même stade.
Résumé de deux idées de résolution de problèmes de programmation dynamique
1. Méthode de la table de transition d'état
Généralement, les problèmes qui peuvent être résolus par programmation dynamique peuvent être résolus par recherche par force brute à l'aide de l'algorithme de backtracking. Dessinez l'arbre de récursivité. À partir de l'arbre de récursivité, nous pouvons facilement voir s'il existe des sous-problèmes répétés et comment les sous-problèmes répétés sont générés.
Après avoir trouvé le sous-problème répété, nous avons deux façons de le résoudre. La première consiste à utiliser directement la méthode de retour en arrière et de « mémo » pour éviter les sous-problèmes répétés. En termes d'efficacité d'exécution, cela n'est pas différent de l'idée de solution de programmation dynamique. La deuxième méthode consiste à utiliser la programmation dynamique, la méthode de la table de transition d'état.
Dessinons d’abord un tableau de statut. Les tables d'états sont généralement bidimensionnelles, vous pouvez donc les considérer comme un tableau bidimensionnel. Parmi eux, chaque état contient trois variables, lignes, colonnes et valeurs de tableau. Nous remplissons chaque état du tableau d'état par étapes selon le processus de prise de décision, d'avant en arrière, et selon la relation récursive. Enfin, nous traduisons ce processus de remplissage de formulaire récursif en code, qui est du code de programmation dynamique.
nécessite la représentation de nombreuses variables, et la table d'état correspondante peut être de grande dimension, comme en trois dimensions ou en quatre dimensions. À l’heure actuelle, nous ne sommes pas en mesure d’utiliser la méthode des tables de transition d’état pour le résoudre. D'une part, c'est parce que les tableaux de transition d'état de grande dimension sont difficiles à dessiner et à représenter, et d'autre part, c'est parce que le cerveau humain n'est vraiment pas doué pour penser aux choses de grande dimension.
2. Méthode d'équation de transition d'état
Nous devons analyser comment un certain problème peut être résolu de manière récursive à travers des sous-problèmes, ce qu'on appelle la sous-structure optimale. Sur la base de la sous-structure optimale, écrivez une formule récursive, qui est ce qu'on appelle l'équation de transition d'état. Avec l’équation de transition d’état, l’implémentation du code est très simple. Généralement, nous avons deux méthodes d'implémentation de code, l'une est récursion plus "mémo" et l'autre est récursivité itérative.
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
Je tiens à souligner que tous les problèmes ne conviennent pas aux deux idées de résolution de problèmes. Certains problèmes peuvent être plus clairs avec la première façon de penser, et certains problèmes peuvent être plus clairs avec la deuxième façon de penser. Par conséquent, vous devez considérer le problème spécifique pour décider quelle méthode de résolution de problèmes utiliser.
Méthode de la table de transition d'étatL'idée de résolution de problèmes peut être résumée grossièrement comme suit : Mise en œuvre de l'algorithme de retour en arrière - Définir l'état - Dessiner l'arbre de récursion - Rechercher les sous-problèmes en double - Dessiner la table de transition d'état - Remplissez le tableau en fonction à la relation de récursion - Traduisez le processus de remplissage de table en code . L'idée générale de la méthode de l'équation de transition d'état peut être résumée comme suit : Trouver la sous-structure optimale - écrire l'équation de transition d'état - traduire l'équation de transition d'état en code.
Comment quantifier la similarité de deux chaînes ?
Distance d'édition fait référence au nombre minimum d'opérations d'édition requises pour convertir une chaîne en une autre chaîne (comme l'ajout d'un caractère, la suppression d'un caractère, le remplacement d'un caractère). Plus la distance d’édition est grande, plus la similarité entre les deux chaînes est faible ; à l’inverse, plus la distance d’édition est petite, plus la similarité entre les deux chaînes est grande. Pour deux chaînes identiques, la distance d'édition est de 0.
Il existe de nombreuses méthodes de calcul différentes pour la distance d'édition, les plus connues sont Distance de Levenshtein et Longueur de sous-chaîne commune la plus longue. Parmi eux, la distance de Levinstein permet trois opérations d'édition d'ajout, de suppression et de remplacement de caractères, et la longueur de la sous-chaîne commune la plus longue n'autorise que deux opérations d'édition d'ajout et de suppression de caractères.
La distance de Lewenstein et la plus longue longueur de sous-chaîne commune analysent la similitude des chaînes sous deux perspectives complètement opposées. La taille de la distance de Levenstein représente la différence entre deux chaînes ; et la taille de la sous-chaîne commune la plus longue représente la similitude entre deux chaînes.
La distance de Levenstein entre deux chaînes mitcmu et mtacnu est de 3, et la longueur de la sous-chaîne commune la plus longue est de 4.
Comment calculer la distance de Levenstein par programme ?
Cette question consiste à trouver le nombre minimum de modifications requises pour changer une chaîne en une autre chaîne. L'ensemble du processus de résolution implique plusieurs étapes de prise de décision. Nous devons examiner tour à tour si chaque caractère d'une chaîne correspond aux caractères d'une autre chaîne, comment le traiter s'il correspond et comment le traiter s'il ne correspond pas. . Par conséquent, ce problème est conforme au modèle de solution optimale de prise de décision en plusieurs étapes.
Algorithme recommandé
Utilise la distance des vecteurs pour trouver la similitude.
Recherche : Comment utiliser l'algorithme de recherche A* pour implémenter la fonction de recherche de chemin dans le jeu ?
Alors, comment trouver rapidement un itinéraire sous-optimal proche de l'itinéraire le plus court ?
Cet algorithme de planification de chemin rapide est l'algorithme A* que nous allons apprendre aujourd'hui. En fait, l'algorithme A* est une optimisation et une transformation de l'algorithme de Dijkstra.
Estimez approximativement la longueur du chemin entre le sommet et le point final à travers la distance en ligne droite entre le sommet et le point final, qui est la distance euclidienne (remarque : la longueur du chemin et la distance en ligne droite sont deux concepts)
Ceci la distance est enregistrée sous la forme h(i) (i représente le numéro de ce sommet), le nom professionnel est fonction heuristique (fonction heuristique)
Parce que la formule de calcul de la distance euclidienne impliquera le calcul fastidieux du signe racine , donc , nous utilisons généralement une autre formule de calcul de distance plus simple, à savoir la distance de Manhattan (distance de Manhattan)
La distance de Manhattan est la somme des distances entre les coordonnées horizontales et verticales entre deux points. Le processus de calcul implique uniquement l'addition, la soustraction et l'inversion des bits de signe, il est donc plus efficace que la distance euclidienne.
int hManhattan(Vertex v1, Vertex v2) { // Le sommet représente le sommet, qui est défini plus tard
Retour Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}
f(i)=g(i)+h(i), la longueur du trajet g(i) entre le sommet et le point de départ, et la longueur estimée du trajet du sommet au point final h(i). Le nom professionnel de f(i) est La méthode est la fonction d'évaluation.
Un algorithme* est une simple modification de l'algorithme de Dijkstra. Le plus petit f(i) est répertorié en premier.
Il existe trois différences principales entre celui-ci et l'implémentation du code de l'algorithme de Dijkstra :
La façon dont la file d'attente prioritaire est construite est différente. L'algorithme A* construit une file d'attente prioritaire basée sur la valeur f (c'est-à-dire f(i)=g(i)+h(i) que nous venons de mentionner), tandis que l'algorithme Dijkstra construit une file d'attente prioritaire basée sur la valeur dist ( c'est-à-dire le g que nous venons de mentionner (i)) pour construire une file d'attente prioritaire ;
Un algorithme* mettra à jour la valeur f de manière synchrone lors de la mise à jour de la valeur de distribution du sommet
Les conditions pour la fin de la boucle sont ; également différent. L'algorithme de Dijkstra se termine lorsque le point final est retiré de la file d'attente, et l'algorithme A* se termine une fois que le parcours atteint le point final.
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
