Inseln zählen in Booleschen Matrizen

9

Bei einer n×m Booleschen Matrix X sollen 0 Einträge das Meer und 1 Einträge das Land darstellen. Definieren Sie eine Insel als vertikal oder horizontal (aber nicht diagonal) neben 1 Einträgen.

Die ursprüngliche Frage war, die Anzahl der Inseln in einer bestimmten Matrix zu zählen. Der Autor beschrieb eine rekursive Lösung ( O(nm) Speicher).

Ich habe jedoch erfolglos versucht, eine Streaming-Lösung (von links nach rechts und dann bis zur nächsten Zeile) zu finden, die Inseln mit O(m) oder O(n) oder O(n+m) Speicher dynamisch zählt (es gibt keine Grenzen) für die zeitliche Komplexität). Ist das möglich? Wenn nicht, wie kann ich das beweisen?


Einige Beispiele für erwartete Ausgaben für bestimmte Eingaben für die countFunktion:

count(010111010)=1;count(101010101)=5;count(111101111)=1;

count(1111100100010110100011011111)=2

count(101111)=1

pgs
quelle
1
1. Was meinst du mit "orthogonal"? Meinen Sie eine verbundene Komponente? 2. Was können wir über die Speicherung der Matrix annehmen? Können wir davon ausgehen, dass es auf einem externen Speicher (z. B. einer langsamen Festplatte) gespeichert ist, sodass Sie jeden gewünschten Teil lesen können, es jedoch schneller ist, ihn blockweise zu lesen? Oder empfangen wir die Matrix in einer Streaming-Weise, bei der wir, sobald wir ein Stück der Eingabematrix erhalten haben, dieses Stück der Eingabe nie wieder sehen können?
DW
1
Cool, danke. Ich ermutige Sie, die Frage zu bearbeiten, um diese Punkte zu klären. In welcher Reihenfolge kommen die Bits der Matrix beim Streaming an? Zwischen einer Reihe von links nach rechts scannen und dann zur nächsten Reihe hinunter?
DW
1
Bitte bearbeiten Sie die Frage, um alle diese Details aufzunehmen. Kommentare sind kurzlebig.
Yuval Filmus
2
Nicht alle Informationen in den Kommentaren finden Sie im Beitrag selbst. Einige dieser Informationen sind sehr wichtig, wie z. B. Ihr Streaming-Modell. Kommentare könnten verschwinden, und daher sollten (und aufgrund von Community-Standards) alle erforderlichen Details Teil des Hauptpostens sein.
Yuval Filmus
1
Was ist die erforderliche zeitliche Komplexität?
Hengxin

Antworten:

4

O(m)O(min(m,n))O(mn)

  1. X

  2. Weisen Sie für jede verbleibende Zeile den Teilzeichenfolgen in dieser Zeile erneut eindeutige IDs zu (weisen Sie niemals zuvor eindeutige IDs zu, stellen Sie sicher, dass Ihre IDs streng ansteigen). Zeigen Sie die vorherige Zeile plus die aktuelle Zeile als x Matrix an, und alle verbundenen Bereiche sollten ihrem Minimum zugewiesen werden. Als Beispiel:2m

    010402220333300506607080009990010402220333300504402020003330

    There's no need to update the previous row for the correctness of this algorithm, only current one.

    After that's done, find the set of all ids in the previous row that do not connect to the next row, discarding duplicates. Add the size of this set to your running counter of islands.

    You can now discard the previous row and assign the current row to the previous row and move on.

  3. To correctly handle the last row pretend there is another row of zeros at the bottom of X and run step 2 again.

orlp
quelle
6

Orlp gives a solution using O(n) words of space, which are O(nlogn) bits of space (assuming for simplicity that n=m). Conversely, it is easy to show that Ω(n) bits of space are needed by reducing set disjointness to your problem.

Suppose that Alice holds a binary vector x1,,xn and Bob holds a binary vector y1,,yn, and they want to know whether there exists an index i such that xi=yi=1. They run your algorithm for the 2×(2n1) matrix whose rows are x1,0,x2,0,,0,xn and y1,0,y2,0,,0,yn. After the first row is read, Alice sends Bob ixi as well as the memory contents, so that Bob can complete the algorithm and compare i(xi+yi) to the number of connected components. If the two numbers match, the two vectors are disjoint (there is no index i), and vice versa. Since any protocol for set disjointness needs Ω(n) bits (even if it can err with a small constant probability), we deduce an Ω(n) lower bound, which holds even for randomized protocols which are allowed to err with some small constant probability.

We can improve on Orlp's solution by using noncrossing partitions. We read the matrix row by row. For each row, we remember which 1s are connected via paths going through preceding rows. The corresponding partition is noncrossing, and so can be encoded using O(n) bits (since noncrossing partitions are counted by Catalan numbers, whose growth rate is exponential rather than factorial). When reading the following row, we maintain this representing, and increase a counter whenever all ends of some part are not connected to the current row (the counter takes an additional O(logn) bits). As in Orlp's solution, we add a final dummy row of zeroes to finish processing the matrix. This solution uses O(n) bits, which is asymptotically optimal given our lower bound.

Yuval Filmus
quelle