DAA - Guide rapide

Un algorithme est un ensemble d'étapes d'opérations pour résoudre un problème en effectuant des tâches de calcul, de traitement de données et de raisonnement automatisé. Un algorithme est une méthode efficace qui peut être exprimée dans une quantité limitée de temps et d'espace.

Un algorithme est le meilleur moyen de représenter la solution d'un problème particulier d'une manière très simple et efficace. Si nous avons un algorithme pour un problème spécifique, nous pouvons l'implémenter dans n'importe quel langage de programmation, ce qui signifie que lealgorithm is independent from any programming languages.

Conception d'algorithmes

Les aspects importants de la conception d'algorithmes incluent la création d'un algorithme efficace pour résoudre un problème de manière efficace en utilisant un minimum de temps et d'espace.

Pour résoudre un problème, différentes approches peuvent être suivies. Certaines d'entre elles peuvent être efficaces en termes de consommation de temps, tandis que d'autres approches peuvent être efficaces en mémoire. Cependant, il faut garder à l'esprit que la consommation de temps et l'utilisation de la mémoire ne peuvent pas être optimisées simultanément. Si nous avons besoin d'un algorithme pour s'exécuter en moins de temps, nous devons investir dans plus de mémoire et si nous avons besoin d'un algorithme pour fonctionner avec moins de mémoire, nous avons besoin de plus de temps.

Étapes de développement du problème

Les étapes suivantes sont impliquées dans la résolution des problèmes de calcul.

• Définition du problème
• Développement d'un modèle
• Spécification d'un algorithme
• Concevoir un algorithme
• Vérification de l'exactitude d'un algorithme
• Analyse d'un algorithme
• Implémentation d'un algorithme
• Test de programme
• Documentation

Caractéristiques des algorithmes

Les principales caractéristiques des algorithmes sont les suivantes -

• Les algorithmes doivent avoir un nom unique

• Les algorithmes doivent avoir un ensemble défini explicitement d'entrées et de sorties

• Les algorithmes sont bien ordonnés avec des opérations sans ambiguïté

• Les algorithmes s'arrêtent dans un laps de temps limité. Les algorithmes ne doivent pas fonctionner à l'infini, c'est-à-dire qu'un algorithme doit se terminer à un moment donné

Pseudocode

Le pseudocode donne une description de haut niveau d'un algorithme sans l'ambiguïté associée au texte brut, mais aussi sans avoir besoin de connaître la syntaxe d'un langage de programmation particulier.

Le temps d'exécution peut être estimé d'une manière plus générale en utilisant le pseudocode pour représenter l'algorithme comme un ensemble d'opérations fondamentales qui peuvent ensuite être comptées.

Différence entre l'algorithme et le pseudocode

Un algorithme est une définition formelle avec certaines caractéristiques spécifiques qui décrit un processus, qui pourrait être exécuté par une machine informatique complète de Turing pour effectuer une tâche spécifique. Généralement, le mot «algorithme» peut être utilisé pour décrire toute tâche de haut niveau en informatique.

D'autre part, le pseudocode est une description lisible par l'homme informelle et (souvent rudimentaire) d'un algorithme en laissant de nombreux détails granulaires. L'écriture d'un pseudocode n'a aucune restriction de styles et son seul objectif est de décrire les étapes de haut niveau de l'algorithme d'une manière très réaliste en langage naturel.

Par exemple, voici un algorithme pour le tri par insertion.

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

Voici un pseudo-code qui décrit comment le processus abstrait de haut niveau mentionné ci-dessus dans l'algorithme Insertion-Sort pourrait être décrit de manière plus réaliste.

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

Dans ce didacticiel, les algorithmes seront présentés sous la forme d'un pseudocode, similaire à bien des égards à C, C ++, Java, Python et d'autres langages de programmation.

Dans l'analyse théorique des algorithmes, il est courant d'estimer leur complexité au sens asymptotique, c'est-à-dire d'estimer la fonction de complexité pour une entrée arbitrairement grande. Le terme"analysis of algorithms" a été inventé par Donald Knuth.

L'analyse des algorithmes est une partie importante de la théorie de la complexité de calcul, qui fournit une estimation théorique des ressources requises d'un algorithme pour résoudre un problème de calcul spécifique. La plupart des algorithmes sont conçus pour fonctionner avec des entrées de longueur arbitraire. L'analyse des algorithmes consiste à déterminer la quantité de ressources temporelles et spatiales nécessaires pour l'exécuter.

Habituellement, l'efficacité ou le temps d'exécution d'un algorithme est indiqué comme une fonction reliant la longueur d'entrée au nombre d'étapes, appelée time complexity, ou volume de mémoire, appelé space complexity.

Le besoin d'analyse

Dans ce chapitre, nous discuterons de la nécessité d'analyser les algorithmes et de la manière de choisir un meilleur algorithme pour un problème particulier, car un problème de calcul peut être résolu par différents algorithmes.

En considérant un algorithme pour un problème spécifique, nous pouvons commencer à développer la reconnaissance de formes afin que des types de problèmes similaires puissent être résolus à l'aide de cet algorithme.

Les algorithmes sont souvent assez différents les uns des autres, bien que l'objectif de ces algorithmes soit le même. Par exemple, nous savons qu'un ensemble de nombres peut être trié à l'aide de différents algorithmes. Le nombre de comparaisons effectuées par un algorithme peut varier avec d'autres pour la même entrée. Par conséquent, la complexité temporelle de ces algorithmes peut différer. Dans le même temps, nous devons calculer l'espace mémoire requis par chaque algorithme.

L'analyse de l'algorithme est le processus d'analyse de la capacité de résolution de problèmes de l'algorithme en termes de temps et de taille requis (la taille de la mémoire pour le stockage pendant la mise en œuvre). Cependant, la principale préoccupation de l'analyse des algorithmes est le temps ou les performances requis. Généralement, nous effectuons les types d'analyses suivants -

• Worst-case - Le nombre maximum de pas effectués sur n'importe quelle instance de taille a.

• Best-case - Le nombre minimum de pas effectués sur toute instance de taille a.

• Average case - Un nombre moyen de pas effectués sur n'importe quelle instance de taille a.

• Amortized - Une séquence d'opérations appliquée à l'entrée de taille a moyenné au fil du temps.

Pour résoudre un problème, nous devons tenir compte du temps ainsi que de la complexité de l'espace car le programme peut s'exécuter sur un système où la mémoire est limitée mais l'espace adéquat est disponible ou peut être l'inverse. Dans ce contexte, si l'on comparebubble sort et merge sort. Le tri par bulles ne nécessite pas de mémoire supplémentaire, mais le tri par fusion nécessite de l'espace supplémentaire. Bien que la complexité temporelle du tri par bulle soit plus élevée que celle du tri par fusion, nous pouvons avoir besoin d'appliquer le tri par bulle si le programme doit s'exécuter dans un environnement où la mémoire est très limitée.

Pour mesurer la consommation de ressources d'un algorithme, différentes stratégies sont utilisées comme indiqué dans ce chapitre.

Analyse asymptotique

Le comportement asymptotique d'une fonction f(n) se réfère à la croissance de f(n) comme n devient grand.

Nous ignorons généralement les petites valeurs de n, puisque nous sommes généralement intéressés à estimer la lenteur du programme sur les gros intrants.

Une bonne règle de base est que plus le taux de croissance asymptotique est lent, meilleur est l'algorithme. Bien que ce ne soit pas toujours vrai.

Par exemple, un algorithme linéaire $f(n) = d * n + k$ est toujours asymptotiquement meilleur qu'un quadratique, $f(n) = c.n^2 + q$.

Résolution d'équations de récurrence

Une récurrence est une équation ou une inégalité qui décrit une fonction en fonction de sa valeur sur des entrées plus petites. Les récurrences sont généralement utilisées dans le paradigme diviser pour conquérir.

Considérons T(n) être le temps d'exécution sur un problème de taille n.

Si la taille du problème est suffisamment petite, dites n < c où c est une constante, la solution simple prend un temps constant, qui s'écrit θ(1). Si la division du problème produit un certain nombre de sous-problèmes de taille$\frac{n}{b}$.

Pour résoudre le problème, le temps requis est a.T(n/b). Si nous considérons que le temps requis pour la division estD(n) et le temps nécessaire pour combiner les résultats des sous-problèmes est C(n), la relation de récurrence peut être représentée par -

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

Une relation de récurrence peut être résolue en utilisant les méthodes suivantes -

• Substitution Method - Dans cette méthode, nous devinons une borne et en utilisant l'induction mathématique nous prouvons que notre hypothèse était correcte.

• Recursion Tree Method - Dans cette méthode, un arbre de récurrence est formé où chaque nœud représente le coût.

• Master’s Theorem - C'est une autre technique importante pour trouver la complexité d'une relation de récurrence.

Analyse amortie

L'analyse amortie est généralement utilisée pour certains algorithmes où une séquence d'opérations similaires est effectuée.

• L'analyse amortie fournit une limite sur le coût réel de la séquence entière, au lieu de limiter le coût de la séquence d'opérations séparément.

• L'analyse amortie diffère de l'analyse de cas moyen; la probabilité n'est pas impliquée dans l'analyse amortie. L'analyse amortie garantit la performance moyenne de chaque opération dans le pire des cas.

Ce n'est pas seulement un outil d'analyse, c'est une façon de penser la conception, car la conception et l'analyse sont étroitement liées.

Méthode d'agrégation

La méthode agrégée donne une vue globale d'un problème. Dans cette méthode, sin les opérations prennent le pire des cas T(n)au total. Ensuite, le coût amorti de chaque opération estT(n)/n. Bien que différentes opérations puissent prendre un temps différent, dans cette méthode, le coût variable est négligé.

Méthode comptable

Dans cette méthode, différentes charges sont affectées à différentes opérations en fonction de leur coût réel. Si le coût amorti d'une opération dépasse son coût réel, la différence est affectée à l'objet en tant que crédit. Ce crédit permet de payer les opérations ultérieures pour lesquelles le coût amorti est inférieur au coût réel.

Si le coût réel et le coût amorti de i^th opération sont $c_{i}$ et $\hat{c_{l}}$, puis

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

Méthode potentielle

Cette méthode représente le travail prépayé comme une énergie potentielle, au lieu de considérer le travail prépayé comme un crédit. Cette énergie peut être libérée pour payer les opérations futures.

Si nous exécutons n opérations commençant par une structure de données initiale D₀. Considérons,c_i comme coût réel et D_i comme structure de données de i^thopération. La fonction potentielle Ф correspond à un nombre réel Ф (D_i), le potentiel associé de D_i. Le coût amorti$\hat{c_{l}}$ peut être défini par

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

Par conséquent, le coût amorti total est

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

Table dynamique

Si l'espace alloué pour la table n'est pas suffisant, nous devons copier la table dans une table de plus grande taille. De même, si un grand nombre de membres sont effacés de la table, il est judicieux de réallouer la table avec une taille plus petite.

En utilisant l'analyse amortie, nous pouvons montrer que le coût amorti d'insertion et de suppression est constant et que l'espace inutilisé dans une table dynamique ne dépasse jamais une fraction constante de l'espace total.

Dans le prochain chapitre de ce didacticiel, nous aborderons brièvement les notations asymptotiques.

Dans la conception de l'algorithme, l'analyse de la complexité d'un algorithme est un aspect essentiel. La complexité algorithmique concerne principalement ses performances, sa vitesse ou sa lenteur.

La complexité d'un algorithme décrit l'efficacité de l'algorithme en termes de quantité de mémoire nécessaire pour traiter les données et le temps de traitement.

La complexité d'un algorithme est analysée selon deux perspectives: Time et Space.

Complexité temporelle

C'est une fonction décrivant le temps nécessaire pour exécuter un algorithme en fonction de la taille de l'entrée. "Temps" peut signifier le nombre d'accès à la mémoire effectués, le nombre de comparaisons entre les entiers, le nombre de fois qu'une boucle interne est exécutée, ou une autre unité naturelle liée à la quantité de temps réel que l'algorithme prendra.

Complexité spatiale

C'est une fonction décrivant la quantité de mémoire qu'un algorithme prend en termes de taille d'entrée de l'algorithme. On parle souvent de mémoire "supplémentaire" nécessaire, sans compter la mémoire nécessaire pour stocker l'entrée elle-même. Encore une fois, nous utilisons des unités naturelles (mais de longueur fixe) pour mesurer cela.

La complexité de l'espace est parfois ignorée parce que l'espace utilisé est minimal et / ou évident, mais parfois cela devient un problème aussi important que le temps.

Notations asymptotiques

Le temps d'exécution d'un algorithme dépend du jeu d'instructions, de la vitesse du processeur, de la vitesse d'E / S du disque, etc. Par conséquent, nous estimons l'efficacité d'un algorithme de manière asymptotique.

La fonction temporelle d'un algorithme est représentée par T(n), où n est la taille d'entrée.

Différents types de notations asymptotiques sont utilisés pour représenter la complexité d'un algorithme. Les notations asymptotiques suivantes sont utilisées pour calculer la complexité en temps d'exécution d'un algorithme.

