reperage d'île - Page 2

NP est une classe plus large que NP-complet... tous les problèmes polynomiaux (déterministes) sont dans NP, mais ne sont (si P!=NP) pas NP-complets.

Par contre effectivement je pense pas qu'on ait mieux que des *algorithmes* exponentiels pour des *problèmes* NP (sinon on aurait prouvé que NP est inclus strictement dans EXP, ce qui n'est pas prouvé je crois [je suis pas sûr là, qqun pour confirmer ?]). Enfin, exponentiels dans le pire des cas en tout cas : il peut y avoir plein de réductions qui marchent dans 99% des cas ^^

Onur :
les posts de Pollux, ca sent les études d'ingénieur

Faut pas déconner hein

Sinon je sais pas si ma solution est meilleure que celle citée plus haut, mais moi j'aurais fait (pour k colonnes) :

Je parcours mon fichier de manière linéaire, après avoir viré les \n, remplacé les . par des -2 et les X par des -1
Si je rencontre un -1 en position t :
Je regarde à gauche (t-1) et en haut (t-k).
* Si les deux valent -2, je met t en position t.
* Si t-k vaut un entier positif, je met t-k en position t.
* Si t-1 vaut un entier positif, je met t-1 en position t.
* Si t-k et t-1 valent un entier positif, je met t-k en position t et en position t-1.
Quand j'ai fini je refais une passe :
* Si je tombe sur un -2, je met un .
* Si je tombe sur t en position t, je met le premier entier strictement positif encore inutilisé.
* Si je tombe sur n<>t en position t, je met ce qu'il y a en n en t.
J'outputte.

Voila, je récurse pas, mais je sais pas si c'est plus rapide, par contre.

Ben ça a l'unique avantage de nécessiter 2 tests au lieu de 3 à chaque itération... Et si c'est la récursivité qui te gêne, ben tu peux facilement transformer l'algo trivial en truc itératif avec une pile... Ca apporte qqch si les "cases" de ton tableaux sont assez grandes pour stocker un index (et dans ce cas-là tu peux traiter sur place, c'est très bien), mais pour un bitmap de 640x480 ça va te bouffer plus d'1 Mo par exemple. Et la mémoire nécessaire est tjs maximale (alors qu'avec l'algo "récursif" trivial la pile est en O(taille_plus_grande_composante*ln(n)), ce qui est bien si t'as plein de blancs)

Ce que j'avais en tête, c'est que si on a une forme assez "simple", ça va être une union de N objets convexes (avec N assez faible). Donc si tu prends le graphe défini sur l'ensemble des pixels G(p,p') ssi p est l'un des 4 voisins de p' et p et p' sont tous les deux un 'X', alors en prenant G' = G/R_h/R_h/.../R_h avec p R_h p' ssi p et p' sont voisins horizontalement, G' est une ligne droite (un arbre 1-aire, quoi) si la forme est convexe, et dans le cas général G'(y) = {ensemble des éléments de G d'ordonnée y} a au plus N éléments. Alors G' a au plus N*sqrt(n) arêtes (en supposant que le truc est orienté pour que Y<=X), donc on peut calculer la composante connexe d'un point en O(N*sqrt(n)*ln(n)) en mémoire et en temps (avec le même algo d'exploration récursive/pseudo-récursive déjà donné, mais appliqué à G' et pas à G).
Ca fait donc, avec le calcul de G', du O(n) en temps et du O(N*sqrt(n)*ln(n)) en espace, ce qui est déjà mieux (et en pratique, j'ai essayé sur une capture d'écran 1280x1024 convertie en noir&blanc et avec un paquet d'îles, ça demande à peine plus de sqrt(n)*ln(n))

Pollux :
NP est une classe plus large que NP-complet... tous les problèmes polynomiaux (déterministes) sont dans NP, mais ne sont (si P!=NP) pas NP-complets.

Par contre effectivement je pense pas qu'on ait mieux que des *algorithmes* exponentiels pour des *problèmes* NP (sinon on aurait prouvé que NP est inclus strictement dans EXP, ce qui n'est pas prouvé je crois [je suis pas sûr là, qqun pour confirmer ?]). Enfin, exponentiels dans le pire des cas en tout cas : il peut y avoir plein de réductions qui marchent dans 99% des cas ^^

De ce que j'ai lu, c'est souvent en se contentant d'approximations que l'on arrive à réduire la complexité des algo exponentiels ...

Pollux > Tu peux détailler un peu le calcul des composantes connexes de G' avec l'algo déjà donné ? J'ai l'impression qu'il me manque pas grand chose pour comprendre, mais j'ai pas compris

Ben c'est juste que si tu peux avoir la liste des voisins d'un noeud, alors tu peux faire explore(noeud) = if (!noeud.painted) { paint(noeud); foreach(v in noeud.voisins) explore(v); }

J'ai l'impression que c'est le même genre d'algo que pour le démineur quand tu choisis une case vide.

C'est le même algo.

C'est du remplissage quoi, avec quelques subtilités. J'ai un truc du genre dans Seven Tiles aussi.

ceci etant dit avant de lancer la dicho il faut bien savoir ou sont les iles pour etre assez performant

j'ai fait ca aussi, le remplissage, quand il a fallu faire un utilitaire style paint.