algorithm
Algorithmes Gourmands

Remarques

Problème de sac à dos continu

Compte tenu des éléments comme (value, weight) nous devons les placer dans un sac à dos (conteneur) d'une capacité k . Remarque! Nous pouvons casser des articles pour maximiser la valeur!

Exemple d'entrée:

values[] = [1, 4, 5, 2, 10]
weights[] = [3, 2, 1, 2, 4]
k = 8

Production attendue:

maximumValueOfItemsInK = 20;

Algorithme:

1) Sort values and weights by value/weight.
   values[] = [5, 10, 4, 2, 1]
   weights[] = [1, 4, 2, 2, 3]
2) currentWeight = 0; currentValue = 0;
3) FOR i = 0; currentWeight < k && i < values.length; i++ DO:
       IF k - currentWeight < weights[i] DO
           currentValue = currentValue + values[i];
           currentWeight = currentWeight + weights[i];
       ELSE
           currentValue = currentValue + values[i]*(k - currentWeight)/weights[i]
           currentWeight = currentWeight + weights[i]*(k - currentWeight)/weights[i]
       END_IF
   END_FOR
   PRINT "maximumValueOfItemsInK = " + currentValue;

Huffman Codage

Le code Huffman est un type particulier de code de préfixe optimal couramment utilisé pour la compression de données sans perte. Il compresse très efficacement les données en économisant de 20% à 90% de mémoire, en fonction des caractéristiques des données compressées. Nous considérons les données comme une suite de caractères. L'algorithme glouton d'Huffman utilise un tableau donnant la fréquence à laquelle chaque caractère se produit (c.-à-d. Sa fréquence) pour constituer une manière optimale de représenter chaque caractère sous la forme d'une chaîne binaire. Le code de Huffman a été proposé par David A. Huffman en 1951.

Supposons que nous ayons un fichier de données de 100 000 caractères que nous souhaitons stocker de manière compacte. Nous supposons qu'il n'y a que 6 caractères différents dans ce fichier. La fréquence des caractères est donnée par:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
|Frequency (in thousands)|  45 |  13 |  12 |  16 |  9  |  5  |
+------------------------+-----+-----+-----+-----+-----+-----+

Nous avons plusieurs options pour représenter un tel fichier d'informations. Ici, nous considérons le problème de la conception d'un code de caractère binaire dans lequel chaque caractère est représenté par une chaîne binaire unique, que nous appelons un mot de code .

L'arbre construit nous fournira:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
| Fixed-length Codeword  | 000 | 001 | 010 | 011 | 100 | 101 |
+------------------------+-----+-----+-----+-----+-----+-----+
|Variable-length Codeword|  0  | 101 | 100 | 111 | 1101| 1100|
+------------------------+-----+-----+-----+-----+-----+-----+

Si nous utilisons un code de longueur fixe , nous avons besoin de trois bits pour représenter 6 caractères. Cette méthode nécessite 300 000 bits pour coder la totalité du fichier. Maintenant, la question est la suivante: pouvons-nous faire mieux?

Un code de longueur variable peut faire beaucoup mieux qu'un code de longueur fixe, en donnant aux mots fréquents des mots de code courts et des mots de code longs sans caractère. Ce code nécessite: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 bits pour représenter le fichier, ce qui économise environ 25% de la mémoire.

Une chose à retenir, nous considérons ici uniquement les codes dans lesquels aucun mot de code n'est également un préfixe d'un autre mot de code. Celles-ci s'appellent des codes de préfixe. Pour le codage à longueur variable, nous codons le fichier à 3 caractères abc avec la valeur 0.101.100 = 0101100, où "." dénote la concaténation.

Les codes de préfixe sont souhaitables car ils simplifient le décodage. Aucun mot de code n'étant un préfixe d'un autre, le mot de code qui commence un fichier codé est sans ambiguïté. Nous pouvons simplement identifier le mot de code initial, le ramener au caractère d'origine et répéter le processus de décodage sur le reste du fichier codé. Par exemple, 001011101 analyse de manière unique comme 0.0.101.1101, ce qui décode en aabe . En bref, toutes les combinaisons de représentations binaires sont uniques. Par exemple, si une lettre est désignée par 110, aucune autre lettre ne sera désignée par 1101 ou 1100. En effet, vous risquez d’être confus quant à la sélection de 110 ou à la concaténation du bit suivant et à sa sélection.

Technique de compression:

La technique fonctionne en créant un arbre binaire de noeuds. Celles-ci peuvent être stockées dans un tableau régulier dont la taille dépend du nombre de symboles, n . Un nœud peut être un nœud feuille ou un nœud interne . Au départ, tous les nœuds sont des nœuds feuilles, qui contiennent le symbole lui-même, sa fréquence et, éventuellement, un lien vers ses nœuds enfants. Par convention, le bit '0' représente l'enfant gauche et le bit '1' représente l'enfant droit. La file d'attente prioritaire est utilisée pour stocker les nœuds, ce qui fournit au nœud la fréquence la plus basse lorsqu'il est survolé. Le processus est décrit ci-dessous:

1. Créez un nœud feuille pour chaque symbole et ajoutez-le à la file d'attente prioritaire.
2. Bien qu'il y ait plus d'un nœud dans la file d'attente:
   1. Supprimez les deux noeuds les plus prioritaires de la file d'attente.
   2. Créez un nouveau nœud interne avec ces deux nœuds en tant qu’enfants et avec une fréquence égale à la somme de la fréquence des deux nœuds.
   3. Ajoutez le nouveau nœud à la file d'attente.
3. Le nœud restant est le nœud racine et l’arbre Huffman est complet.

Pour notre exemple:

Le pseudo-code ressemble à:

Procedure Huffman(C):     // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
    n = node(C[i])
    Q.push(n)
end for
while Q.size() is not equal to 1
    Z = new node()
    Z.left = x = Q.pop
    Z.right = y = Q.pop
    Z.frequency = x.frequency + y.frequency
    Q.push(Z)
end while
Return Q

Bien que les entrées triées selon le temps linéaire, dans les cas généraux d'entrées arbitraires, l'utilisation de cet algorithme nécessite un tri préalable. Ainsi, comme le tri prend du temps O (nlogn) dans les cas généraux, les deux méthodes ont la même complexité.

Comme n est le nombre de symboles dans l'alphabet, qui est généralement très petit (comparé à la longueur du message à coder), la complexité temporelle n'est pas très importante dans le choix de cet algorithme.

Technique de décompression:

Le processus de décompression consiste simplement à traduire le flux de codes de préfixe en valeur d'octet individuel, généralement en parcourant le nœud d'arborescence Huffman par nœud à mesure que chaque bit est lu depuis le flux d'entrée. Atteindre un nœud feuille termine nécessairement la recherche de cette valeur d'octet particulière. La valeur de feuille représente le caractère souhaité. Habituellement, l'arbre Huffman est construit en utilisant des données ajustées statistiquement à chaque cycle de compression, la reconstruction est donc assez simple. Sinon, les informations pour reconstituer l'arborescence doivent être envoyées séparément. Le pseudo-code:

Procedure HuffmanDecompression(root, S):   // root represents the root of Huffman Tree
n := S.length                              // S refers to bit-stream to be decompressed
for i := 1 to n
    current = root
    while current.left != NULL and current.right != NULL
        if S[i] is equal to '0'
            current := current.left
        else
            current := current.right
        endif
        i := i+1
    endwhile
    print current.symbol
endfor

Explication gourmande:
Le codage de Huffman examine l'occurrence de chaque caractère et le stocke comme une chaîne binaire de manière optimale. L'idée est d'affecter des codes de longueur variable aux caractères d'entrée, la longueur des codes assignés étant basée sur les fréquences des caractères correspondants. Nous créons un arbre binaire et nous y travaillons de manière ascendante afin que les deux caractères les plus fréquents soient le plus loin possible de la racine. De cette façon, le caractère le plus fréquent reçoit le plus petit code et le caractère le moins fréquent reçoit le code le plus grand.

Les références:

• Introduction aux algorithmes - Charles E. Leiserson, Clifford Stein, Ronald Rivest et Thomas H. Cormen
• Huffman Coding - Wikipedia
• Mathématiques discrètes et leurs applications - Kenneth H. Rosen

Problème de changement

Étant donné un système monétaire, est-il possible de donner une quantité de pièces et de trouver un ensemble minimal de pièces correspondant à ce montant.