• O - Grand Oh

• Ω - Gros oméga

• θ - Gros thêta

• o - Petit Oh

• ω - Petit oméga

O: Limite supérieure asymptotique

«O» (Big Oh) est la notation la plus couramment utilisée. Une fonctionf(n) peut être représenté est l'ordre de g(n) C'est O(g(n)), s'il existe une valeur d'entier positif n comme n₀ et une constante positive c tel que -

$f(n)\leqslant c.g(n)$ pour $n > n_{0}$ dans tous les cas

Par conséquent, la fonction g(n) est une limite supérieure pour la fonction f(n), comme g(n) pousse plus vite que f(n).

Exemple

Considérons une fonction donnée, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considérant $g(n) = n^3$,

$f(n)\leqslant 5.g(n)$ pour toutes les valeurs de $n > 2$

D'où la complexité de f(n) peut être représenté comme $O(g(n))$, c'est à dire $O(n^3)$

Ω: Limite inférieure asymptotique

On dit que $f(n) = \Omega (g(n))$ quand il existe une constante c cette $f(n)\geqslant c.g(n)$ pour toute valeur suffisamment grande de n. Icinest un entier positif. Cela signifie la fonctiong est une borne inférieure pour la fonction f; après une certaine valeur den, f ne descendra jamais en dessous g.

Exemple

Considérons une fonction donnée, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$.

Considérant $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ pour toutes les valeurs de $n > 0$.

D'où la complexité de f(n) peut être représenté comme $\Omega (g(n))$, c'est à dire $\Omega (n^3)$

θ: lié serré asymptotique

On dit que $f(n) = \theta(g(n))$ quand il existe des constantes c₁ et c₂ cette $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ pour toute valeur suffisamment grande de n. Icin est un entier positif.

Cela signifie la fonction g est une limite étroite pour la fonction f.

Exemple

Considérons une fonction donnée, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considérant $g(n) = n^3$, $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ pour toutes les grandes valeurs de n.

D'où la complexité de f(n) peut être représenté comme $\theta (g(n))$, c'est à dire $\theta (n^3)$.

O - Notation

La limite supérieure asymptotique fournie par O-notationpeut ou non être asymptotiquement serré. Le bond$2.n^2 = O(n^2)$ est asymptotiquement serré, mais la borne $2.n = O(n^2)$ n'est pas.

Nous utilisons o-notation pour désigner une limite supérieure qui n'est pas asymptotiquement serrée.

Nous définissons formellement o(g(n)) (peu-oh de g de n) comme l'ensemble f(n) = o(g(n)) pour toute constante positive $c > 0$ et il existe une valeur $n_{0} > 0$, tel que $0 \leqslant f(n) \leqslant c.g(n)$.

Intuitivement, dans le o-notation, la fonction f(n) devient insignifiant par rapport à g(n) comme ns'approche de l'infini; C'est,

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

Exemple

Considérons la même fonction, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considérant $g(n) = n^{4}$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

D'où la complexité de f(n) peut être représenté comme $o(g(n))$, c'est à dire $o(n^4)$.

ω - Notation

Nous utilisons ω-notationpour désigner une borne inférieure qui n'est pas asymptotiquement serrée. Cependant, formellement, nous définissonsω(g(n)) (petit-oméga de g de n) comme l'ensemble f(n) = ω(g(n)) pour toute constante positive C > 0 et il existe une valeur $n_{0} > 0$, tel que $ 0 \ leqslant cg (n) <f (n) $.

Par exemple, $\frac{n^2}{2} = \omega (n)$, mais $\frac{n^2}{2} \neq \omega (n^2)$. La relation$f(n) = \omega (g(n))$ implique que la limite suivante existe

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

C'est, f(n) devient arbitrairement grand par rapport à g(n) comme n s'approche de l'infini.

Exemple

Considérons la même fonction, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

Considérant $g(n) = n^2$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

D'où la complexité de f(n) peut être représenté comme $o(g(n))$, c'est à dire $\omega (n^2)$.

Analyse Apriori et Apostiari

L'analyse Apriori signifie que l'analyse est effectuée avant de l'exécuter sur un système spécifique. Cette analyse est une étape où une fonction est définie à l'aide d'un modèle théorique. Par conséquent, nous déterminons la complexité temporelle et spatiale d'un algorithme en regardant simplement l'algorithme plutôt que de l'exécuter sur un système particulier avec une mémoire, un processeur et un compilateur différents.

L'analyse Apostiari d'un algorithme signifie que nous effectuons l'analyse d'un algorithme uniquement après son exécution sur un système. Cela dépend directement du système et des changements d'un système à l'autre.

Dans une industrie, nous ne pouvons pas effectuer d'analyse Apostiari car le logiciel est généralement conçu pour un utilisateur anonyme, qui l'exécute sur un système différent de ceux présents dans l'industrie.

Dans Apriori, c'est la raison pour laquelle nous utilisons des notations asymptotiques pour déterminer la complexité du temps et de l'espace à mesure qu'elles changent d'un ordinateur à l'autre; cependant, asymptotiquement, ils sont identiques.

Dans ce chapitre, nous discuterons de la complexité des problèmes de calcul par rapport à la quantité d'espace requise par un algorithme.

La complexité spatiale partage de nombreuses caractéristiques de la complexité temporelle et sert de moyen supplémentaire de classer les problèmes en fonction de leurs difficultés de calcul.

Qu'est-ce que la complexité spatiale?

La complexité de l'espace est une fonction décrivant la quantité de mémoire (espace) qu'un algorithme prend en termes de quantité d'entrée à l'algorithme.

On parle souvent de extra memorynécessaire, sans compter la mémoire nécessaire pour stocker l'entrée elle-même. Encore une fois, nous utilisons des unités naturelles (mais de longueur fixe) pour mesurer cela.

Nous pouvons utiliser des octets, mais il est plus facile d'utiliser, par exemple, le nombre d'entiers utilisés, le nombre de structures de taille fixe, etc.

En fin de compte, la fonction que nous proposons sera indépendante du nombre réel d'octets nécessaires pour représenter l'unité.

La complexité de l'espace est parfois ignorée parce que l'espace utilisé est minimal et / ou évident, mais parfois cela devient un problème aussi important que la complexité du temps

Définition

Laisser M être un déterministe Turing machine (TM)qui s'arrête sur toutes les entrées. La complexité spatiale deM est la fonction $f \colon N \rightarrow N$, où f(n) est le nombre maximum de cellules de bande et M scanne toute entrée de longueur M. Si la complexité spatiale deM est f(n), on peut dire ça M court dans l'espace f(n).

Nous estimons la complexité spatiale de la machine de Turing en utilisant la notation asymptotique.

Laisser $f \colon N \rightarrow R^+$être une fonction. Les classes de complexité spatiale peuvent être définies comme suit -

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE est la classe des langages décidables dans l'espace polynomial sur une machine de Turing déterministe.

En d'autres termes, PSPACE = U_k SPACE (n^k)

Théorème de Savitch

L'un des premiers théorèmes liés à la complexité spatiale est le théorème de Savitch. Selon ce théorème, une machine déterministe peut simuler des machines non déterministes en utilisant une petite quantité d'espace.

Pour la complexité temporelle, une telle simulation semble exiger une augmentation exponentielle du temps. Pour la complexité spatiale, ce théorème montre que toute machine de Turing non déterministe qui utilisef(n) l'espace peut être converti en une TM déterministe qui utilise f²(n) espace.

Par conséquent, le théorème de Savitch déclare que, pour toute fonction, $f \colon N \rightarrow R^+$, où $f(n) \geqslant n$

NSPACE(f(n)) ⊆ SPACE(f(n))

Relation entre les classes de complexité

Le diagramme suivant illustre la relation entre les différentes classes de complexité.

Jusqu'à présent, nous n'avons pas discuté des classes P et NP dans ce tutoriel. Ceux-ci seront discutés plus tard.

De nombreux algorithmes sont de nature récursive pour résoudre un problème donné traitant de manière récursive des sous-problèmes.

Dans divide and conquer approach, un problème est divisé en problèmes plus petits, puis les problèmes plus petits sont résolus indépendamment, et enfin les solutions des problèmes plus petits sont combinées en une solution pour le problème plus grand.

En règle générale, les algorithmes de division et de conquête comportent trois parties -

• Divide the problem en un certain nombre de sous-problèmes qui sont des instances plus petites du même problème.

• Conquer the sub-problemsen les résolvant récursivement. S'ils sont suffisamment petits, résolvez les sous-problèmes en tant que cas de base.

• Combine the solutions aux sous-problèmes dans la solution du problème d'origine.

Avantages et inconvénients de l'approche Divide and Conquer

L'approche Divide and Conquer prend en charge le parallélisme car les sous-problèmes sont indépendants. Par conséquent, un algorithme, qui est conçu en utilisant cette technique, peut fonctionner sur le système multiprocesseur ou dans différentes machines simultanément.

Dans cette approche, la plupart des algorithmes sont conçus en utilisant la récursivité, la gestion de la mémoire est donc très élevée. Pour les fonctions récursives, la pile est utilisée, où l'état de la fonction doit être stocké.

Application de l'approche Divide and Conquer

Voici quelques problèmes, qui sont résolus en utilisant l'approche de division pour conquérir.

• Trouver le maximum et le minimum d'une séquence de nombres
• Multiplication matricielle de Strassen
• Tri par fusion
• Recherche binaire

Considérons un problème simple qui peut être résolu par une technique de division et de conquête.

Énoncé du problème

Le problème Max-Min dans l'analyse d'algorithme est de trouver la valeur maximale et minimale dans un tableau.

Solution

Pour trouver les nombres maximum et minimum dans un tableau donné numbers[] de taille n, l'algorithme suivant peut être utilisé. Nous représentons d'abord lenaive method et ensuite nous présenterons divide and conquer approach.

Méthode naïve

La méthode naïve est une méthode de base pour résoudre n'importe quel problème. Dans cette méthode, le nombre maximum et minimum peut être trouvé séparément. Pour trouver les nombres maximum et minimum, l'algorithme simple suivant peut être utilisé.

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

Une analyse

Le nombre de comparaison en méthode Naive est 2n - 2.

Le nombre de comparaisons peut être réduit en utilisant l'approche de division et de conquête. Voici la technique.

Approche Diviser pour Vaincre

Dans cette approche, le réseau est divisé en deux moitiés. Ensuite, en utilisant une approche récursive, les nombres maximum et minimum dans chaque moitié sont trouvés. Plus tard, retournez le maximum de deux maxima de chaque moitié et le minimum de deux minima de chaque moitié.

Dans ce problème donné, le nombre d'éléments dans un tableau est $y - x + 1$, où y est supérieur ou égal à x.

$\mathbf{\mathit{Max - Min(x, y)}}$ renverra les valeurs maximale et minimale d'un tableau $\mathbf{\mathit{numbers[x...y]}}$.

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

Une analyse

Laisser T(n) être le nombre de comparaisons effectuées par $\mathbf{\mathit{Max - Min(x, y)}}$, où le nombre d'éléments $n = y - x + 1$.

Si T(n) représente les nombres, alors la relation de récurrence peut être représentée par

$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}$$

Supposons que n est sous la forme de puissance de 2. Par conséquent,n = 2^k où k est la hauteur de l'arbre de récursivité.

Alors,

$$T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ..... = \frac{3n}{2} - 2$$

Par rapport à la méthode Naïve, dans l'approche diviser pour conquérir, le nombre de comparaisons est moindre. Cependant, en utilisant la notation asymptotique, les deux approches sont représentées parO(n).

Dans ce chapitre, nous aborderons le tri par fusion et analyserons sa complexité.

Énoncé du problème

Le problème du tri d'une liste de nombres se prête immédiatement à une stratégie de division pour conquérir: diviser la liste en deux moitiés, trier récursivement chaque moitié, puis fusionner les deux sous-listes triées.

Solution

Dans cet algorithme, les nombres sont stockés dans un tableau numbers[]. Ici,p et q représente l'index de début et de fin d'un sous-tableau.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n1 = q – p + 1 
n2 = r – q 
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
for i = 1 to n1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n2 
   rightnums[j] = numbers[q+ j] 
