Aller au contenu

Glouton☘

En informatique, un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix local optimum.

Dans certains cas, cette approche permet d'arriver à un optimum global, mais dans le cas général, c'est une heuristique (méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d'optimisation difficile).

Stratégie pour le « Plus Grand Carré Blanc »☘

  1. On commence à parcourir notre image de 1 pixel en 1 pixel, en testant chaque fois, quel est le plus grand carré blanc.

  2. Si on trouve un carré blanc de dimension 2, alors inutile de continuer à parcourir chaque pixel. On saute alors de 2 en 2 et on ne teste qu'à partir de la taille 2.

  3. Si on trouve un carré blanc de dimension 3, alors, on saute de 3 en 3 et on ne teste qu'à partir de la taille 3.

  4. Si on trouve un carré blanc de dimension 4, alors, on saute de 4 en 4...

Discussion☘

Cet algorithme vous semble-t-il optimal, donnera-t-il les bons résultats ?
Est-il rapide ?

Une réponse

L'algorithme glouton ne va pas renvoyer les valeurs optimales car il va sauter certains plus grand carrés blancs. Il est en revanche très rapide puisqu'il va rapidement sauter 2 ou 3 pixels, réduisant ainsi le temps de parcours. Selon l'image, il pourrait renvoyer des réponses optimales...

Implémentation☘

Implémenter cet algorithme dans la fonction recherche_pgcb_glouton(). On pourra notamment jouer sur les pas des boucles for.

1
2
3
4
5
6
7
def recherche_pgcb_glouton(source):
    """
    source - référence d'une image carrée (au format 'L') déjà importée à l'aide de PIL au format 'L'
            La "couleur" d'un pixel noir est 0, celle d'un pixel blanc est 255
    Sortie: list - tableau d'association entre chaque pixel de l'image et la longueur
            du côté du plus grand carré blanc qu'il permet de définir
    """
Un code possible

Ce code est très peu optimal mais très rapide.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def recherche_pgcb_glouton(source):
    """
    source - référence d'une image carrée (au format 'L') déjà importée à l'aide de PIL au format 'L'
            La "couleur" d'un pixel noir est 0, celle d'un pixel blanc est 255
    Sortie: list - tableau d'association entre chaque pixel de l'image et la longueur
            du côté du plus grand carré blanc qu'il permet de définir
    """
    largeur, hauteur = source.size                          # L'image est carrée donc largeur = hauteur
    coordonnees = []
    taille_max = 1
    for y in range(0, hauteur - taille_max, taille_max):
        for x in range(0, largeur - taille_max, taille_max):
            coin = (x,y)
            j = 0
            compte = 0                                      # compteur de pixels noirs
            while compte == 0 and j < taille_max:
                i = 0
                while compte == 0 and i < taille_max:
                    if source.getpixel((x+i,y+j)) != 255:
                        compte += 1
                    i += 1
                j += 1
            if compte == 0:                                 # si que des pixels blanc
                coordonnees.append(coin)
        if len(coordonnees) == 0:                           # Une taille de carrée plus grande ne retourne rien
            return taille_max-1, liste_a_retourner          # Je retourne la liste précédente, décrémenter de 1 à cause de mon passage sans rien trouver à taille_max+1
        else:
            liste_a_retourner = coordonnees                 # Je stocke l'état de coordonnees pour un éventuel return dans la boucle d'après
            taille_max += 1                                 # je passe à la taille à détecter suivante
            coordonnees = []