Compter les îles dans les matrices booléennes

Étant donné une matrice booléenne , soit entrées représentent la mer et entrées représentent la terre. Définissez un îlot comme verticalement ou horizontalement (mais pas en diagonale) adjacent entrées. $n \times m$ $\mathrm X$ $0$ $1$ $1$

La question initiale était de compter le nombre d'îles dans une matrice donnée. L'auteur a décrit une solution récursive ( mémoire ). $\mathcal{O}(nm)$

Mais j'essayais en vain de trouver une solution de streaming (de gauche à droite, puis vers le bas à la ligne suivante) qui compte dynamiquement les îles avec ou ou mémoire (il n'y a pas de limite de complexité temporelle). Est-ce possible? Sinon, comment puis-je le prouver? $\mathcal{O}(m)$ $\mathcal{O}(n)$ $\mathcal{O}(n+m)$

Quelques exemples de sorties attendues pour certaines entrées de la countfonction:

$count\begin{pmatrix} 010\\ 111\\ 010\\ \end{pmatrix} = 1; % count\begin{pmatrix} 101\\ 010\\ 101\\ \end{pmatrix} = 5; % count\begin{pmatrix} 111\\ 101\\ 111\\ \end{pmatrix} = 1;$

$count\begin{pmatrix} 1111100\\ 1000101\\ 1010001\\ 1011111\\ \end{pmatrix} = 2$

$count\begin{pmatrix} 101\\ 111\\ \end{pmatrix} = 1$

algorithms matrices counting streaming-algorithm pgs
la source

1. Que voulez-vous dire par "orthogonal"? Voulez-vous dire un composant connecté? 2. Que pouvons-nous supposer sur la façon dont la matrice est stockée? Pouvons-nous supposer qu'il est stocké sur un stockage externe (par exemple, un disque dur lent), afin que vous puissiez lire n'importe quelle partie de votre choix, mais il sera plus rapide de le lire un bloc à la fois? Ou recevons-nous la matrice en mode streaming, où une fois que nous avons reçu un peu de la matrice d'entrée, nous ne pouvons plus jamais voir ce bit d'entrée?

Cool merci. Je vous encourage à modifier la question pour clarifier ces points. Si c'est en streaming, dans quel ordre arrivent les bits de la matrice? Numériser de gauche à droite dans une rangée, puis descendre à la rangée suivante?

Veuillez modifier la question pour inclure tous ces détails. Les commentaires sont éphémères.

Yuval Filmus

Toutes les informations fournies dans les commentaires ne peuvent pas être trouvées dans le message lui-même. Certaines de ces informations sont plutôt cruciales, comme votre modèle de streaming. Les commentaires pourraient disparaître, et donc (et en raison des normes de la communauté), tous les détails requis devraient faire partie du message principal.

Yuval Filmus

Quelle est la complexité temporelle requise?

hengxin

Réponses:

Voici un schéma d'un algorithme qui ne conserve que deux lignes en mémoire à la fois, donc de la mémoire . Mais comme vous pouvez exécuter cet algorithme sur la transposition de la matrice sans problème, la complexité réelle est la mémoire . Le temps de traitement est . $O(m)$ $O(\min(m, n))$ $O(mn)$

Initialisation. Parcourez la première ligne et recherchez toutes les sous-chaînes connectées de cette ligne. Attribuez à chaque sous-chaîne disjointe un identifiant positif unique et enregistrez-le en tant que vecteur nul où est nul et identifiant positif unique sinon. $X$
Pour chaque ligne restante, attribuez des ID uniques (ne réattribuez jamais les ID uniques précédents, assurez-vous que vos ID augmentent strictement) aux sous-chaînes de cette ligne. Affichez la ligne précédente plus la ligne actuelle sous la forme d'une matrice de par , et toutes les zones connectées doivent être affectées à leur minimum. Par exemple: $2$ $m$

$\begin{matrix} 010402220333300 \\ 506607080009990 \end{matrix} \to \begin{matrix} 010402220333300 \\ 504402020003330 \end{matrix}$ $\begin{array}0010402220333300\\ 506607080009990\end{array} \rightarrow \begin{array}0010402220333300\\ 504402020003330\end{array}$
Il n'est pas nécessaire de mettre à jour la ligne précédente pour l'exactitude de cet algorithme, seul celui en cours.

Après cela, recherchez l'ensemble de tous les identifiants de la ligne précédente qui ne se connectent pas à la ligne suivante, en supprimant les doublons . Ajoutez la taille de cet ensemble à votre compteur d'îles en cours d'exécution.

Vous pouvez maintenant supprimer la ligne précédente et affecter la ligne actuelle à la ligne précédente et continuer.
Pour gérer correctement la dernière ligne, faites comme s'il y avait une autre ligne de zéros au bas de et exécutez à nouveau l'étape 2. $X$

orlp
la source

Orlp donne une solution en utilisant mots d'espace, qui sont bits d'espace (en supposant pour simplifier que ). Inversement, il est facile de montrer que bits d'espace sont nécessaires en réduisant la disjonction d'ensemble à votre problème. $O(n)$ $O(n\log n)$ $n=m$ $\Omega(n)$

$x_1,\ldots,x_n$ $y_1,\ldots,y_n$ $i$ $x_i=y_i=1$ $2\times(2n-1)$ $x_1,0,x_2,0,\ldots,0,x_n$ $y_1,0,y_2,0,\ldots,0,y_n$ $\sum_i x_i$ $\sum_i (x_i+y_i)$ $i$ $\Omega(n)$ $\Omega(n)$

$O(n)$ $O(\log n)$ $O(n)$

Yuval Filmus
la source