Plus grand rectangle de cases blanches dans une grille

  Pour aborder ce sujet, il faut déjà avoir étudié le sujet: grille - Présentation et objectifs, dont on utilise les définitions et certaines des fonctions écrites. On résout ici le problème suivant:
    (1) Trouver le plus grand rectangle de cases blanches contenu dans une grille.
On souhaite que les algorithmes aient une complexité de O ( n 2 ) pour une grille de côté n .

  Pour utiliser les fonctions écrites dans le sujet grille - Présentation et objectifs, qui ont été regroupées dans un fichier appelé par exemple presentation.py, il suffit d'écrire au début du fichier appelé par exemple chemins.py qui regroupera les fonctions du présent sujet:

from presentation import *

  Les fichiers de données sont stockés dans http://www.maths-algo.fr/algo/explorateur.php?dir=exercices/Grilles.

I) Objectifs et cahier des charges

  On rappelle qu'une grille est un tableau carré de cases noires ou blanches, comme une grille de mots croisés. Les cases noires sont interdites et les cases blanches autorisées.
  On cherche le plus grand (en surface) rectangle de cases blanches contenu dans la grille. On veut:
    (1) La surface maximum Smax
    (2) Le nombre de rectangles ayant pour surface Smax, ainsi que leur localisation dans la grille.

  Comme on souhaite que les algorithmes aient une complexité de O ( n 2 ) pour une grille de côté n , on ne peut parcourir chaque case du babyrinthe (pour savoir si elle est noire ou blanche) qu'un nombre maximum constant (indépendant de n ) de fois, l'idéal étant de ne parcourir chaque case qu'une fois.
  Dans un premier temps, on écrit un algorithme "naïf" opérationnel dont on évalue la complexité.

  Pour pouvoir visualiser les plus grands rectangles, on utilisera la fonction affiche_rectangles_grille() donnée dans le TP  grille - Présentation et objectifs. Les rectangles ou carrés [a, b]×[a+xL, b+yL] de plus grande surface seront donc stockés dans la liste solution sous la forme [(a, b), xL, yL].

II) Recherche du plus grand rectangle: algorithme naïf

  La première idée est de parcourir la grille A et, pour chaque case blanche C visitée, de rechercher le plus grand rectangle R dont la case C est un coin déterminé du rectangle, par exemple le coin en haut et à gauche.

  Etant donnée C = (i, j) une case blanche de A, comment calculer le plus grand (en surface) rectangle R de cases blanches dont la case C est le coin en haut et à gauche ? Voilà une suggestion:
    (1) On commence par chercher le plus grand rectangle R du type R = [i,i] × [j, j0]
    (2) Puis à à chercher  le plus grand rectangle R du type R = [i,i+1] × [j, j1]. Noter que j1 ≤ j0
    (3) Puis à à chercher  le plus grand rectangle R du type R = [i,i+2] × [j, j2]. Noter que j2 ≤ j1
    (3) Etc jusqu'à ce que la case A[i1][j] ( avec i1 > i) soit noire ou que l'on soit au bord inférieur de A
A chaque fois que l'on trouve un plus grand rectangle R, il faut "regarder" si on le conserve ou non dans la liste des solutions.    

Q1) Ecrire une fonction plus_grands_rectangles_1(A) calculant et affichant les plus grands rectangles de cases blanches contenus dans la grille A. Votre fonction peut avoir la structure suivante:

def plus_grands_rectangles_1(A):
    """ Plus grands rectangles de cases blanches contenus dans A"""

    def surf(a, b, c, d):
        """ Surface de [a,b] x [c,d]"""
        return (b - a + 1) *(d - c + 1)

    def  rect_maxi(i, j):
        """ Recherche d'éventuels plus grands rectangles de cases blanches de A
         dont C = (i, j) est la case en haut et à gauche."""
# Sous fonction à écrire

# Début de la fonction principale
    liste_rectangles, n, Smax = [], len(A), 0
    for i in range(n):
        for j in range(n):
            rect_maxi(i, j)
# Finalisation
    col = ["blue",  "orange", "green", "red", "yellow", "purple", "brown"]
    nSol = len(liste_rectangles)
    titre = "Il y a {0} rectangles de surface {1}".format(nSol, Smax)
##    return titre
    affiche_rectangles_grille(A, titre, liste_rectangles, col)