leftnums[n1 + 1] = ∞ 
rightnums[n2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

Une analyse

Considérons le temps d'exécution de Merge-Sort comme T(n). Par conséquent,

$T(n)=\begin{cases}c & if\:n\leqslant 1\\2\:x\:T(\frac{n}{2})+d\:x\:n & otherwise\end{cases}$où c et d sont des constantes

Par conséquent, en utilisant cette relation de récurrence,

$$T(n) = 2^i T(\frac{n}{2^i}) + i.d.n$$

Comme, $i = log\:n,\: T(n) = 2^{log\:n} T(\frac{n}{2^{log\:n}}) + log\:n.d.n$

$=\:c.n + d.n.log\:n$

Par conséquent, $T(n) = O(n\:log\:n)$

Exemple

Dans l'exemple suivant, nous avons montré pas à pas l'algorithme Merge-Sort. Tout d'abord, chaque tableau d'itération est divisé en deux sous-tableaux, jusqu'à ce que le sous-tableau ne contienne qu'un seul élément. Lorsque ces sous-tableaux ne peuvent plus être divisés, des opérations de fusion sont effectuées.

Dans ce chapitre, nous discuterons d'un autre algorithme basé sur la méthode de division et de conquête.

Énoncé du problème

La recherche binaire peut être effectuée sur un tableau trié. Dans cette approche, l'index d'un élémentxest déterminé si l'élément appartient à la liste des éléments. Si le tableau n'est pas trié, une recherche linéaire est utilisée pour déterminer la position.

Solution

Dans cet algorithme, nous voulons savoir si l'élément x appartient à un ensemble de nombres stockés dans un tableau numbers[]. Oùl et r représentent les index gauche et droit d'un sous-tableau dans lequel l'opération de recherche doit être effectuée.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Une analyse

La recherche linéaire s'exécute dans O(n)temps. Alors que la recherche binaire produit le résultat dansO(log n) temps

Laisser T(n) être le nombre de comparaisons dans le pire des cas dans un tableau de n éléments.

Par conséquent,

$$T(n)=\begin{cases}0 & if\:n= 1\\T(\frac{n}{2})+1 & otherwise\end{cases}$$

Utiliser cette relation de récurrence $T(n) = log\:n$.

Par conséquent, la recherche binaire utilise $O(log\:n)$ temps.

Exemple

Dans cet exemple, nous allons rechercher l'élément 63.

Dans ce chapitre, nous discuterons d'abord de la méthode générale de multiplication matricielle et plus tard, nous discuterons de l'algorithme de multiplication matricielle de Strassen.

Énoncé du problème

Considérons deux matrices X et Y. Nous voulons calculer la matrice résultanteZ en multipliant X et Y.

Méthode naïve

Tout d'abord, nous discuterons de la méthode naïve et de sa complexité. Ici, nous calculonsZ = X × Y. En utilisant la méthode Naïve, deux matrices (X et Y) peut être multipliée si l'ordre de ces matrices est p × q et q × r. Voici l'algorithme.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

Complexité

Ici, nous supposons que les opérations entières prennent O(1)temps. Il ya troisforboucles dans cet algorithme et l'une est imbriquée dans l'autre. Par conséquent, l'algorithme prendO(n³) le temps de l'exécuter.

Algorithme de multiplication matricielle de Strassen

Dans ce contexte, en utilisant l'algorithme de multiplication Matrix de Strassen, la consommation de temps peut être un peu améliorée.

La multiplication de la matrice de Strassen ne peut être effectuée que sur square matrices où n est un power of 2. L'ordre des deux matrices estn × n.

Diviser X, Y et Z en quatre matrices (n / 2) × (n / 2) comme représenté ci-dessous -

$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ et $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$

En utilisant l'algorithme de Strassen, calculez ce qui suit -

$$M_{1} \: \colon= (A+C) \times (E+F)$$

$$M_{2} \: \colon= (B+D) \times (G+H)$$

$$M_{3} \: \colon= (A-D) \times (E+H)$$

$$M_{4} \: \colon= A \times (F-H)$$

$$M_{5} \: \colon= (C+D) \times (E)$$

$$M_{6} \: \colon= (A+B) \times (H)$$

$$M_{7} \: \colon= D \times (G-E)$$

Ensuite,

$$I \: \colon= M_{2} + M_{3} - M_{6} - M_{7}$$

$$J \: \colon= M_{4} + M_{6}$$

$$K \: \colon= M_{5} + M_{7}$$

$$L \: \colon= M_{1} - M_{3} - M_{4} - M_{5}$$

Une analyse

$T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases}$où c et d sont des constantes

En utilisant cette relation de récurrence, nous obtenons $T(n) = O(n^{log7})$

Par conséquent, la complexité de l'algorithme de multiplication matricielle de Strassen est $O(n^{log7})$.

Parmi toutes les approches algorithmiques, l'approche la plus simple et la plus directe est la méthode Greedy. Dans cette approche, la décision est prise sur la base des informations actuellement disponibles sans se soucier de l'effet de la décision actuelle à l'avenir.

Les algorithmes gourmands construisent une solution partie par partie, choisissant la partie suivante de telle manière qu'elle donne un avantage immédiat. Cette approche ne reconsidère jamais les choix faits précédemment. Cette approche est principalement utilisée pour résoudre des problèmes d'optimisation. La méthode gourmande est facile à mettre en œuvre et assez efficace dans la plupart des cas. Par conséquent, nous pouvons dire que l'algorithme Greedy est un paradigme algorithmique basé sur l'heuristique qui suit le choix optimal local à chaque étape dans l'espoir de trouver une solution optimale globale.

Dans de nombreux problèmes, il ne produit pas de solution optimale bien qu'il donne une solution approximative (presque optimale) dans un délai raisonnable.

Composants de l'algorithme gourmand

Les algorithmes gourmands ont les cinq composants suivants -

• A candidate set - Une solution est créée à partir de cet ensemble.

• A selection function - Permet de choisir le meilleur candidat à ajouter à la solution.

• A feasibility function - Utilisé pour déterminer si un candidat peut être utilisé pour contribuer à la solution.

• An objective function - Utilisé pour attribuer une valeur à une solution ou à une solution partielle.

• A solution function - Utilisé pour indiquer si une solution complète a été atteinte.

Zones d'application

L'approche gourmande est utilisée pour résoudre de nombreux problèmes, tels que

• Trouver le chemin le plus court entre deux sommets à l'aide de l'algorithme de Dijkstra.

• Trouver l'arbre couvrant minimal dans un graphique à l'aide de l'algorithme de Prim / Kruskal, etc.

Là où l'approche cupide échoue

Dans de nombreux problèmes, l'algorithme Greedy ne parvient pas à trouver une solution optimale, de plus il peut produire la pire solution. Des problèmes comme le vendeur itinérant et le sac à dos ne peuvent pas être résolus en utilisant cette approche.

L'algorithme Greedy pourrait être très bien compris avec un problème bien connu appelé problème Knapsack. Bien que le même problème puisse être résolu en utilisant d'autres approches algorithmiques, l'approche Greedy résout raisonnablement le problème du sac à dos fractionnaire dans un délai raisonnable. Laissez-nous discuter du problème de Knapsack en détail.

Problème de sac à dos

Étant donné un ensemble d'éléments, chacun avec un poids et une valeur, déterminez un sous-ensemble d'éléments à inclure dans une collection afin que le poids total soit inférieur ou égal à une limite donnée et que la valeur totale soit aussi grande que possible.

Le problème du sac à dos est un problème d'optimisation combinatoire. Il apparaît comme un sous-problème dans de nombreux modèles mathématiques plus complexes de problèmes du monde réel. Une approche générale des problèmes difficiles consiste à identifier la contrainte la plus restrictive, à ignorer les autres, à résoudre un problème de sac à dos et à ajuster d'une manière ou d'une autre la solution pour satisfaire les contraintes ignorées.

Applications

Dans de nombreux cas d'allocation de ressources avec certaines contraintes, le problème peut être dérivé de la même manière que le problème de Knapsack. Voici un ensemble d'exemples.

• Trouver le moyen le moins coûteux de réduire les matières premières
• optimisation du portefeuille
• Réduire les problèmes de stock

Scénario de problème

Un voleur vole un magasin et peut porter un poids maximal de Wdans son sac à dos. Il y a n articles disponibles dans le magasin et le poids dei^th l'élément est w_i et son profit est p_i. Quels objets le voleur doit-il emporter?

Dans ce contexte, les objets doivent être sélectionnés de manière à ce que le voleur porte les objets pour lesquels il réalisera un profit maximum. Par conséquent, l'objectif du voleur est de maximiser le profit.

En fonction de la nature des articles, les problèmes de sac à dos sont classés comme

• Sac à dos fractionnaire
• Knapsack

Sac à dos fractionnaire

Dans ce cas, les objets peuvent être divisés en morceaux plus petits, le voleur peut donc sélectionner des fractions d'objets.

Selon l'énoncé du problème,

• Il y a n articles dans le magasin

• Poids de i^th article $w_{i} > 0$

• Profiter pour i^th article $p_{i} > 0$ et

• La capacité du sac à dos est W

Dans cette version du problème Knapsack, les articles peuvent être divisés en morceaux plus petits. Donc, le voleur ne peut prendre qu'une fractionx_i de i^th article.

$$0 \leqslant x_{i} \leqslant 1$$

le i^th l'élément contribue au poids $x_{i}.w_{i}$ au poids total dans le sac à dos et au profit $x_{i}.p_{i}$ au profit total.

Par conséquent, l'objectif de cet algorithme est de

$$maximize\:\displaystyle\sum\limits_{n=1}^n (x_{i}.p_{}i)$$

soumis à contrainte,

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) \leqslant W$$

Il est clair qu'une solution optimale doit remplir exactement le sac à dos, sinon nous pourrions ajouter une fraction de l'un des articles restants et augmenter le profit global.

Ainsi, une solution optimale peut être obtenue en

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) = W$$

Dans ce contexte, nous devons d'abord trier ces éléments en fonction de la valeur de $\frac{p_{i}}{w_{i}}$, pour que $\frac{p_{i}+1}{w_{i}+1}$ ≤ $\frac{p_{i}}{w_{i}}$. Ici,x est un tableau pour stocker la fraction d'éléments.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Une analyse

Si les éléments fournis sont déjà triés dans un ordre décroissant de $\mathbf{\frac{p_{i}}{w_{i}}}$, puis le whileloop prend un certain temps O(n); Par conséquent, le temps total, y compris le tri, estO(n logn).

Exemple

Considérons que la capacité du sac à dos W = 60 et la liste des éléments fournis sont indiqués dans le tableau suivant -

Article	UNE	B	C	ré
Profit	280	100	120	120
Poids	40	dix	20	24
Rapport $(\frac{p_{i}}{w_{i}})$	sept	dix	6	5

Comme les éléments fournis ne sont pas triés en fonction de $\mathbf{\frac{p_{i}}{w_{i}}}$. Après le tri, les éléments sont comme indiqué dans le tableau suivant.

Article	B	UNE	C	ré
Profit	100	280	120	120
Poids	dix	40	20	24
Rapport $(\frac{p_{i}}{w_{i}})$	dix	sept	6	5

Solution

Après avoir trié tous les articles selon $\frac{p_{i}}{w_{i}}$. Tout d'abordB est choisi comme poids de Best inférieure à la capacité du sac à dos. Prochain pointA est choisi, car la capacité disponible du sac à dos est supérieure au poids du A. Maintenant,Cest choisi comme élément suivant. Cependant, l'article entier ne peut pas être choisi car la capacité restante du sac à dos est inférieure au poids deC.

