Algorithme glouton python – Exemple rendu de monnaie

Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c’est le cas.

Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c'est le cas.

Algorithme glouton : Introduction

Le problème du rendu de monnaie est formulé de la façon suivante. Comment rendre une somme donnée avec un minimum de pièces et billets  ?

Voici un exemple en python de la résolution du problème :

Si on considère le système monétaire Euro sans les centimes on a l’ensemble

EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)

Algorithme glouton rendu de monnaie python

Maintenant, pour rendre la monnaie sur une valeur x de en utilisant ces pièces et billets, alors nous vérifierons le premier élément du tableau. Et si il est supérieur à x, nous passons à l’élément suivant. Sinon le gardons. Maintenant, après avoir pris une pièce ou un billet de valeur issu du tableau de pieceEtBillet [i], la valeur totale x que nous devons faire deviendra x – pieceEtBillet [i].

Voici l’algorithme glouton python associé :

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(33)#Exemple sur 33 euros

La sortie pour 33 euro est alors :

20
10
2
1

Autre exemple avec 55 euro d’algorithme glouton python :

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(55)#Exemple sur 55 euros

La sortie est alors :

50
5

Conclusion

Le problème du rendu de monnaie est NP-difficile relativement au nombre de pièce et billet du système monétaire considéré (euro dans cet exemple). Pour aller plus loin on pourra démontrer que pour certains systèmes de monnaie dits canoniques, l’utilisation d’un algorithme glouton est optimal. Un système monétaire est dit canonique si pour toute somme s l’algorithme glouton conduit à une décomposition minimale.

La difficulté NP est la propriété déterminante d’une classe de problèmes informellement « au moins aussi difficiles que les problèmes les plus difficiles de NP ».

Un exemple simple de problème NP-hard est le problème de somme de sous-ensembles. Si P est différent de NP alors il est peu probable de trouver un algorithme en temps polynomial qui résout de façon exact ce problème.

Liens externes

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Liens internes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/non-classe/

Implémentation Python de l’algorithme de Dijkstra

Cet article fait suite à l’article suivant sur l’algorithme de Dijkstra : http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Voici l’implémentation Python de l’algorithme

from collections import deque

def dijkstra(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    while queue:
        t = queue.popleft()
        print("On visite le sommet " + str(t))
        for voisin in graph[t]:
                queue.append(voisin)
                nouvelle_distance = distance[t] + graph[t][voisin]
                if(voisin not in distance or nouvelle_distance < distance[voisin]):
                    distance[voisin] = nouvelle_distance
                    print("Met à jour le sommet " + str(voisin) + " avec la distance : " + str(nouvelle_distance))
                    
    return distance



#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distance = dijkstra(graph,'A')
print("Distances" + str(distance))

Glossaire sur les graphes en un peu plus de 128 mots

source wikipedia : Graphe non orienté

Graphe (Graph) : Un ensemble de point reliés entre eux

Sommets (vertices, a vertex) : Les points d’un graphe s’appellent des sommets
Sommets adjacents (adjacent vertices) : Deux sommets sont adjacents si ils sont reliés entre eux
Arête (edge) : La liaison entre deux sommets s’appelle une arête si la relation entre deux sommet n’est pas orientée (pas de notion de précédence, ou d’ordre dans lequel on visite les deux sommets).

source wikipedia : graphe orienté


Arc (arc): La liaison orientée entre deux sommet (c’est une flèche qui indique le sens de la relation orientée, il y a une notion d’ordre d’exécution et de contrainte pour visiter les deux sommets)
Le degré d’un sommet (the degree of a vertex) : Nombre d’arêtes qui partent d’un sommet.
Ordre d’un graphe (order of a graph) : Le nombre de sommet dans un graphe.
Graphe Connexe (connected graph) : Un graphe est connexe si tous les sommets sont reliés par une chaine quelconque.
Chaine Eulerienne (eulerian path) : Une chaine qui prend toutes les arêtes une seule fois du graphe.


Matrice d’adjacente : La matrice d’adjacence d’un graphe est une matrice dont les lignes et les colonnes sont toutes deux indexées par les sommets du graphe, avec un 1 dans la cellule pour la rangée i et la colonne j lorsque les sommets i et j sont adjacents, et un 0 sinon.

source wikipedia : matrice d’adjacence