Systèmes monétaires canoniques Pour certains systèmes monétaires, comme ceux que nous utilisons dans la vie réelle, la solution "intuitive" fonctionne parfaitement. Par exemple, si les différentes pièces et billets en euros (à l'exclusion des centimes) sont de 1 €, 2 €, 5 €, 10 €, donner la pièce la plus élevée jusqu'à ce que nous atteignions le montant et répéter cette procédure .

Nous pouvons le faire récursivement avec OCaml:

(* assuming the money system is sorted in decreasing order *)
let change_make money_system amount =
  let rec loop given amount =
    if amount = 0 then given
    else 
      (* we find the first value smaller or equal to the remaining amount *)
      let coin = List.find ((>=) amount) money_system in
      loop (coin::given) (amount - coin)
  in loop [] amount

Ces systèmes sont conçus pour faciliter le changement. Le problème devient plus difficile en ce qui concerne le système monétaire arbitraire.

Cas général Comment donner 99 € avec des pièces de 10 €, 7 € et 5 €? Ici, donner des pièces de 10 € jusqu'à ce qu'il nous reste 9 € conduit évidemment à aucune solution. Pire que cela, une solution pourrait ne pas exister. Ce problème est en fait np-hard, mais des solutions acceptables combinant la gourmandise et la mémorisation existent. L'idée est d'explorer toutes les possibilités et de choisir celle avec le nombre minimal de pièces.

Pour donner un montant X> 0, nous choisissons une pièce P dans le système monétaire, puis nous résolvons le sous-problème correspondant à XP. Nous essayons ceci pour toutes les pièces du système. La solution, si elle existe, est alors le plus petit chemin qui mène à 0.

Voici une fonction récursive OCaml correspondant à cette méthode. Il renvoie Aucun si aucune solution n'existe.

(* option utilities *)
let optmin x y =
  match x,y with
  | None,a | a,None -> a
  | Some x, Some y-> Some (min x y)

let optsucc = function
  | Some x -> Some (x+1)
  | None -> None

(* Change-making problem*)
let change_make money_system amount =
  let rec loop n =
    let onepiece acc piece =
      match n - piece with
      | 0 -> (*problem solved with one coin*) 
             Some 1
      | x -> if x < 0 then 
               (*we don't reach 0, we discard this solution*)
               None
             else
               (*we search the smallest path different to None with the remaining pieces*) 
               optmin (optsucc (loop x)) acc
    in
    (*we call onepiece forall the pieces*)
    List.fold_left onepiece None money_system
  in loop amount

Note : Nous pouvons remarquer que cette procédure peut calculer plusieurs fois le changement défini pour la même valeur. En pratique, l'utilisation de la mémorisation pour éviter ces répétitions conduit à des résultats plus rapides (beaucoup plus rapides).

Problème de sélection d'activité

Le problème

Vous avez un ensemble de choses à faire (activités). Chaque activité a une heure de début et une heure de fin. Vous n'êtes pas autorisé à effectuer plus d'une activité à la fois. Votre tâche consiste à trouver un moyen d'effectuer le maximum d'activités.

Par exemple, supposons que vous ayez une sélection de classes parmi lesquelles choisir.

N'oubliez pas que vous ne pouvez pas suivre deux cours en même temps. Cela signifie que vous ne pouvez pas prendre les classes 1 et 2 car elles partagent un temps commun 10h30 à 11h00. Cependant, vous pouvez prendre les classes 1 et 3 car elles ne partagent pas une heure commune. Ainsi, votre tâche consiste à prendre le plus grand nombre possible de classes sans aucun chevauchement. Comment peux-tu faire ça?

Une analyse

Pensons à la solution par une approche gourmande. Tout d'abord, nous avons choisi au hasard une approche et une vérification qui fonctionneront ou non.

• triez l’activité par heure de début, c’est-à-dire quelle activité commence en premier, nous la prendrons en premier. puis prenez la première de la liste triée et vérifiez qu'elle se recoupe ou non de l'activité précédente. Si l'activité en cours ne recoupe pas l'activité précédemment prise, nous effectuerons l'activité sinon nous ne réaliserons pas. cette approche fonctionnera pour certains cas comme

l'ordre de tri sera 4 -> 1 -> 2 -> 3. L'activité 4 -> 1 -> 3 sera effectuée et l'activité 2 sera ignorée. 3 activités maximum seront effectuées. Cela fonctionne pour ce type de cas. mais cela échouera dans certains cas. Permet d'appliquer cette approche pour le cas

L'ordre de tri sera 4 -> 1 -> 2 -> 3 et seule l'activité 4 sera effectuée mais la réponse peut être l'activité 1 -> 3 ou 2 -> 3 sera effectuée. Donc, notre approche ne fonctionnera pas pour le cas ci-dessus. Essayons une autre approche

• Triez l’activité par durée, c’est-à-dire effectuez d’abord l’activité la plus courte. cela peut résoudre le problème précédent. Bien que le problème ne soit pas complètement résolu. Il y a encore des cas qui peuvent faire échouer la solution. appliquer cette approche sur le cas ci-dessous.

Si nous trions l'activité par durée, l'ordre de tri sera 2 -> 3 ---> 1. et si nous effectuons l'activité n ° 2 en premier, aucune autre activité ne peut être effectuée. Mais la réponse sera effectuer l'activité 1 puis effectuer 3. Donc, nous pouvons effectuer un maximum d'activité 2. Cela ne peut donc pas être une solution à ce problème. Nous devrions essayer une approche différente.

La solution

• Triez l'activité en terminant l'heure, ce qui signifie que l'activité se termine en premier et en premier. l'algorithme est donné ci-dessous

1. Trier les activités par ses heures de fin.
2. Si l'activité à effectuer ne partage pas une heure commune avec les activités effectuées précédemment, effectuez l'activité.

Permet d'analyser le premier exemple

trier l'activité par ses heures de fin, donc l'ordre de tri sera 1 -> 5 -> 2 -> 4 -> 3 .. la réponse est 1 -> 3 ces deux activités seront effectuées. c'est la réponse. voici le code sudo.

1. trier: activités
2. effectuer la première activité à partir de la liste triée d'activités.
3. Set: Current_activity: = première activité
4. set: end_time: = end_time de l'activité en cours
5. aller à l'activité suivante s'il existe, s'il n'existe pas terminer
6. si start_time de l'activité en cours <= end_time: effectue l'activité et passe à 4
7. sinon: a 5.

voir ici pour l'aide au codage http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/