Maximaler durchschnittlicher Abstand zwischen zwei Zahlen über mehrere Arrays

8

Angenommen, Sie haben kArrays mit einer Größe N, die jeweils eindeutige Werte von 1bis enthalten N.

Wie würden Sie die beiden Zahlen finden, die im Durchschnitt am weitesten voneinander entfernt sind?

Zum Beispiel angesichts der Arrays:

[1,4,2,3]
[4,2,3,1]
[2,3,4,1]

Dann wäre die Antwort item 1und 2, da sie in den ersten beiden Arrays einen Abstand von 2 und im letzten einen Abstand von 3 haben.

Mir ist eine O (kN ^ 2) -Lösung bekannt (durch Messen des Abstands zwischen jedem Zahlenpaar für jedes der kArrays), aber gibt es eine bessere Lösung?

Ich möchte einen solchen Algorithmus in C ++ implementieren, aber jede Beschreibung einer Lösung wäre hilfreich.

arrays algorithm performance Magnus EF
quelle

Antworten:

3

Nach einer linearen Zeittransformation, die die Zahlen indiziert, läuft dieses Problem darauf hinaus, den Durchmesser eines Satzes von Punkten in Bezug auf den L1-Abstand zu berechnen. Leider unterliegt dieses Problem dem Fluch der Dimensionalität.

Gegeben

    1 2 3 4
1: [1,4,2,3]
2: [4,2,3,1]
3: [2,3,4,1]

wir berechnen

    1 2 3
1: [1,4,4]
2: [3,2,1]
3: [4,3,2]
4: [2,1,3]

und dann wird der Abstand zwischen L1 1und 2ist |1-3| + |4-2| + |4-1| = 8, was deren durchschnittliche Abstand (in der Problembedingungen) mal k = 3.

Abgesehen davon können Sie einen ungefähren Algorithmus für den nächsten Nachbarn anwenden, indem Sie die obige Eingabe als Datenbank und das Bild jedes Punkts in der Datenbank N+1-vals Abfrage verwenden.

David Eisenstat
quelle
Diese Referenz schlägt einen randomisierten Algorithmus mit erwarteter linearer Laufzeit vor, der für das OP von Interesse sein kann.
hilberts_drinking_problem
@hilberts_drinking_problem Könnte nützlich sein, aber nur für kleine Dimensionen.
David Eisenstat
Glauben Sie, dass es möglich wäre, dies mit einem heuristischen Ansatz zu kombinieren, der in einer anderen Antwort beschrieben wird?
Magnus EF
@ MagnusE-F Es gibt viele ungefähre Algorithmen für den nächsten Nachbarn. Ich habe meine Antwort dahingehend geändert, wie dieses Problem auf ANN reduziert werden kann.
David Eisenstat
1

Ich habe einen Vorschlag für den besten Fall . Sie können einen heuristischen Ansatz verfolgen.

Zum Beispiel wissen Sie , dass , wenn N=4, N-1=3wird der maximale Abstand sein und 1wird das Minimum sein. Der mittlere Abstand ist 10/6=1,66667 (Summe der Abstände zwischen Paaren innerhalb eines Arrays / Anzahl der Paare innerhalb eines Arrays).

Dann wissen Sie, dass zwei Zahlen, die sich k/2(meistens) an den Rändern von Arrays befinden, bereits im Durchschnitt oben liegen (> = 2Abstand), selbst wenn sie 1in den anderen k/2Arrays nur Abstand voneinander haben . Das könnte eine Lösung für den besten Fall in O(2k)= sein O(k).

samthegolden
quelle
Das scheint ein guter Ansatz zu sein. In meinem Fall ist N viel größer als k und ich denke, ein heuristischer Algorithmus wird gut
Magnus EF
Was ist mit dem schlimmsten Fall dieses Algorithmus? Ist es noch O (k N ^ 2)?
Jérôme Richard
@ JérômeRichard Wir haben den Algorithmus nicht geändert, sondern nur eine Heuristik hinzugefügt, die, falls zutreffend, nur für ein gutes Szenario gilt. Im schlimmsten Fall wird es vom Hauptalgorithmus gelöst.
Samthegolden