Vérifier par exemple que:

plus_grands_rectangles_1(double_diag_grille(10)) →grille_plus_grand_rectangle_1.png

plus_grands_rectangles_1(lire("grille_50.gri")) → grille_plus_grand_rectangle_2.png

Q2) On s'intéresse à la complexité de la fonctionplus_grands_rectangles_1(A). On modifie lègèrement cette fonction de manière à ce qu'elle renvoie le titre sans affichage de la grille.
En faisant des calculs de durées d'exécution ou de manière théorique, prouver que la complexité est en O ( n 4 ) .

III) Recherche du plus grand rectangle: un algorithme performant

  Il faut changer complètement de point de vue pour espérer construire un algorithme en O ( n 2 ) , qui impose de ne parcourir qu'un nombre maximum indépendant de n chaque case du grille A. Voilà ce que l'on propose de mettre en œuvre.

1) La hauteur d'un plus grang rectangle: la liste CB

  Un plus grand rectangle de cases blanches R = [a,b]×[c,d] (entre les lignes a et b et les colonnes c et d) de la grille A vérifie:
    a = 0 (la première ligne de R est la première ligne de A) ou il y a une case noire dans le rectangle [a-1,a-1]×[c,d] (sur la ligne située juste au dessus de R)
  En effet si ce n'était pas le cas le rectangle R' = [a-1,b]×[c,d] serait blanc et plus grand que R.
  On peut en déduire que pour au moins une des cases C  de la ligne du bas du rectangle R (la ligne [b,b]×[c,d]), la hauteur du rectangle R est le nombre maximum de cases blanches situées au dessus de C.
  En conséquence on va parcourir la grille A ligne par ligne en actualisant la liste CB du nombre de cases blanches situées au dessus (au sens large) de la ligne en cours. On cherchera alors R en "traitant" CB.

Par exemple, avec la grille A = grille_plus_grand_rectangle_3.png

A = [[1, 1, 0, 1, 1], [0, 0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1]]
CB = [0] * 5
for L in A:
    actualiser et afficher CB
# renvoie:
[1, 1, 0, 1, 1]
[0, 0, 1, 0, 2]
[1, 1, 0, 1, 3]
[2, 0, 1, 2, 4]
[3, 1, 2, 0, 5]

2) La largeur d'un plus grang rectangle: les listes G et D

  Lors du parcours d'une ligne L[i] = L = [L[0],...,L[n-1]] de la grille A et après avoir actualisé CB, on actualisera les deux listes G (comme gauche) et D (comme droite) qui sont définies de la manière suivante:
  Etant donné k ∈ {0, 1,..., n-1}, ]G[k], D[k][ = ]g, d[  est le plus grand intervalle de ]-1, n[ tel que:
      (1) g < k < d
      (2) ∀ j ∈]g, d[, CB[j] ≥ CB[k]
Alors R = [i-CB[k]+1, i]×[g+1, d-1] sera le plus grand rectangle de cases blanches contenu dans A dont la hauteur en L[k] est CB[k]. Sa surface est S = CB[k]*(d-g+1). Le rectangle champion que l'on cherche est l'un de ces rectangles compte tenu de la première remarque.

Le point crucial est l'actualisation de ces listes G et D lors du parcours de L = L[i], actualisation qui doit être en O ( n ) . Il faut remarquer que seules les cases noires de la ligne L (qui correspondent au zéro de la liste CB) perturbent légèrement les listes G et D. Plus précisément, entre deux cases noires en position n1 et n2 sur la ligne L, alors:
    (1) ∀ k ∈ ]n1, n2[, G[k] = max(G[k], n1)
    (2) ∀ k ∈ ]n1, n2[, D[k] = min(G[k], n1)
Et bien sûr G[n1] = -1 et D[n1] = n, de même pour n2. Il faut traiter également correctement le début et la fin de la ligne.

Q3)  Ecrire une fonction plus_grands_rectangles_2(A) calculant et affichant les plus grands rectangles de cases blanches contenus dans la grille A avec un coût de O ( n 2 ) . Votre fonction peut avoir la structure suivante si vous suivez le plan suggéré:

def plus_grands_rectangles_2(A):
    """ Plus grand rectangle de cases blanches dans A.
    Lors du traitement de la ième ligne L de A,   CB[j] est le nombre de cases
     blanches au dessus de A[i][j].
      Pour l'élément L[k] d'une ligne L de A, ]g, d[ = G[k], D[k][ est le plus
    grand intervalle tel que g < k < d et CB[j] >= CB[k] pour tout j dans ]g, d[.
    Ainsi S = CB[k] * (d - g  + 1) est la surface du plus grand rectangle de
    cases blanches dont la base est la ligne L, et dont la hauteur en k est CB[k]
        """
    def traitement_Smax():
        """ Calcul de surface et MAJ éventuelle de Smax et liste_rectangles"""
        A écrire

    liste_rectangles, n, Smax = [], len(A), 0
    CB, G, D = [0] * n, [-1] * n, [n] * n

    for ligne in range(n):
        L = A[ligne]
        actualiser CB
        actualiser G et D et mettre à jour liste_rectangles

    Eliminer les doublons éventuels de liste_rectangle

# Finalisation
    nSol = len(liste_rectangles_single)
    col = ["blue",  "orange", "green", "red", "yellow", "purple", "brown"]
    titre = "Il y a {0} rectangles de surface {1}".format(nSol, Smax)
    return titre
    affiche_rectangles_grille(A, titre, liste_rectangles_single, col)

Q4) Faire les mêmes tests qu'en Q1), puis d'autres avec les grilles prédéfinis pour valider votre fonction plus_grands_rectangles_2(A).

Q5) On valide expérimentalement le calcul de complexité dans les cas suivants, vérifier que vos réponses sont cohérentes:

# Pour les grilles données
for n in (500, 1000):
    A = lire("grille_{0}.gri".format(n))
    t = time.perf_counter()
    res, t = plus_grands_rectangles_2(A), time.perf_counter() - t
    print("n = {0:4} | Durée = {1:6.3}s ; {2}".format(n, t, res))
# renvoie
n =  500 | Durée =  0.371s ; Il y a 1 rectangles de surface 1591
n = 1000 | Durée =    1.6s ; Il y a 1 rectangles de surface 2325    

# Pour des grilles blanches
for n in (500, 1000, 2000):
    A = blanc_grille(n)
    t = time.perf_counter()
    res, t = plus_grands_rectangles_2(A), time.perf_counter() - t
    print("n = {0:4} | Durée = {1:6.3}s ; {2}".format(n, t, res))
# renvoie
n =  500 | Durée =  0.258s ; Il y a 1 rectangles de surface 250000
n = 1000 | Durée =   1.06s ; Il y a 1 rectangles de surface 1000000
n = 2000 | Durée =   4.29s ; Il y a 1 rectangles de surface 4000000

# Pour des grilles spécifiques
for n in (500, 1000, 2000):
    A = double_diag_grille(n)
    t = time.perf_counter()
    res, t = plus_grands_rectangles_2(A), time.perf_counter() - t
    print("n = {0:4} | Durée = {1:6.3}s ; {2}".format(n, t, res))
# renvoie
n =  500 | Durée =  0.363s ; Il y a 4 rectangles de surface 31250
n = 1000 | Durée =   1.47s ; Il y a 4 rectangles de surface 125000
n = 2000 | Durée =   5.93s ; Il y a 4 rectangles de surface 500000    

# Pour une grille aleatoire
for n in (500, 1000, 2000):
    A = aleatoire_grille(n, 0.978)
    t = time.perf_counter()
    res, t = plus_grands_rectangles_2(A), time.perf_counter() - t
    print("n = {0:4} | Durée = {1:6.3}s ; {2}".format(n, t, res))
# renvoie
n =  500 | Durée =  0.403s ; Il y a 1 rectangles de surface 660
n = 1000 | Durée =   1.66s ; Il y a 1 rectangles de surface 592
n = 2000 | Durée =   6.73s ; Il y a 1 rectangles de surface 729

  Justifier (expérimentalement et théoriquement) que la complexité est bien en O ( n 2 ) .

Q6) Réactiver l'affichage des plus grands rectangles et faites des essais du genre:

n = 150 #ou 100 ou 200 par exemple
A = aleatoire_grille(n, 0.97)# par exemple 0.97
affiche_grille(A)
plus_grands_rectangles_2(A)

  Essayer de deviner où est le plus grand rectangle après affiche_grille(A) et contrôler. Commenter les résultats.

© 2015 - Eric Obermeyer      Powered by      Corrigé