Ich frage mich, ob es einen Algorithmus gibt, um effizient zu berechnen eine diskrete 1-dimensionale Minkowski-Summe. Die Minkowski-Summe ist definiert als:
%Vor%Könnte es sein, dass wir die Mengen als Listen darstellen können, sortieren wir S und T und dann tue etwas Ähnliches wie die Vereinigung zweier Sätze zu berechnen. d.h. gehen Entlang der Sets parallel und erzeugen das Ergebnis.
Gibt es solche Algorithmen, bei denen ich nicht zusätzlich sortieren muss? Ergebnis, um überlappende Fälle zu entfernen x1 + y1 = x2 + y2? Vorzugsweise in Java formuliert?
Erstens kann die Größe der Ausgabe O(nm) sein, wenn keine Kollisionen auftreten (zB A={0, 1, 2, ..., n-1} , B={n, 2*n, 3*n, ...n*n} ). Wenn wir also von n und m abhängen, haben wir keine Hoffnung der Suche nach einem sub-quadratischen Algorithmus.
Eine einfache Methode ist die Berechnung aller Paare ( O(nm) ), Sortierung und Eindeutigkeit (insgesamt O(nm log nm) .
Wenn Sie eine Obergrenze haben M so dass x <= M für alle x in A union B , können wir die Summe in O(M log M) auf die folgende Weise berechnen.
Generieren Sie die Merkmalsvektoren A[i] = 1 ff i \in A, 0 otherwise und ähnlich für B . Jeder dieser Vektoren hat die Größe M .
Berechnen Sie die Faltung von A und B mit FFT (Zeit: O(M log M) ). Die Ausgabegröße ist O ( M ).
O - O[i] ist bei jeder Zelle ungleich Null, wenn i ein Element der Minkowski-Summe ist. Beweis: O[i] != 0 wenn k existiert so dass A[k] != 0 und B[i-k] != 0 , wenn k \in A und i-k \in B , wenn k + i-k , das ist i , ist in der Minkowski Summe.
(Aus diesem Papier )
Sortiere S und T, iteriere über S nach passenden Elementen in T, jedes Mal, wenn du eine Übereinstimmung findest, entferne das Element von S und T und lege es in einen neuen Satz U. Weil sie sortiert sind, sobald du eine Übereinstimmung gefunden hast in T können weitere Vergleiche in T von der letzten Übereinstimmung ausgehen.
Jetzt sind S, T und U alle disjunkt. Iterieren Sie also über S und T und fügen Sie S, U, T und U hinzu. Schließlich iterieren Sie über U und fügen jedes Element in U durch jedes Element in U hinzu, dessen Index gleich oder größer als der aktuelle Index ist.
Leider ist der Algorithmus bei dieser Optimierung immer noch O (n ^ 2). Wenn T und S identisch sind, ist es 2x schneller als die naive Lösung. Sie müssen auch nicht im Ausgabesatz nach Duplikaten suchen.