Discussion :

[bafman]

bonjour,

pour un projet, j'ai besoin de decouper une matrice de case de type differents en sous carré de même type. le but etant de realiser un graph de zones connexes servant pour hierarchiser un algo de pathfinding.

pour cela nous avons realiser une version simple de qui consiste en gros a faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
pour chaque case de la matrice
    on crée un carré d'1 case
    tantque on peut construire un carré valide
        on agrandit le carré
    fintantQue
finpour

en considerant qu'un carré est valide quand il ne contient que des cases du même type et non deja utilisée dans un autre carré.

le probleme est que des que le contenu de la matrice se complexifie, on se retouve avec un graphe de voisinage qui ne contient quasiment que des carré de la taille d'une case... bref on en revient presque à la matrice, ce qui fait perdre tout l'interet de la hierarchie du pathfinder...

etant donné qu'on utilise ici un algo glouton qui est loins de nous donner une solution optimal en terme de nombre de case dans le graph, si vous pouviez m'indiquer comment approcher de l'optimalitée (en nombre de sous carré)
en fait on ne cheche pas forcement l'optimalitée mais une approche, etant donnée qu'on souhaite un algorithme "relativement" rapide, etant donné que le temps d'analyse d'une carte est deja tres long a cause d'autres analyse effectuée dessus et j'ai bien peur de ne voir de solution que par essais succecifs...

[FrancisSourd]

L'heuristique gloutonne pourrait commencer par rechercher un gros carré afin d'empêcher que la création d'un tel gros carré soit empêchée par la création préalable d'un petit carré voisin.

As-tu un exemple où ton heuristique donne manifeste nettement plus mauvaise que l'optimum? Sinon, on peut supposer que la création de nombreux petits carrés est due à la nature "morcelée de ton entrée"...

[Jean-Marc.Bourguet]

L'heuristique gloutonne pourrait commencer par rechercher un gros carré afin d'empêcher que la création d'un tel gros carré soit empêchée par la création préalable d'un petit carré voisin.

Il y a un algorithme pour trouver le plus gros carre en ne faisant qu'une passe sur la matrice et en employant un tableau dont la dimention est le plus petit cote de la matrice.

[bafman]

L'heuristique gloutonne pourrait commencer par rechercher un gros carré afin d'empêcher que la création d'un tel gros carré soit empêchée par la création préalable d'un petit carré voisin.

effectivement, c'est ce qu'il me fallait... en effectuant une passe qui recherche le plus gros sous carré de la matrice et en le bloquant on ameliore sensiblement le resultat (et la complexitée en même temps... on passe de O(n) a O(n²) )

[Trap D]

effectivement, c'est ce qu'il me fallait... en effectuant une passe qui recherche le plus gros sous carré de la matrice et en le bloquant on ameliore sensiblement le resultat (et la complexitée en même temps... on passe de O(n) a O(n²) )

A prendre au second degré, n'est-ce-pas ?

[Jean-Marc.Bourguet]

L'heuristique gloutonne pourrait commencer par rechercher un gros carré afin d'empêcher que la création d'un tel gros carré soit empêchée par la création préalable d'un petit carré voisin.

effectivement, c'est ce qu'il me fallait... en effectuant une passe qui recherche le plus gros sous carré de la matrice et en le bloquant on ameliore sensiblement le resultat (et la complexitée en même temps... on passe de O(n) a O(n²) )

On peut trouver le plus gros carre dans une matrice de bits en un temps proportionnel au nombre d'elements dans la matrice.

[bafman]

oui, c'est ca que je fait... mais etant donné que je veut trouver tout les sous carré, ca me donne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
// on parcourt la matrice :
tant que la matrice n'est pas entierement decoupé :
    on recupere le plus grand sous carré // complexité lineaire
    on le "bloc", il ne sera plus pris en compte pour les prochaines iteration
fin tant que

on a donc une complexité en O(N²)

[FrancisSourd]

Pour rester en O(N), on peut faire une nombre constant (disons 10) passe où on ajoute le plus gros carré puis tu termines avec ton algo initial en O(N).

Tu peux aussi ajouter d'un seul coup plusieurs gros carrés distincts que tu as pu trouvé dans la programmation dynamique (j'imagine que tu utilises la programmation dynamique pour trouver le plus gros carré).

[Jean-Marc.Bourguet]

Tu peux aussi arreter de chercher le plus grand quand il est sous une taille donnee (deja sans perte de generalite, si le plus grand est de taille 1, c'est evident que c'est inutile de faire plusieurs recherches, s'il est de taille 2, la passe d'apres tu peux prendre un carre des qu'il est de taille 2 sans perte de qualite egalement) .

Si tu acceptes de prendre plus de place en memoire, tu ne fais qu'une passe dans laquelle tu stockes pour chaque element de ta matrice le carre le plus grand ayant cet element comme coin inferieur droit (c'est immediat avec l'algo de programmation dynamique auquel je pensais) ce qu tu mets dans une file a priorite. Une fois ta passe faite, tu enleves les elements de ta file par ordre descendant. Pour chaque element, tu regardes si le carre est toujours valable. S'il l'est tu l'ajoute dans ta partition, tu mets tous les elements qui le compose a 0 pour pouvoir faire le test de validite par la suite. S'il ne l'est pas parce que l'element a ete mis a 0, tu l'oublies. S'il ne l'est pas parce qu'un autre element a ete mis a 0, tu peux trouver le nouveau carre maximal et tu le reinsere dans ta file.

Une borne superieure de la complexite est N sqrt N log N si le nombre d'elements dans ta matrice est N.