Par conséquent, une fraction de C (c'est-à-dire (60 - 50) / 20) est choisi.

Désormais, la capacité du sac à dos est égale aux articles sélectionnés. Par conséquent, aucun autre élément ne peut être sélectionné.

Le poids total des articles sélectionnés est 10 + 40 + 20 * (10/20) = 60

Et le profit total est 100 + 280 + 120 * (10/20) = 380 + 60 = 440

C'est la solution optimale. Nous ne pouvons pas gagner plus de profit en sélectionnant une combinaison différente d'articles.

Énoncé du problème

Dans le problème de séquençage des travaux, l'objectif est de trouver une séquence de travaux, qui est achevée dans leurs délais et donne un profit maximal.

Solution

Considérons, un ensemble de ndes emplois donnés qui sont associés à des délais et des bénéfices sont gagnés, si un travail est terminé à sa date limite. Ces travaux doivent être ordonnés de manière à générer un profit maximum.

Il peut arriver que tous les travaux donnés ne soient pas terminés dans leurs délais.

Supposons, date limite de i^th emploi J_i est d_i et le profit tiré de ce travail est p_i. Par conséquent, la solution optimale de cet algorithme est une solution réalisable avec un profit maximal.

Donc, $D(i) > 0$ pour $1 \leqslant i \leqslant n$.

Au départ, ces travaux sont classés en fonction du profit, c'est-à-dire $p_{1} \geqslant p_{2} \geqslant p_{3} \geqslant \:... \: \geqslant p_{n}$.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Une analyse

Dans cet algorithme, nous utilisons deux boucles, l'une dans l'autre. Par conséquent, la complexité de cet algorithme est$O(n^2)$.

Exemple

Considérons un ensemble d'emplois donnés comme indiqué dans le tableau suivant. Nous devons trouver une séquence de travaux, qui seront achevés dans leurs délais et donneront un profit maximum. Chaque travail est associé à une échéance et à un profit.

Emploi	J1	J2	J3	J4	J5
Date limite	2	1	3	2	1
Profit	60	100	20	40	20

Solution

Pour résoudre ce problème, les emplois donnés sont triés en fonction de leur profit dans un ordre décroissant. Par conséquent, après le tri, les travaux sont classés comme indiqué dans le tableau suivant.

Emploi	J2	J1	J4	J3	J5
Date limite	1	2	2	3	1
Profit	100	60	40	20	20

From this set of jobs, first we select J₂, as it can be completed within its deadline and contributes maximum profit.

• Next, J₁ is selected as it gives more profit compared to J₄.

• In the next clock, J₄ cannot be selected as its deadline is over, hence J₃ is selected as it executes within its deadline.

• The job J₅ is discarded as it cannot be executed within its deadline.

Thus, the solution is the sequence of jobs (J₂, J₁, J₃), which are being executed within their deadline and gives maximum profit.

Total profit of this sequence is 100 + 60 + 20 = 180.

Merge a set of sorted files of different length into a single sorted file. We need to find an optimal solution, where the resultant file will be generated in minimum time.

If the number of sorted files are given, there are many ways to merge them into a single sorted file. This merge can be performed pair wise. Hence, this type of merging is called as 2-way merge patterns.

As, different pairings require different amounts of time, in this strategy we want to determine an optimal way of merging many files together. At each step, two shortest sequences are merged.

To merge a p-record file and a q-record file requires possibly p + q record moves, the obvious choice being, merge the two smallest files together at each step.

Two-way merge patterns can be represented by binary merge trees. Let us consider a set of n sorted files {f₁, f₂, f₃, …, f_n}. Initially, each element of this is considered as a single node binary tree. To find this optimal solution, the following algorithm is used.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

At the end of this algorithm, the weight of the root node represents the optimal cost.

Example

Let us consider the given files, f₁, f₂, f₃, f₄ and f₅ with 20, 30, 10, 5 and 30 number of elements respectively.

If merge operations are performed according to the provided sequence, then

M₁ = merge f₁ and f₂ => 20 + 30 = 50

M₂ = merge M₁ and f₃ => 50 + 10 = 60

M₃ = merge M₂ and f₄ => 60 + 5 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Hence, the total number of operations is

50 + 60 + 65 + 95 = 270

Now, the question arises is there any better solution?

En triant les nombres en fonction de leur taille dans un ordre croissant, nous obtenons la séquence suivante -

f₄, f₃, f₁, f₂, f₅

Par conséquent, les opérations de fusion peuvent être effectuées sur cette séquence

M₁ = merge f₄ and f₃ => 5 + 10 = 15

M₂ = merge M₁ and f₁ => 15 + 20 = 35

M₃ = merge M₂ and f₂ => 35 + 30 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Par conséquent, le nombre total d'opérations est

15 + 35 + 65 + 95 = 210

Évidemment, c'est mieux que le précédent.

Dans ce contexte, nous allons maintenant résoudre le problème en utilisant cet algorithme.

Ensemble initial

Étape 1

Étape 2

Étape 3

Étape 4

Par conséquent, la solution prend 15 + 35 + 60 + 95 = 205 nombre de comparaisons.

La programmation dynamique est également utilisée dans les problèmes d'optimisation. À l'instar de la méthode de division et de conquête, la programmation dynamique résout les problèmes en combinant les solutions de sous-problèmes. De plus, l'algorithme de programmation dynamique résout chaque sous-problème une seule fois, puis enregistre sa réponse dans un tableau, évitant ainsi le travail de recalculer la réponse à chaque fois.

Deux propriétés principales d'un problème suggèrent que le problème donné peut être résolu à l'aide de la programmation dynamique. Ces propriétés sontoverlapping sub-problems and optimal substructure.

Sous-problèmes qui se chevauchent

Semblable à l'approche Divide-and-Conquer, la programmation dynamique combine également des solutions à des sous-problèmes. Il est principalement utilisé lorsque la solution d'un sous-problème est nécessaire à plusieurs reprises. Les solutions calculées sont stockées dans une table, de sorte qu'elles ne doivent pas être recalculées. Par conséquent, cette technique est nécessaire lorsque des sous-problèmes se chevauchent.

Par exemple, la recherche binaire n'a pas de sous-problème de chevauchement. Alors que le programme récursif des nombres de Fibonacci a de nombreux sous-problèmes qui se chevauchent.

Sous-structure optimale

Un problème donné a une propriété de sous-structure optimale, si la solution optimale du problème donné peut être obtenue en utilisant des solutions optimales de ses sous-problèmes.

Par exemple, le problème du chemin le plus court a la propriété de sous-structure optimale suivante -

Si un nœud x se trouve dans le chemin le plus court depuis un nœud source u au nœud de destination v, puis le chemin le plus court depuis u à v est la combinaison du chemin le plus court depuis u à x, et le chemin le plus court depuis x à v.

Les algorithmes standard All Pair Shortest Path comme Floyd-Warshall et Bellman-Ford sont des exemples typiques de programmation dynamique.

Étapes de l'approche de programmation dynamique

L'algorithme de programmation dynamique est conçu en utilisant les quatre étapes suivantes -

• Caractériser la structure d'une solution optimale.
• Définissez récursivement la valeur d'une solution optimale.
• Calculez la valeur d'une solution optimale, généralement de manière ascendante.
• Construisez une solution optimale à partir des informations calculées.

Applications de l'approche de programmation dynamique

• Multiplication de la chaîne matricielle
• Sous-séquence commune la plus longue
• Problème de vendeur itinérant

Dans ce didacticiel, nous avons précédemment abordé le problème du sac à dos fractionnaire en utilisant l'approche Greedy. Nous avons montré que l'approche Greedy donne une solution optimale pour Fractional Knapsack. Cependant, ce chapitre couvrira le problème 0-1 Knapsack et son analyse.

Dans 0-1 Knapsack, les articles ne peuvent pas être cassés, ce qui signifie que le voleur doit prendre l'article dans son ensemble ou le laisser. C'est la raison pour laquelle il s'appelle 0-1 Knapsack.

Par conséquent, dans le cas de 0-1 Knapsack, la valeur de x_i peut être soit 0 ou 1, où les autres contraintes restent les mêmes.

0-1 Knapsack ne peut pas être résolu par une approche cupide. Une approche gourmande ne garantit pas une solution optimale. Dans de nombreux cas, l'approche Greedy peut donner une solution optimale.

Les exemples suivants établiront notre déclaration.

Exemple 1

Considérons que la capacité du sac à dos est W = 25 et les articles sont comme indiqué dans le tableau suivant.

Article	UNE	B	C	ré
Profit	24	18	18	dix
Poids	24	dix	dix	sept

Sans considérer le profit par unité de poids (p_i/w_i), si nous appliquons l'approche Greedy pour résoudre ce problème, premier élément Asera sélectionnée car elle contribuera max _i profit mum entre tous les éléments.

Après avoir sélectionné l'élément A, aucun autre élément ne sera sélectionné. Par conséquent, pour cet ensemble donné d'éléments, le profit total est24. Alors que la solution optimale peut être obtenue en sélectionnant des éléments,B et C, où le profit total est 18 + 18 = 36.

Exemple-2

Au lieu de sélectionner les éléments en fonction de l'avantage global, dans cet exemple, les éléments sont sélectionnés sur la base du rapport p _i / w _i . Considérons que la capacité du sac à dos est W = 60 et les articles sont comme indiqué dans le tableau suivant.

Article	UNE	B	C
Prix	100	280	120
Poids	dix	40	20
Rapport	dix	sept	6

Utilisation de l'approche gourmande, premier élément Aest sélectionné. Ensuite, l'élément suivantBest choisi. Par conséquent, le profit total est100 + 280 = 380. Cependant, la solution optimale de cette instance peut être obtenue en sélectionnant des éléments,B et C, où le profit total est 280 + 120 = 400.

Par conséquent, on peut conclure que l'approche cupide peut ne pas donner une solution optimale.

Pour résoudre 0-1 Knapsack, une approche de programmation dynamique est nécessaire.

Énoncé du problème

Un voleur vole un magasin et peut porter un max _i poids de malWdans son sac à dos. Il y an articles et poids de i^th l'élément est w_i et le bénéfice de la sélection de cet article est p_i. Quels objets le voleur doit-il emporter?

Approche de programmation dynamique

Laisser i être l'élément le plus numéroté dans une solution optimale S pour Wdollars. ensuiteS^' = S - {i} est une solution optimale pour W - w_i dollars et la valeur de la solution S est V_i plus la valeur du sous-problème.

Nous pouvons exprimer ce fait dans la formule suivante: définir c[i, w] être la solution pour les objets 1,2, … , iet le poids max _i mumw.

L'algorithme prend les entrées suivantes

• Le poids max _i mumW

• Le nombre d'articles n

• Les deux séquences v = <v₁, v₂, …, v_n> et w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

L'ensemble des éléments à prendre peut être déduit du tableau, à partir de c[n, w] et remonter la provenance des valeurs optimales.

Si c [i, w] = c [i-1, w] , alors itemi ne fait pas partie de la solution, et nous continuons à tracer avec c[i-1, w]. Sinon, itemi fait partie de la solution, et nous continuons à tracer avec c[i-1, w-W].

Une analyse

Cet algorithme prend θ ( n , w ) fois car la table c a ( n + 1). ( W + 1) entrées, où chaque entrée nécessite θ (1) temps pour calculer.

Le problème de sous-séquence le plus long est de trouver la séquence la plus longue qui existe dans les deux chaînes données.

Sous-séquence

Considérons une suite S = <s ₁ , s ₂ , s ₃ , s ₄ ,…, s _n >.

Une suite Z = <z ₁ , z ₂ , z ₃ , z ₄ ,…, z _m > sur S est appelée une sous-séquence de S, si et seulement si elle peut être dérivée de la suppression S de certains éléments.

Sous-séquence commune

Supposer, X et Ysont deux séquences sur un ensemble fini d'éléments. On peut dire çaZ est une sous-séquence commune de X et Y, si Z est une sous-séquence des deux X et Y.

Sous-séquence commune la plus longue

Si un ensemble de séquences est donné, le problème de sous-séquence le plus long est de trouver une sous-séquence commune de toutes les séquences qui est de longueur maximale.

Le problème de sous-séquence le plus long est un problème informatique classique, à la base de programmes de comparaison de données tels que l'utilitaire de diff, et a des applications en bioinformatique. Il est également largement utilisé par les systèmes de contrôle de révision, tels que SVN et Git, pour réconcilier plusieurs modifications apportées à une collection de fichiers contrôlée par révision.

Méthode naïve

Laisser X être une séquence de longueur m et Y une séquence de longueur n. Vérifiez chaque sous-séquence deX s'il s'agit d'une sous-séquence de Yet renvoie la plus longue sous-séquence commune trouvée.

Il y a 2^m sous-séquences de X. Tester les séquences, qu'il s'agisse ou non d'une sous-séquence deY prend O(n)temps. Ainsi, l'algorithme naïf prendraitO(n2^m) temps.

Programmation dynamique

Soit X = <x ₁ , x ₂ , x ₃ ,…, x _m > et Y = <y ₁ , y ₂ , y ₃ ,…, y _n > les suites. Pour calculer la longueur d'un élément, l'algorithme suivant est utilisé.

Dans cette procédure, table C[m, n] est calculé dans l'ordre principal de la ligne et dans une autre table B[m,n] est calculé pour construire une solution optimale.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Cet algorithme imprimera la plus longue sous-séquence commune de X et Y.

Une analyse

Pour peupler la table, le for boucle itère m les temps et l'intérieur for boucle itère nfois. Par conséquent, la complexité de l'algorithme est O (m, n) , oùm et n sont la longueur de deux chaînes.

Exemple

Dans cet exemple, nous avons deux chaînes X = BACDB et Y = BDCB pour trouver la sous-séquence commune la plus longue.

En suivant l'algorithme LCS-Length-Table-Formulation (comme indiqué ci-dessus), nous avons calculé le tableau C (montré sur le côté gauche) et le tableau B (montré sur le côté droit).

Dans le tableau B, au lieu de «D», «L» et «U», nous utilisons respectivement la flèche diagonale, la flèche gauche et la flèche haut. Après avoir généré la table B, le LCS est déterminé par la fonction LCS-Print. Le résultat est BCB.

UNE spanning tree est un sous-ensemble d'un graphe non orienté dont tous les sommets sont reliés par un nombre minimum d'arêtes.

Si tous les sommets sont connectés dans un graphe, alors il existe au moins un arbre couvrant. Dans un graphique, il peut exister plus d'un arbre couvrant.

Propriétés

• Un Spanning Tree n'a pas de cycle.
• N'importe quel sommet peut être atteint depuis n'importe quel autre sommet.

Exemple

Dans le graphique suivant, les arêtes en surbrillance forment un arbre couvrant.

Arbre couvrant minimum

UNE Minimum Spanning Tree (MST)est un sous-ensemble d'arêtes d'un graphe non orienté pondéré connecté qui relie tous les sommets avec le poids d'arête total minimum possible. Pour dériver un MST, l'algorithme de Prim ou l'algorithme de Kruskal peut être utilisé. Par conséquent, nous discuterons de l'algorithme de Prim dans ce chapitre.

Comme nous l'avons vu, un graphe peut avoir plus d'un arbre couvrant. S'il y an nombre de sommets, l'arbre couvrant doit avoir n - 1nombre d'arêtes. Dans ce contexte, si chaque arête du graphe est associée à un poids et qu'il existe plusieurs spanning tree, nous devons trouver l'arborescence minimale du graphe.

De plus, s'il existe des arêtes pondérées en double, le graphe peut avoir plusieurs arbres couvrant minimum.

Dans le graphique ci-dessus, nous avons montré un arbre couvrant bien qu'il ne s'agisse pas de l'arbre couvrant minimum. Le coût de cet arbre couvrant est (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Nous utiliserons l'algorithme de Prim pour trouver l'arbre couvrant minimum.

Algorithme de Prim

L'algorithme de Prim est une approche gourmande pour trouver l'arbre couvrant minimum. Dans cet algorithme, pour former un MST, nous pouvons partir d'un sommet arbitraire.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

La fonction Extract-Min renvoie le sommet avec un coût d'arête minimum. Cette fonction fonctionne sur min-heap.

Exemple

En utilisant l'algorithme de Prim, nous pouvons partir de n'importe quel sommet, commençons par un sommet 1.

Sommet 3 est connecté au sommet 1 avec un coût de bord minimal, donc un bord (1, 2) est ajouté à l'arbre couvrant.

Ensuite, bord (2, 3) est considéré car c'est le minimum parmi les arêtes {(1, 2), (2, 3), (3, 4), (3, 7)}.

Dans la prochaine étape, nous avons l'avantage (3, 4) et (2, 4)avec un coût minimum. Bord(3, 4) est sélectionné au hasard.

De la même manière, les bords (4, 5), (5, 7), (7, 8), (6, 8) et (6, 9)sont sélectionnés. Comme tous les sommets sont visités, l'algorithme s'arrête maintenant.

Le coût de l'arbre couvrant est (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. Il n'y a plus d'arbre couvrant dans ce graphique avec un coût inférieur à 23.

Algorithme de Dijkstra

L'algorithme de Dijkstra résout le problème des chemins les plus courts à source unique sur un graphe pondéré dirigé G = (V, E) , où toutes les arêtes sont non négatives (c'est-à-dire w (u, v) ≥ 0 pour chaque arête (u, v ) Є E ).

