Programmation dynamique - Bloc carré le plus grand

Question

J'ai besoin de trouver le plus grand carré de 1 est dans un gigantesque fichier complet de 1 et de 0. Je sais que je dois utiliser la programmation dynamique. Je suis le stocker dans un tableau 2D. L'aide de l'algorithme pour trouver la plus grande place serait génial, merci!

exemple d'entrée:

1 0 1 0 1 0
1 0 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 1
1 1 1 1 1 1

réponse:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Mon code pour l'instant:

int Square (Sq[int x][int y]) {
   if (Sq[x][y]) == 0) {
       return 0;
   }
   else {
       return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
   }
}

(en supposant que les valeurs déjà saisies dans le tableau)

int main() {
    int Sq[5][6]; //5,6 = bottom right conner
    int X = Square(Sq[5][6]);
}

Comment allez-vous à partir de là?

Answer 1

Voici une esquisse de la solution:

Pour chacune des cellules, nous allons garder un compteur de savoir comment grand d'un carré peut être faite à l'aide de la cellule en haut à gauche. Évidemment, toutes les cellules avec 0 a 0 comme le nombre de.

Commencer à parcourir par le bas à droite de la cellule et aller en bas à gauche, puis aller à une ligne et la répétition.

À chaque scan ce faire:

1. Si la cellule a 0 attribuer count=0
2. Si la cellule a 1 et a un bord de la cellule (en bas ou à droite uniquement), affecter count=1
3. Pour toutes les autres cellules, vérifier le décompte de la cellule sur sa droite, de droite ci-dessous et ci-dessous. Prendre le min de et ajouter 1 et affectez-le à la nombre de. Garder un mondial max_count variable pour suivre le compte maximum jusqu'à présent.

À la fin de la traversée de la matrice, max_count aura la valeur souhaitée.

La complexité n'est pas plus que le coût de la traversée de la matrice.

C'est la façon dont la matrice après la traversée. Les valeurs entre parenthèses sont les chiffres, c'est à dire plus grand carré qui peut être fait à l'aide de la cellule en haut à gauche.

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Mise en œuvre en Python

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)

Answer 2

LSBRA(X,Y) signifie "Grand Carré avec Fond-Droit À X,Y"

Pseudo-code:

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

(Pour la bordure des cellules, vous pouvez sauter la partie MIN et il suffit de retourner 1 si (x,y) n'est pas 0.)

Travail en diagonale à travers la grille en "vagues", comme suit:

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

ou sinon, le travail par le biais de gauche à droite, de haut en bas, aussi longtemps que vous remplissez en bord de cellules.

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

De cette façon, vous ne serez jamais à court dans un calcul où l'on n'a pas calculé les données nécessaires - ce qui fait que le LSBRA() "appels" sont en fait juste la table des recherches de vos précédents résultats de calcul (d'où la programmation dynamique aspect).

Pourquoi cela fonctionne

Afin d'avoir un carré avec un bas-droit à X,Y, - elle doit contenir les carrés qui se chevauchent d'une moindre dimension qui touche chacun des 3 autres coins. En d'autres termes, d'avoir

XXXX
XXXX
XXXX
XXXX

vous devez également avoir...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

Tant que vous avez ces 3 (chaque LSBRA contrôles) N-taille places en plus de la case courante est également "occupé", vous aurez une (N+1)-la taille du carré.

Answer 3

Le premier algorithme qui me vient à l'esprit est:

1. '&&' colonne/ligne 1 colonne/ligne 2 si, c'est-à-dire faire une "& & ' opération entre chaque entrée et son entrée correspondante dans l'autre colonne/rangée.
2. Vérifiez la colonne résultante, si il y a n'importe quelle longueur de 2 à 1 cela signifie que nous avons touché un carré 2x2.
3. Et la prochaine colonne avec le résultat des deux premières. Si il y a n'importe quelle longueur 3 1 nous avons frappé un carré de 3x3 cases.
4. Répétez jusqu'à ce que toutes les colonnes ont été utilisées.
5. Répéter 1 à 4 de départ à la colonne 2.

Je ne vais pas vous montrer la mise en œuvre de ses assez simple et votre problème de sons comme des devoirs. En outre, il y a probablement beaucoup plus efficace façons de le faire, car cela va devenir lent si l'entrée était très grande.

Answer 4

Laissez entrer la matrice est - M: n x m

T[i][j] DP est la matrice qui contient la plus grande place du côté de carrés en bas à droite de l'angle (i,j).

Règle générale, pour remplir la table:

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

Le résultat de la taille des carrés est la valeur max. en T.

De remplissage en T[i][0] et T[0][j] est trivial.

Je ne suis pas sûr si cette algo peut être utilisé pour votre énorme fichier, mais vous n'avez pas besoin de stocker l'ensemble de la matrice T , mais seulement en cours et le précédent lignes seulement.

Notes suivantes peuvent aider à comprendre idée générale:

• tous les carrés à droite en bas angles (i-1, j), (i, j-1), (i-1, j-1) taille s sont à l'intérieur de place de avec en bas à droite de l'angle (i, j) de taille s+1.
• si il y a carré de la taille s+1 avec coin en bas à droite (i, j), puis la taille maximale de la square avec de la, droite, bas angles (i-1, j), (i, j-1), (i-1, j-1) est d'au moins s.
• Inverse est également vrai. Si la taille d'au moins un carré avec en bas à angle droit par rapport à (i-1, j), (i, j-1), (i-1, j-1) est inférieur à s, alors la taille de carré avec coin en bas à droite (i, j) ne peut pas être plus grand que s+1.

Answer 5

OK, la façon la plus inefficace mais simple serait:

1. sélectionner le premier élément. vérifiez si 1, si vous avez un carré de 1x1.

2. cocher une case ci-dessous et un de droite, si 1, puis cochez la ligne 2 col 2, si 1, 2x2 carrés.

3. vérifiez la ligne 3 col 1 col 2 et col 3, plus la ligne 1 col 3, ligne 2 col 3, si 1, 3x3.

4. Donc, fondamentalement, vous gardez l'expansion de la ligne et le col, vérifiez toutes les cellules à l'intérieur de leurs frontières. Dès que vous frappez un 0, il est cassé, de sorte que vous vous déplacez le long de 1 point dans une rangée, et recommencer.

5. À la fin de la ligne, passez à la ligne suivante.

6. jusqu'à la fin.

Vous pouvez probablement voir comment ils s'insèrent dans les boucles while, etc, et comment &&s peut être utilisé pour vérifier les 0, et que vous le regardez, vous aurez peut-être également remarqué comment il peut être accéléré. Mais comme l'autre réponse vient d'être mentionné, il ne sembler un peu comme des devoirs, donc nous allons laisser le code jusqu'à vous.

Bonne chance!