Dans l'algorithme suivant, nous utiliserons une fonction Extract-Min(), qui extrait le nœud avec la plus petite clé.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Une analyse

La complexité de cet algorithme dépend entièrement de l'implémentation de la fonction Extract-Min. Si la fonction d'extraction min est implémentée en utilisant la recherche linéaire, la complexité de cet algorithme estO(V² + E).

Dans cet algorithme, si nous utilisons min-heap sur lequel Extract-Min() fonctionne pour renvoyer le nœud de Q avec la plus petite clé, la complexité de cet algorithme peut être réduite davantage.

Exemple

Considérons le sommet 1 et 9comme sommet de départ et de destination respectivement. Initialement, tous les sommets sauf le sommet de départ sont marqués par ∞ et le sommet de départ est marqué par0.

Sommet	Initiale	Étape 1 V 1	Étape 2 V 3	Étape 3 V 2	Étape 4 V 4	Étape 5 V 5	Étape 6 V 7	Étape 7 V 8	Étape 8 V 6
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	sept	sept	sept	sept	sept	sept
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
sept	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

Par conséquent, la distance minimale du sommet 9 du sommet 1 est 20. Et le chemin est

1 → 3 → 7 → 8 → 6 → 9

Ce chemin est déterminé en fonction des informations du prédécesseur.

Algorithme Bellman Ford

Cet algorithme résout le problème de chemin le plus court source unique d'un graphe orienté G = (V, E)dans lequel les poids des bords peuvent être négatifs. De plus, cet algorithme peut être appliqué pour trouver le chemin le plus court, s'il n'existe pas de cycle pondéré négatif.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Une analyse

La première for boucle est utilisée pour l'initialisation, qui s'exécute dans O(V)fois. Le suivantfor boucle s'exécute |V - 1| passe sur les bords, ce qui prendO(E) fois.

Par conséquent, l'algorithme de Bellman-Ford s'exécute dans O(V, E) temps.

Exemple

L'exemple suivant montre comment l'algorithme Bellman-Ford fonctionne étape par étape. Ce graphe a un bord négatif mais n'a pas de cycle négatif, le problème peut donc être résolu en utilisant cette technique.

Au moment de l'initialisation, tous les sommets sauf la source sont marqués par ∞ et la source est marquée par 0.

Dans un premier temps, tous les sommets accessibles depuis la source sont mis à jour au coût minimum. Par conséquent, les sommetsa et h sont mis à jour.

Dans l'étape suivante, les sommets a, b, f et e sont mis à jour.

Suivant la même logique, dans cette étape les sommets b, f, c et g sont mis à jour.

Ici, les sommets c et d sont mis à jour.

Par conséquent, la distance minimale entre les sommets s et sommet d est 20.

Sur la base des informations du prédécesseur, le chemin est s → h → e → g → c → d

Un graphique à plusieurs niveaux G = (V, E) est un graphe orienté où les sommets sont partitionnés en k (où k > 1) nombre de sous-ensembles disjoints S = {s₁,s₂,…,s_k}tel que l'arête (u, v) est dans E, alors u Є s _i et v Є s _{1 + 1} pour certains sous-ensembles de la partition et |s₁| = |s_k| = 1.

Le sommet s Є s₁ s'appelle le source et le sommet t Є s_k est appelé sink.

Gest généralement supposé être un graphique pondéré. Dans ce graphique, le coût d'une arête (i, j) est représenté par c (i, j) . Par conséquent, le coût du chemin depuis la sources couler t est la somme des coûts de chaque arête de ce chemin.

Le problème du graphe en plusieurs étapes consiste à trouver le chemin avec un coût minimum à partir de la source s couler t.

Exemple

Prenons l'exemple suivant pour comprendre le concept de graphe à plusieurs étages.

Selon la formule, nous devons calculer le coût (i, j) en suivant les étapes suivantes

Étape 1: Coût (K-2, j)

Dans cette étape, trois nœuds (nœuds 4, 5. 6) sont sélectionnés comme j. Par conséquent, nous avons trois options pour choisir le coût minimum à cette étape.

Coût (3, 4) = min {c (4, 7) + Coût (7, 9), c (4, 8) + Coût (8, 9)} = 7

Coût (3, 5) = min {c (5, 7) + Coût (7, 9), c (5, 8) + Coût (8, 9)} = 5

Coût (3, 6) = min {c (6, 7) + Coût (7, 9), c (6, 8) + Coût (8, 9)} = 5

Étape 2: Coût (K-3, j)

Deux nœuds sont sélectionnés comme j car à l'étape k - 3 = 2, il y a deux nœuds, 2 et 3. Ainsi, la valeur i = 2 et j = 2 et 3.

Coût (2, 2) = min {c (2, 4) + Coût (4, 8) + Coût (8, 9), c (2, 6) +

Coût (6, 8) + Coût (8, 9)} = 8

Coût (2, 3) = {c (3, 4) + Coût (4, 8) + Coût (8, 9), c (3, 5) + Coût (5, 8) + Coût (8, 9), c (3, 6) + Coût (6, 8) + Coût (8, 9)} = 10

Étape 3: Coût (K-4, j)

Coût (1, 1) = {c (1, 2) + Coût (2, 6) + Coût (6, 8) + Coût (8, 9), c (1, 3) + Coût (3, 5) + Coût (5, 8) + Coût (8, 9))} = 12

c (1, 3) + Coût (3, 6) + Coût (6, 8 + Coût (8, 9))} = 13

Par conséquent, le chemin ayant le coût minimum est 1→ 3→ 5→ 8→ 9.

Énoncé du problème

Un voyageur doit visiter toutes les villes à partir d'une liste, où les distances entre toutes les villes sont connues et chaque ville ne doit être visitée qu'une seule fois. Quel est l'itinéraire le plus court possible pour qu'il visite chaque ville une seule fois et retourne à la ville d'origine?

Solution

Le problème des vendeurs itinérants est le problème de calcul le plus notoire. Nous pouvons utiliser l'approche de la force brute pour évaluer chaque tour possible et sélectionner le meilleur. Pourn nombre de sommets dans un graphe, il y a (n - 1)! nombre de possibilités.

Au lieu de la force brute utilisant une approche de programmation dynamique, la solution peut être obtenue en moins de temps, bien qu'il n'y ait pas d'algorithme de temps polynomial.

Considérons un graphe G = (V, E), où V est un ensemble de villes et Eest un ensemble d'arêtes pondérées. Un borde(u, v) représente que les sommets u et vest connecté. Distance entre les sommetsu et v est d(u, v), qui doit être non négatif.

Supposons que nous ayons commencé à la ville 1 et après avoir visité quelques villes maintenant nous sommes en ville j. Par conséquent, il s'agit d'une visite partielle. Nous avons certainement besoin de savoirj, car cela déterminera les villes les plus pratiques à visiter ensuite. Nous devons également connaître toutes les villes visitées jusqu'à présent, afin de ne répéter aucune d'entre elles. C'est donc un sous-problème approprié.

Pour un sous-ensemble de villes S Є {1, 2, 3, ... , n} qui comprend 1, et j Є S, laisser C(S, j) être la longueur du chemin le plus court visitant chaque nœud de S exactement une fois, à partir de 1 et se terminant à j.

Quand |S| > 1, on définitC(S, 1) = ∝ puisque le chemin ne peut pas commencer et se terminer à 1.

Maintenant, laisse exprimer C(S, j)en termes de sous-problèmes plus petits. Nous devons commencer à1 et se terminer à j. Nous devons sélectionner la prochaine ville de telle manière que

$$C(S, j) = min \:C(S - \lbrace j \rbrace, i) + d(i, j)\:where\: i\in S \: and\: i \neq jc(S, j) = minC(s- \lbrace j \rbrace, i)+ d(i,j) \:where\: i\in S \: and\: i \neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Une analyse

Il y a au plus $2^n.n$sous-problèmes et chacun prend un temps linéaire à résoudre. Par conséquent, la durée totale de fonctionnement est$O(2^n.n^2)$.

Exemple

Dans l'exemple suivant, nous illustrerons les étapes pour résoudre le problème du voyageur de commerce.

À partir du graphique ci-dessus, le tableau suivant est préparé.

	1	2	3	4
1	0	dix	15	20
2	5	0	9	dix
3	6	13	0	12
4	8	8	9	0

S = Φ

$$\small Cost (2,\Phi,1) = d (2,1) = 5\small Cost(2,\Phi,1)=d(2,1)=5$$

$$\small Cost (3,\Phi,1) = d (3,1) = 6\small Cost(3,\Phi,1)=d(3,1)=6$$

$$\small Cost (4,\Phi,1) = d (4,1) = 8\small Cost(4,\Phi,1)=d(4,1)=8$$

S = 1

$$\small Cost (i,s) = min \lbrace Cost (j,s – (j)) + d [i,j]\rbrace\small Cost (i,s)=min \lbrace Cost (j,s)-(j))+ d [i,j]\rbrace$$

$$\small Cost (2,\lbrace 3 \rbrace,1) = d [2,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(2,\lbrace3 \rbrace,1)=d[2,3]+cost(3,\Phi ,1)=9+6=15$$

$$\small Cost (2,\lbrace 4 \rbrace,1) = d [2,4] + Cost (4,\Phi,1) = 10 + 8 = 18cost(2,\lbrace4 \rbrace,1)=d[2,4]+cost(4,\Phi,1)=10+8=18$$

$$\small Cost (3,\lbrace 2 \rbrace,1) = d [3,2] + Cost (2,\Phi,1) = 13 + 5 = 18cost(3,\lbrace2 \rbrace,1)=d[3,2]+cost(2,\Phi,1)=13+5=18$$

$$\small Cost (3,\lbrace 4 \rbrace,1) = d [3,4] + Cost (4,\Phi,1) = 12 + 8 = 20cost(3,\lbrace4 \rbrace,1)=d[3,4]+cost(4,\Phi,1)=12+8=20$$

$$\small Cost (4,\lbrace 3 \rbrace,1) = d [4,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(4,\lbrace3 \rbrace,1)=d[4,3]+cost(3,\Phi,1)=9+6=15$$

$$\small Cost (4,\lbrace 2 \rbrace,1) = d [4,2] + Cost (2,\Phi,1) = 8 + 5 = 13cost(4,\lbrace2 \rbrace,1)=d[4,2]+cost(2,\Phi,1)=8+5=13$$

S = 2

$$\small Cost(2, \lbrace 3, 4 \rbrace, 1)=\begin{cases}d[2, 3] + Cost(3, \lbrace 4 \rbrace, 1) = 9 + 20 = 29\\d[2, 4] + Cost(4, \lbrace 3 \rbrace, 1) = 10 + 15 = 25=25\small Cost (2,\lbrace 3,4 \rbrace,1)\\\lbrace d[2,3]+ \small cost(3,\lbrace4\rbrace,1)=9+20=29d[2,4]+ \small Cost (4,\lbrace 3 \rbrace ,1)=10+15=25\end{cases}= 25$$

$$\small Cost(3, \lbrace 2, 4 \rbrace, 1)=\begin{cases}d[3, 2] + Cost(2, \lbrace 4 \rbrace, 1) = 13 + 18 = 31\\d[3, 4] + Cost(4, \lbrace 2 \rbrace, 1) = 12 + 13 = 25=25\small Cost (3,\lbrace 2,4 \rbrace,1)\\\lbrace d[3,2]+ \small cost(2,\lbrace4\rbrace,1)=13+18=31d[3,4]+ \small Cost (4,\lbrace 2 \rbrace ,1)=12+13=25\end{cases}= 25$$

$$\small Cost(4, \lbrace 2, 3 \rbrace, 1)=\begin{cases}d[4, 2] + Cost(2, \lbrace 3 \rbrace, 1) = 8 + 15 = 23\\d[4, 3] + Cost(3, \lbrace 2 \rbrace, 1) = 9 + 18 = 27=23\small Cost (4,\lbrace 2,3 \rbrace,1)\\\lbrace d[4,2]+ \small cost(2,\lbrace3\rbrace,1)=8+15=23d[4,3]+ \small Cost (3,\lbrace 2 \rbrace ,1)=9+18=27\end{cases}= 23$$

S = 3

$$\small Cost(1, \lbrace 2, 3, 4 \rbrace, 1)=\begin{cases}d[1, 2] + Cost(2, \lbrace 3, 4 \rbrace, 1) = 10 + 25 = 35\\d[1, 3] + Cost(3, \lbrace 2, 4 \rbrace, 1) = 15 + 25 = 40\\d[1, 4] + Cost(4, \lbrace 2, 3 \rbrace, 1) = 20 + 23 = 43=35 cost(1,\lbrace 2,3,4 \rbrace),1)\\d[1,2]+cost(2,\lbrace 3,4 \rbrace,1)=10+25=35\\d[1,3]+cost(3,\lbrace 2,4 \rbrace,1)=15+25=40\\d[1,4]+cost(4,\lbrace 2,3 \rbrace ,1)=20+23=43=35\end{cases}$$

Le chemin de coût minimum est de 35.

Partir du coût {1, {2, 3, 4}, 1}, nous obtenons la valeur minimale pour d [1, 2]. Quands = 3, sélectionnez le chemin de 1 à 2 (le coût est de 10) puis revenez en arrière. Quands = 2, nous obtenons la valeur minimale pour d [4, 2]. Sélectionnez le chemin de 2 à 4 (le coût est de 10) puis revenez en arrière.

Quand s = 1, nous obtenons la valeur minimale pour d [4, 3]. En sélectionnant le chemin 4 à 3 (le coût est de 9), nous passerons ensuite às = Φétape. Nous obtenons la valeur minimale pourd [3, 1] (le coût est de 6).

Un arbre de recherche binaire (BST) est un arbre dans lequel les valeurs de clé sont stockées dans les nœuds internes. Les nœuds externes sont des nœuds nuls. Les clés sont ordonnées lexicographiquement, c'est-à-dire que pour chaque nœud interne, toutes les clés du sous-arbre gauche sont inférieures aux clés du nœud, et toutes les clés du sous-arbre droit sont plus grandes.

Lorsque nous connaissons la fréquence de recherche de chacune des clés, il est assez facile de calculer le coût attendu d'accès à chaque nœud de l'arbre. Un arbre de recherche binaire optimal est un BST, qui a un coût attendu minimal pour localiser chaque nœud

Le temps de recherche d'un élément dans un BST est O(n), alors que dans un temps de recherche Balanced-BST est O(log n). Encore une fois, le temps de recherche peut être amélioré dans l'arbre de recherche binaire à coût optimal, en plaçant les données les plus fréquemment utilisées à la racine et plus près de l'élément racine, tout en plaçant les données les moins fréquemment utilisées près des feuilles et dans les feuilles.

Ici, l'algorithme optimal d'arbre de recherche binaire est présenté. Tout d'abord, nous construisons un BST à partir d'un ensemble den nombre de clés distinctes < k₁, k₂, k₃, ... k_n >. Ici, nous supposons, la probabilité d'accéder à une cléK_i est p_i. Quelques clés factices (d₀, d₁, d₂, ... d_n) sont ajoutés car certaines recherches peuvent être effectuées pour les valeurs qui ne sont pas présentes dans l'ensemble de clés K. Nous supposons, pour chaque clé facticed_i la probabilité d'accès est q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

Une analyse

L'algorithme nécessite O (n³) temps, depuis trois imbriqués fordes boucles sont utilisées. Chacune de ces boucles prend au plusn valeurs.

Exemple

Compte tenu de l'arbre suivant, le coût est de 2,80, bien que ce ne soit pas un résultat optimal.

Nœud	Profondeur	Probabilité	Contribution
k 1	1	0,15	0,30
k 2	0	0,10	0,10
k 3	2	0,05	0,15
k 4	1	0,10	0,20
k 5	2	0,20	0,60
d 0	2	0,05	0,15
d 1	2	0,10	0,30
d 2	3	0,05	0,20
d 3	3	0,05	0,20
d 4	3	0,05	0,20
d 5	3	0,10	0,40
Total			2,80

Pour obtenir une solution optimale, en utilisant l'algorithme décrit dans ce chapitre, les tableaux suivants sont générés.

Dans les tableaux suivants, l'index de colonne est i et l'index de ligne est j.

e	1	2	3	4	5	6
5	2,75	2,00	1,30	0,90	0,50	0,10
4	1,75	1,20	0,60	0,30	0,05
3	1,25	0,70	0,25	0,05
2	0,90	0,40	0,05
1	0,45	0,10
0	0,05

w	1	2	3	4	5	6
5	1,00	0,80	0,60	0,50	0,35	0,10
4	0,70	0,50	0,30	0,20	0,05
3	0,55	0,35	0,15	0,05
2	0,45	0,25	0,05
1	0,30	0,10
0	0,05

racine	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

À partir de ces tables, l'arbre optimal peut être formé.

Il existe plusieurs types de tas, cependant dans ce chapitre, nous allons discuter du tas binaire. UNEbinary heapest une structure de données, qui ressemble à un arbre binaire complet. La structure de données du tas obéit aux propriétés de classement décrites ci-dessous. Généralement, un tas est représenté par un tableau. Dans ce chapitre, nous représentons un tas parH.

Comme les éléments d'un tas sont stockés dans un tableau, en considérant l'index de départ comme 1, la position du nœud parent de i^th élément peut être trouvé à ⌊ i/2 ⌋. Enfant gauche et enfant droit dei^th le nœud est en position 2i et 2i + 1.

Un tas binaire peut être classé comme un max-heap ou un min-heap en fonction de la propriété de commande.

Max-Heap

Dans ce tas, la valeur de clé d'un nœud est supérieure ou égale à la valeur de clé de l'enfant le plus élevé.

Par conséquent, H[Parent(i)] ≥ H[i]

Min-Heap

Dans le tas moyen, la valeur de clé d'un nœud est inférieure ou égale à la valeur de clé de l'enfant le plus bas.

Par conséquent, H[Parent(i)] ≤ H[i]

Dans ce contexte, les opérations de base sont présentées ci-dessous par rapport à Max-Heap. L'insertion et la suppression d'éléments dans et à partir des tas nécessitent un réarrangement des éléments. Par conséquent,Heapify la fonction doit être appelée.

Représentation du tableau

Un arbre binaire complet peut être représenté par un tableau, stockant ses éléments en utilisant la traversée par ordre de niveau.

Considérons un tas (comme indiqué ci-dessous) qui sera représenté par un tableau H.

Considérant l'index de départ comme 0, en utilisant la traversée par ordre de niveau, les éléments sont conservés dans un tableau comme suit.

Index	0	1	2	3	4	5	6	sept	8	...
elements	70	30	50	12	20	35	25	4	8	...

Dans ce contexte, les opérations sur le tas sont représentées par rapport à Max-Heap.

Pour trouver l'index du parent d'un élément à l'index i, l'algorithme suivant Parent (numbers[], i) est utilisé.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

L'index de l'enfant gauche d'un élément à l'index i peut être trouvée en utilisant l'algorithme suivant, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

L'index de l'enfant droit d'un élément à l'index i peut être trouvée en utilisant l'algorithme suivant, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL

Pour insérer un élément dans un tas, le nouvel élément est initialement ajouté à la fin du tas comme dernier élément du tableau.

Après avoir inséré cet élément, la propriété du tas peut être violée, par conséquent la propriété du tas est réparée en comparant l'élément ajouté avec son parent et en déplaçant l'élément ajouté vers le haut, en échangeant des positions avec le parent. Ce processus s'appellepercolation up.

La comparaison est répétée jusqu'à ce que le parent soit plus grand ou égal à l'élément percolateur.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Une analyse

Au départ, un élément est ajouté à la fin du tableau. S'il viole la propriété du tas, l'élément est échangé avec son parent. La hauteur de l'arbre estlog n. Maximumlog n nombre d’opérations à effectuer.

Par conséquent, la complexité de cette fonction est O(log n).

Exemple

Considérons un tas max, comme indiqué ci-dessous, où un nouvel élément 5 doit être ajouté.

Initialement, 55 seront ajoutés à la fin de ce tableau.

Après l'insertion, il viole la propriété du tas. Par conséquent, l'élément doit échanger avec son parent. Après l'échange, le tas ressemble à ce qui suit.

Là encore, l'élément viole la propriété de heap. Par conséquent, il est échangé avec son parent.

Maintenant, nous devons nous arrêter.

La méthode Heapify réorganise les éléments d'un tableau où les sous-arborescences gauche et droite de i^th L'élément obéit à la propriété du tas.

Algorithm: Max-Heapify(numbers[], i) 
leftchild := numbers[2i] 
rightchild := numbers [2i + 1] 
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
   largest := leftchild 
else 
   largest := i 
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
   largest := rightchild 
if largest ≠ i 
   swap numbers[i] with numbers[largest] 
   Max-Heapify(numbers, largest)

Lorsque le tableau fourni n'obéit pas à la propriété du tas, le tas est construit en fonction de l'algorithme suivant Build-Max-Heap (numbers[]).

Algorithm: Build-Max-Heap(numbers[]) 
numbers[].size := numbers[].length 
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 
   Max-Heapify (numbers[], i)

La méthode d'extraction est utilisée pour extraire l'élément racine d'un tas. Voici l'algorithme.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

Exemple

Prenons le même exemple discuté précédemment. Nous voulons maintenant extraire un élément. Cette méthode retournera l'élément racine du tas.

Après la suppression de l'élément racine, le dernier élément sera déplacé vers la position racine.

Maintenant, la fonction Heapify sera appelée. Après Heapify, le tas suivant est généré.

Bubble Sort est un algorithme de tri élémentaire, qui fonctionne en échangeant à plusieurs reprises des éléments adjacents, si nécessaire. Lorsqu'aucun échange n'est requis, le fichier est trié.

Il s'agit de la technique la plus simple parmi tous les algorithmes de tri.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

la mise en oeuvre

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Une analyse

Ici, le nombre de comparaisons est

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Clairement, le graphique montre le n² nature de la sorte de bulle.

Dans cet algorithme, le nombre de comparaison est indépendant de l'ensemble de données, c'est-à-dire si les éléments d'entrée fournis sont dans l'ordre trié ou dans l'ordre inverse ou au hasard.

Mémoire nécessaire

D'après l'algorithme indiqué ci-dessus, il est clair que le tri à bulles ne nécessite pas de mémoire supplémentaire.

Exemple

Unsorted list:

5 2 1 4 3 sept 6

1 ^er itération:

5 > 2 swap	2 5 1 4 3 sept 6
5 > 1 swap	2 1 5 4 3 sept 6
5 > 4 swap	2 1 4 5 3 sept 6
5 > 3 swap	2 1 4 3 5 sept 6
5 < 7 no swap	2 1 4 3 5 sept 6
7 > 6 swap	2 1 4 3 5 6 sept

2 ^ème itération:

2 > 1 swap	1 2 4 3 5 6 sept
2 < 4 no swap	1 2 4 3 5 6 sept
4 > 3 swap	1 2 3 4 5 6 sept
4 < 5 no swap	1 2 3 4 5 6 sept
5 < 6 no swap	1 2 3 4 5 6 sept

Il n'y a pas de changement de 3 ^e , 4 ^e , 5 ^e et 6 ^e itération.

Finalement,

the sorted list is

1 2 3 4 5 6 sept

Le tri par insertion est une méthode très simple pour trier les nombres dans un ordre croissant ou décroissant. Cette méthode suit la méthode incrémentielle. Il peut être comparé à la technique de tri des cartes au moment de la partie.

Les nombres, qui doivent être triés, sont appelés keys. Voici l'algorithme de la méthode de tri par insertion.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Une analyse

Le temps d'exécution de cet algorithme dépend beaucoup de l'entrée donnée.

Si les nombres donnés sont triés, cet algorithme s'exécute dans O(n)temps. Si les nombres donnés sont dans l'ordre inverse, l'algorithme s'exécute enO(n²) temps.

Exemple

Unsorted list:

2 13 5 18 14

1^st iteration:

Clé = a [2] = 13

a [1] = 2 <13

Swap, pas de swap

2 13 5 18 14

2^nd iteration:

Clé = a [3] = 5

a [2] = 13> 5

Swap 5 et 13

2 5 13 18 14

Ensuite, a [1] = 2 <13

Swap, pas de swap

2 5 13 18 14

3^rd iteration:

Clé = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Swap, pas de swap

2 5 13 18 14

4^th iteration:

Clé = a [5] = 14

a [4] = 18> 14

Swap 18 et 14

2 5 13 14 18

Ensuite, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Donc, pas de swap

2 5 13 14 18

Finalement,

the sorted list is

2 5 13 14 18

Ce type de tri s'appelle Selection Sortcar il fonctionne en triant les éléments à plusieurs reprises. Cela fonctionne comme suit: trouvez d'abord le plus petit du tableau et échangez-le avec l'élément en première position, puis trouvez le deuxième plus petit élément et échangez-le avec l'élément en deuxième position, et continuez ainsi jusqu'à ce que tout le tableau soit triés.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Le tri par sélection fait partie des techniques de tri les plus simples et fonctionne très bien pour les petits fichiers. Il a une application assez importante car chaque élément est déplacé au plus une fois.

Le tri par section est une méthode de choix pour trier des fichiers avec de très gros objets (enregistrements) et de petites clés. Le pire des cas se produit si le tableau est déjà trié dans un ordre décroissant et que nous voulons les trier dans un ordre croissant.

Néanmoins, le temps requis par l'algorithme de tri par sélection n'est pas très sensible à l'ordre d'origine du tableau à trier: le test si A[j] < min x est exécuté exactement le même nombre de fois dans tous les cas.

Le tri par sélection passe la plupart de son temps à essayer de trouver l'élément minimum dans la partie non triée du tableau. Cela montre clairement la similitude entre le tri par sélection et le tri par bulle.

• Le tri par bulles sélectionne le maximum d'éléments restants à chaque étape, mais gaspille un peu d'effort pour donner de l'ordre à une partie non triée du tableau.

• Le tri par sélection est quadratique dans le cas le plus défavorable et dans le cas moyen et ne nécessite aucune mémoire supplémentaire.

Pour chaque i de 1 à n - 1, il y a un échange et n - i comparaisons, il y a donc un total de n - 1 échanges et

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparaisons.

Ces observations sont valables, quelles que soient les données d'entrée.

Dans le pire des cas, cela pourrait être quadratique, mais dans le cas moyen, cette quantité est O(n log n). Cela implique que lerunning time of Selection sort is quite insensitive to the input.

la mise en oeuvre

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Exemple

Unsorted list:

5 2 1 4 3

1 ^er itération:

Plus petit = 5

2 <5, le plus petit = 2

1 <2, le plus petit = 1

4> 1, le plus petit = 1

3> 1, le plus petit = 1

Swap 5 et 1

1 2 5 4 3

2 ^ème itération:

Plus petit = 2

2 <5, le plus petit = 2

2 <4, le plus petit = 2

2 <3, le plus petit = 2

Pas d'échange

1 2 5 4 3

3 ^ème itération:

Plus petit = 5

4 <5, le plus petit = 4

3 <4, le plus petit = 3

Swap 5 et 3

1 2 3 4 5

4 ^ème itération:

Plus petit = 4

4 <5, le plus petit = 4

Pas d'échange

1 2 3 4 5

Finalement,

the sorted list is

1 2 3 4 5

Il est utilisé sur le principe de diviser pour conquérir. Le tri rapide est un algorithme de choix dans de nombreuses situations car il n'est pas difficile à mettre en œuvre. C'est un bon tri à usage général et il consomme relativement moins de ressources lors de l'exécution.

Avantages

• Il est en place car il n'utilise qu'une petite pile auxiliaire.

• Il ne nécessite que n (log n) il est temps de trier n articles.

• Il a une boucle intérieure extrêmement courte.

• Cet algorithme a été soumis à une analyse mathématique approfondie, une déclaration très précise peut être faite sur les problèmes de performances.

Désavantages

• C'est récursif. Surtout, si la récursivité n'est pas disponible, la mise en œuvre est extrêmement compliquée.

• Il nécessite un temps quadratique (c'est-à-dire n2) dans le pire des cas.

• Il est fragile, c'est-à-dire qu'une simple erreur de mise en œuvre peut passer inaperçue et entraîner de mauvaises performances.

Le tri rapide fonctionne en partitionnant un tableau donné A[p ... r] en deux sous-tableaux non vides A[p ... q] et A[q+1 ... r] de telle sorte que chaque clé dans A[p ... q] est inférieur ou égal à chaque clé dans A[q+1 ... r].

Ensuite, les deux sous-tableaux sont triés par des appels récursifs au tri rapide. La position exacte de la partition dépend du tableau et de l'index donnésq est calculé dans le cadre de la procédure de partitionnement.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Notez que pour trier le tableau entier, l'appel initial doit être Quick-Sort (A, 1, length[A])

Dans un premier temps, Tri rapide choisit l'un des éléments du tableau à trier comme pivot. Ensuite, le tableau est partitionné de chaque côté du pivot. Les éléments inférieurs ou égaux à pivot se déplaceront vers la gauche, tandis que les éléments supérieurs ou égaux à pivot se déplaceront vers la droite.

Partitionner le tableau

La procédure de partitionnement réorganise les sous-tableaux sur place.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Une analyse

Le pire des cas de complexité de l'algorithme de tri rapide est O(n²). Cependant, en utilisant cette technique, dans les cas moyens, nous obtenons généralement la sortie enO(n log n) temps.

Radix sortest une petite méthode que de nombreuses personnes utilisent intuitivement pour classer par ordre alphabétique une grande liste de noms. Plus précisément, la liste des noms est d'abord triée en fonction de la première lettre de chaque nom, c'est-à-dire que les noms sont organisés en 26 classes.

Intuitivement, on peut vouloir trier les nombres sur leur chiffre le plus significatif. Cependant, le tri Radix fonctionne de manière contre-intuitive en triant d'abord les chiffres les moins significatifs. Lors du premier passage, tous les nombres sont triés sur le chiffre le moins significatif et combinés dans un tableau. Ensuite, au deuxième passage, les nombres entiers sont à nouveau triés sur les deuxièmes chiffres les moins significatifs et combinés dans un tableau et ainsi de suite.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Une analyse

Chaque touche est regardée une fois pour chaque chiffre (ou lettre si les touches sont alphabétiques) de la touche la plus longue. Par conséquent, si la clé la plus longue am chiffres et il y a n clés, le tri de base a un ordre O(m.n).

Cependant, si nous regardons ces deux valeurs, la taille des clés sera relativement petite par rapport au nombre de clés. Par exemple, si nous avons des clés à six chiffres, nous pourrions avoir un million d'enregistrements différents.

Ici, on voit que la taille des clés n'est pas significative, et cet algorithme est de complexité linéaire O(n).

Exemple

L'exemple suivant montre comment le tri Radix fonctionne sur sept nombres à 3 chiffres.

Contribution	1 er col	2 ème passage	3 ème passage
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

Dans l'exemple ci-dessus, la première colonne est l'entrée. Les colonnes restantes affichent la liste après des tris successifs sur des positions de chiffres de plus en plus significatives. Le code pour le tri Radix suppose que chaque élément d'un tableauA de n éléments a d chiffres, où chiffre 1 est le chiffre le plus bas et d est le chiffre d'ordre le plus élevé.

Pour comprendre la classe P et NP, nous devons d'abord connaître le modèle de calcul. Par conséquent, dans ce chapitre, nous discuterons de deux modèles de calcul importants.

Calcul déterministe et classe P

Machine de Turing déterministe

L'un de ces modèles est la machine de Turing à une bande déterministe. Cette machine se compose d'un contrôle d'état fini, d'une tête de lecture-écriture et d'une bande bidirectionnelle à séquence infinie.

Voici le diagramme schématique d'une machine de Turing à une bande déterministe.

Un programme pour une machine de Turing déterministe spécifie les informations suivantes -

• Un ensemble fini de symboles de bande (symboles d'entrée et symbole vide)
• Un ensemble fini d'états
• Une fonction de transition

En analyse algorithmique, si un problème peut être résolu en temps polynomial par une machine de Turing à une bande déterministe, le problème appartient à la classe P.

Calcul non déterministe et classe NP

Machine de Turing non déterministe

Pour résoudre le problème de calcul, un autre modèle est la machine de Turing non déterministe (NDTM). La structure de NDTM est similaire à DTM, mais nous avons ici un module supplémentaire appelé module de devinettes, qui est associé à une tête d'écriture seule.

Voici le diagramme schématique.

Si le problème est résoluble en temps polynomial par une machine de Turing non déterministe, le problème appartient à la classe NP.

Dans un graphe non orienté, un cliqueest un sous-graphique complet du graphique donné. Sous-graphe complet signifie que tous les sommets de ce sous-graphe sont connectés à tous les autres sommets de ce sous-graphe.

Le problème Max-Clique est le problème de calcul de trouver la clique maximale du graphe. Max clique est utilisé dans de nombreux problèmes du monde réel.

Considérons une application de réseautage social, où les sommets représentent le profil des personnes et les arêtes représentent une connaissance mutuelle dans un graphique. Dans ce graphique, une clique représente un sous-ensemble de personnes qui se connaissent toutes.

Pour trouver une clique maximale, on peut systématiquement inspecter tous les sous-ensembles, mais ce type de recherche par force brute est trop long pour les réseaux comportant plus de quelques dizaines de sommets.

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

Une analyse

Le problème Max-Clique est un algorithme non déterministe. Dans cet algorithme, nous essayons d'abord de déterminer un ensemble dek des sommets distincts puis nous essayons de tester si ces sommets forment un graphe complet.

Il n'y a pas d'algorithme déterministe polynomial pour résoudre ce problème. Ce problème est NP-Complete.

Exemple

Jetez un œil au graphique suivant. Ici, le sous-graphe contenant les sommets 2, 3, 4 et 6 forme un graphe complet. Par conséquent, ce sous-graphique est unclique. Comme il s'agit du sous-graphique complet maximum du graphique fourni, c'est un4-Clique.

Une couverture de sommet d'un graphe non orienté G = (V, E) est un sous-ensemble de sommets V^' ⊆ V tel que si bord (u, v) est un bord de G, alors soit u dans V ou v dans V^' ou les deux.

Trouvez une couverture de sommet de taille maximale dans un graphe non orienté donné. Ce vertexcover optimal est la version d'optimisation d'un problème NP-complet. Cependant, il n'est pas trop difficile de trouver une couverture de sommets presque optimale.

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

Exemple

L'ensemble des arêtes du graphe donné est -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Maintenant, nous commençons par sélectionner une arête arbitraire (1,6). Nous éliminons toutes les arêtes, qui sont soit incidentes au sommet 1 ou 6 et nous ajoutons l'arête (1,6) pour couvrir.

Dans l'étape suivante, nous avons choisi une autre arête (2,3) au hasard

Maintenant, nous sélectionnons une autre arête (4,7).

Nous sélectionnons une autre arête (8,5).

Par conséquent, la couverture des sommets de ce graphe est {1,2,4,5}.

Une analyse

Il est facile de voir que le temps d'exécution de cet algorithme est O(V + E), en utilisant la liste de contiguïté pour représenter E^'.

En informatique, de nombreux problèmes sont résolus où l'objectif est de maximiser ou de minimiser certaines valeurs, tandis que dans d'autres problèmes, nous essayons de trouver s'il y a une solution ou non. Par conséquent, les problèmes peuvent être classés comme suit -

Problème d'optimisation

Les problèmes d'optimisation sont ceux pour lesquels l'objectif est de maximiser ou de minimiser certaines valeurs. Par exemple,

• Trouver le nombre minimum de couleurs nécessaires pour colorer un graphique donné.

• Trouver le chemin le plus court entre deux sommets dans un graphe.

Problème de décision

Il existe de nombreux problèmes pour lesquels la réponse est oui ou non. Ces types de problèmes sont connus sous le nom de decision problems. Par exemple,

• Si un graphique donné peut être coloré par seulement 4 couleurs.

• Trouver un cycle hamiltonien dans un graphe n'est pas un problème de décision, alors que vérifier qu'un graphe est hamiltonien ou non est un problème de décision.

Qu'est-ce que la langue?

Chaque problème de décision ne peut avoir que deux réponses, oui ou non. Par conséquent, un problème de décision peut appartenir à une langue s'il fournit une réponse «oui» pour une entrée spécifique. Une langue est la totalité des entrées pour lesquelles la réponse est Oui. La plupart des algorithmes discutés dans les chapitres précédents sontpolynomial time algorithms.

Pour la taille d'entrée n, si la complexité temporelle du pire des cas d'un algorithme est O(n^k), où k est une constante, l'algorithme est un algorithme de temps polynomial.

Les algorithmes tels que la multiplication de la chaîne matricielle, le chemin le plus court de source unique, le chemin le plus court de toutes les paires, l'arbre couvrant minimum, etc. s'exécutent en temps polynomial. Cependant, il existe de nombreux problèmes, tels que le vendeur itinérant, la coloration optimale des graphiques, les cycles hamiltoniens, la recherche du chemin le plus long dans un graphique et la satisfaction d'une formule booléenne, pour laquelle aucun algorithme de temps polynomial n'est connu. Ces problèmes appartiennent à une classe intéressante de problèmes, appelés lesNP-Complete problèmes, dont le statut est inconnu.

Dans ce contexte, nous pouvons catégoriser les problèmes comme suit -

Classe P

La classe P comprend les problèmes qui peuvent être résolus en temps polynomial, c'est-à-dire que ces problèmes peuvent être résolus en temps O(n^k) dans le pire des cas, où k est constante.

Ces problèmes sont appelés tractable, tandis que d'autres sont appelés intractable or superpolynomial.

Formellement, un algorithme est un algorithme de temps polynomial, s'il existe un polynôme p(n) tel que l'algorithme peut résoudre n'importe quelle instance de taille n dans un temps O(p(n)).

Problème nécessitant Ω(n⁵⁰) le temps de résolution est essentiellement intraitable pour les grands n. L'algorithme de temps polynomial le plus connu s'exécute dans le tempsO(n^k) pour une valeur assez faible de k.

L'avantage de considérer la classe des algorithmes en temps polynomial est que tous deterministic single processor model of computation peuvent être simulés l'un sur l'autre avec au plus un polynôme slow-d

Classe NP

La classe NP comprend les problèmes vérifiables en temps polynomial. NP est la classe des problèmes de décision pour lesquels il est facile de vérifier l'exactitude d'une réponse revendiquée, à l'aide d'un peu d'informations supplémentaires. Par conséquent, nous ne demandons pas un moyen de trouver une solution, mais seulement de vérifier qu'une solution alléguée est vraiment correcte.

Tous les problèmes de cette classe peuvent être résolus en temps exponentiel en utilisant une recherche exhaustive.

P contre NP

Tout problème de décision qui peut être résolu par un algorithme de temps polynomial déterministe peut également être résolu par un algorithme non déterministe de temps polynomial.

Tous les problèmes de P peuvent être résolus avec des algorithmes de temps polynomiaux, alors que tous les problèmes de NP - P sont insolubles.

On ne sait pas si P = NP. Cependant, de nombreux problèmes sont connus dans NP avec la propriété que s'ils appartiennent à P, alors on peut prouver que P = NP.

Si P ≠ NP, il y a des problèmes dans NP qui ne sont ni dans P ni dans NP-Complete.

Le problème appartient à la classe Ps'il est facile de trouver une solution au problème. Le problème appartient àNP, s'il est facile de vérifier une solution qui peut avoir été très fastidieuse à trouver.

Stephen Cook a présenté quatre théorèmes dans son article «La complexité des procédures de démonstration du théorème». Ces théorèmes sont énoncés ci-dessous. Nous comprenons que de nombreux termes inconnus sont utilisés dans ce chapitre, mais nous n'avons aucune possibilité de discuter de tout en détail.

Voici les quatre théorèmes de Stephen Cook -

Théorème-1

Si un ensemble S de chaînes est acceptée par une machine de Turing non déterministe dans un temps polynomial, alors S est P-réductible à {tautologies DNF}.

Théorème-2

Les ensembles suivants sont P-réductibles les uns aux autres par paires (et donc chacun a le même degré de difficulté polynomial): {tautologies}, {DNF tautologies}, D3, {paires de sous-graphes}.

Théorème-3

• Pour toute T_Q(k) de type Q, $\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ est illimité

• Il y a un T_Q(k) de type Q tel que $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$

Théorème-4

Si l'ensemble S de chaînes est accepté par une machine non déterministe dans le temps T(n) = 2ⁿ, et si T_Q(k) est une fonction honnête (c'est-à-dire dénombrable en temps réel) de type Q, alors il y a une constante K, alors S peut être reconnu par une machine déterministe dans le temps T_Q(K8ⁿ).

• Premièrement, il a souligné l'importance de la réductibilité polynomiale du temps. Cela signifie que si nous avons une réduction de temps polynomiale d'un problème à un autre, cela garantit que tout algorithme de temps polynomial du deuxième problème peut être converti en un algorithme de temps polynomial correspondant pour le premier problème.

• Deuxièmement, il a concentré son attention sur la classe NP des problèmes de décision qui peuvent être résolus en temps polynomial par un ordinateur non déterministe. La plupart des problèmes insolubles appartiennent à cette classe, NP.

• Troisièmement, il a prouvé qu'un problème particulier de NP a la propriété que tout autre problème de NP peut lui être réduit de manière polynomiale. Si le problème de satisfiabilité peut être résolu avec un algorithme de temps polynomial, alors chaque problème de NP peut également être résolu en temps polynomial. Si un problème dans NP est insoluble, alors le problème de satisfiabilité doit être insoluble. Ainsi, le problème de satisfiabilité est le problème le plus difficile dans NP.

• Quatrièmement, Cook a suggéré que d'autres problèmes de NP pourraient partager avec le problème de satisfiabilité cette propriété d'être le membre le plus difficile de NP.

Un problème est dans la classe NPC s'il est dans NP et est comme hardcomme tout problème dans NP. Un problème estNP-hard si tous les problèmes de NP lui sont réductibles en temps polynomial, même s'il peut ne pas être dans NP lui-même.

Si un algorithme de temps polynomial existe pour l'un de ces problèmes, tous les problèmes de NP seraient résolubles en temps polynomial. Ces problèmes sont appelésNP-complete. Le phénomène d'exhaustivité des NP est important pour des raisons à la fois théoriques et pratiques.

Définition de l'exhaustivité NP

Une langue B est NP-complete s'il remplit deux conditions

• B est en NP

• Chaque A dans NP est le temps polynomial réductible à B.

Si une langue satisfait la deuxième propriété, mais pas nécessairement la première, la langue B est connu comme NP-Hard. De manière informelle, un problème de rechercheB est NP-Hard s'il en existe NP-Complete problème A que Turing réduit à B.

Le problème dans NP-Hard ne peut être résolu en temps polynomial, tant que P = NP. Si un problème s'avère être un NPC, il n'est pas nécessaire de perdre du temps à essayer de trouver un algorithme efficace pour cela. Au lieu de cela, nous pouvons nous concentrer sur l'algorithme d'approximation de la conception.

Problèmes NP-Complete

Voici quelques problèmes NP-Complete, pour lesquels aucun algorithme de temps polynomial n'est connu.

• Déterminer si un graphe a un cycle hamiltonien
• Déterminer si une formule booléenne est satisfiable, etc.

Problèmes NP-Hard

Les problèmes suivants sont NP-Hard

• Le problème de la satisfiabilité des circuits
• Set Cover
• Couverture Vertex
• Problème de vendeur itinérant

Dans ce contexte, nous allons maintenant discuter de TSP is NP-Complete

TSP est NP-Complete

Le problème du voyageur de commerce se compose d'un vendeur et d'un ensemble de villes. Le vendeur doit visiter chacune des villes en partant d'une certaine et en revenant dans la même ville. Le défi du problème est que le voyageur de commerce veut minimiser la durée totale du voyage

Preuve

Prouver TSP is NP-Complete, nous devons d'abord prouver que TSP belongs to NP. Dans TSP, nous trouvons un tour et vérifions que le tour contient chaque sommet une fois. Ensuite, le coût total des bords de la tournée est calculé. Enfin, nous vérifions si le coût est minimum. Cela peut être effectué en temps polynomial. DoncTSP belongs to NP.

Deuxièmement, nous devons prouver que TSP is NP-hard. Pour le prouver, une façon est de montrer queHamiltonian cycle ≤_p TSP (comme nous savons que le problème du cycle hamiltonien est NPcomplete).

Présumer G = (V, E) être une instance du cycle hamiltonien.

Par conséquent, une instance de TSP est construite. Nous créons le graphique completG^' = (V, E^'), où

$$E^{'}=\lbrace(i, j)\colon i, j \in V \:\:and\:i\neq j$$

Ainsi, la fonction de coût est définie comme suit -

$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & otherwise\end{cases}$$

Maintenant, supposons qu'un cycle hamiltonien h existe dans G. Il est clair que le coût de chaque bord enh est 0 dans G^' comme chaque bord appartient à E. Par conséquent,h a un coût de 0 dans G^'. Ainsi, si grapheG a un cycle hamiltonien, puis graphe G^' a une visite de 0 Coût.

Inversement, nous supposons que G^' a une tournée h^' du coût au plus 0. Le coût des bords dansE^' sont 0 et 1par définition. Par conséquent, chaque bord doit avoir un coût de0 comme le coût de h^' est 0. Nous concluons donc queh^' contient uniquement des arêtes dans E.

Nous avons ainsi prouvé que G a un cycle hamiltonien, si et seulement si G^' a une tournée de coût au plus 0. TSP est NP-complet.

Les algorithmes discutés dans les chapitres précédents fonctionnent systématiquement. Pour atteindre l'objectif, un ou plusieurs chemins explorés précédemment vers la solution doivent être stockés pour trouver la solution optimale.

Pour de nombreux problèmes, le chemin vers l'objectif est sans importance. Par exemple, dans le problème N-Queens, nous n'avons pas besoin de nous soucier de la configuration finale des reines ni de l'ordre dans lequel les reines sont ajoutées.

Escalade

L'escalade est une technique permettant de résoudre certains problèmes d'optimisation. Dans cette technique, nous commençons avec une solution sous-optimale et la solution est améliorée à plusieurs reprises jusqu'à ce qu'une condition soit maximisée.

L'idée de commencer avec une solution sous-optimale est comparée à partir de la base de la colline, l'amélioration de la solution est comparée à la montée de la colline, et enfin, maximiser certaines conditions est comparé à atteindre le sommet de la colline.

Par conséquent, la technique d'escalade peut être considérée comme les phases suivantes -

• Construire une solution sous-optimale obéissant aux contraintes du problème
• Améliorer la solution étape par étape
• Améliorer la solution jusqu'à ce que plus aucune amélioration ne soit possible

La technique de l'escalade est principalement utilisée pour résoudre des problèmes complexes de calcul. Il ne regarde que l'état actuel et l'état futur immédiat. Par conséquent, cette technique est efficace en mémoire car elle ne maintient pas d'arbre de recherche.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Amélioration itérative

Dans la méthode d'amélioration itérative, la solution optimale est obtenue en progressant vers une solution optimale à chaque itération. Cependant, cette technique peut rencontrer des maxima locaux. Dans cette situation, il n'y a pas d'état proche pour une meilleure solution.

Ce problème peut être évité par différentes méthodes. L'une de ces méthodes est le recuit simulé.

Redémarrage aléatoire

C'est une autre méthode pour résoudre le problème des optima locaux. Cette technique effectue une série de recherches. À chaque fois, il part d'un état initial généré aléatoirement. Par conséquent, une solution optimale ou presque optimale peut être obtenue en comparant les solutions des recherches effectuées.

Problèmes de la technique d'escalade

Maxima locale

Si l'heuristique n'est pas convexe, l'escalade peut converger vers des maxima locaux, au lieu de maxima globaux.

Crêtes et ruelles

Si la fonction cible crée une crête étroite, le grimpeur ne peut grimper la crête ou descendre l'allée qu'en zig-zag. Dans ce scénario, le grimpeur doit faire de très petits pas nécessitant plus de temps pour atteindre l'objectif.

Plateau

Un plateau est rencontré lorsque l'espace de recherche est plat ou suffisamment plat pour que la valeur renvoyée par la fonction cible ne puisse pas être distinguée de la valeur renvoyée pour les régions proches, en raison de la précision utilisée par la machine pour représenter sa valeur.

Complexité de la technique d'escalade

Cette technique ne souffre pas de problèmes liés à l'espace, car elle ne regarde que l'état actuel. Les chemins précédemment explorés ne sont pas stockés.

Pour la plupart des problèmes de la technique d'escalade à redémarrage aléatoire, une solution optimale peut être obtenue en temps polynomial. Cependant, pour les problèmes NP-Complete, le temps de calcul peut être exponentiel basé sur le nombre de maxima locaux.

Applications de la technique d'escalade

La technique d'escalade de colline peut être utilisée pour résoudre de nombreux problèmes, où l'état actuel permet une fonction d'évaluation précise, comme le flux réseau, le problème du voyageur de commerce, le problème 8-Queens, la conception de circuits intégrés, etc.

L'escalade est également utilisée dans les méthodes d'apprentissage inductives. Cette technique est utilisée en robotique pour la coordination entre plusieurs robots dans une équipe. Il existe de nombreux autres problèmes où cette technique est utilisée.

Exemple

Cette technique peut être appliquée pour résoudre le problème du voyageur de commerce. Tout d'abord, une solution initiale est déterminée qui visite toutes les villes une seule fois. Par conséquent, cette solution initiale n'est pas optimale dans la plupart des cas. Même cette solution peut être très mauvaise. L'algorithme Hill Climbing démarre avec une telle solution initiale et y apporte des améliorations de manière itérative. Finalement, un itinéraire beaucoup plus court est susceptible d'être obtenu.