Ermitteln höherer Werte von Arrays, die alle näher als vordefinierte Entfernungen sind

Question

Ermitteln höherer Werte von Arrays, die alle näher als vordefinierte Entfernungen sind

8

Ich habe Arrays a ₁ zu einem _n jeweils mit m Anzahl von Elementen. Ich habe eine andere symmetrische n X n Matrix b , die den Abstand zwischen den Arrays enthält. Ich möchte ein Element aus jedem Array x _{1 bis x auswählen, das auf die folgende Beschränkung beschränkt ist. (a ₁ ist ein Array und x <1> ein einzelner Wert, der von einem ₁}

genommen wird)

Für jedes x _i (das ursprünglich ein _iu war) und x _j (das ursprünglich ein _jv war) >), wobei i nicht dasselbe ist wie j und u und v die ursprünglichen Array-Indizes sind, haben wir | u - v | & lt; = b _ij.
Die Gesamtsumme von x1 bis xn ist das Maximum aller möglichen derartigen Mengen.

Ein Beispiel

%Vor%

Die ausgewählten Werte sind x _{1 <8 und x 2> 4. Man kann feststellen, dass wir nicht 10 oder 11 von der zweiten Auswahl ausgewählt haben, weil sie so nah wie möglich sind Wert für jede von ihnen ist nur 0.}

Jetzt, wenn ich nur zwei Arrays habe, kann ich folgendes in Java in O (n ²) Zeit machen, denke ich und finde die maximale Summe, die 12 in diesem Fall. Wie kann ich eine bessere Lösung für mehr als 2 Arrays erreichen?

%Vor%

algorithm java arrays

besabestin 14.12.2017, 14:13

quelle

1 Antwort

Tags und Links algorithm java arrays

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Alle npm-Befehle geben den gleichen Fehler (ENOENT)

score 2 · Answer 1

Sie können hier keine dynamische Programmierung verwenden, weil es keine optimale Unterstruktur gibt: Der Eintrag b_1n kann einen sehr wertvollen Pfad von x_1 nach x_ {n-1} ruinieren. Daher ist es wahrscheinlich schwierig, die exponentielle Zeit im Allgemeinen zu vermeiden. Für eine Reihe von b_ij, die die Auswahl vernünftigerweise einschränken, gibt es jedoch einen direkten Backtracking-Ansatz, der eine angemessene Leistung haben sollte:

Bei jedem Schritt wurde ein Wert aus einigen der a_i ausgewählt, aber von den anderen wurde noch keine Auswahl getroffen. (Die ausgewählten Arrays müssen kein Präfix der Liste oder sogar zusammenhängend sein.)
Wenn für jedes Array eine Auswahl getroffen wurde, geben Sie (von diesem rekursiven Aufruf) die erhaltene Punktzahl zurück.
Betrachte für jedes Paar eines ausgewählten Arrays und eines verbleibenden Arrays das Intervall von Indizes, die in letzterem zur Auswahl stehen, wobei die Entfernung von der Auswahl, die in ersterem getroffen wird, eingeschränkt ist.
Schneiden Sie diese Intervalle für jedes verbleibende Array durch. Wenn eine Kreuzung leer ist, lehnen Sie diese vorgeschlagenen Auswahlmöglichkeiten ab und fahren Sie zurück.
Wählen Sie andernfalls das verbleibende Array mit den kleinsten verfügbaren Auswahlmöglichkeiten aus. Fügen Sie jede Auswahl zu den vorgeschlagenen Auswahlmöglichkeiten hinzu und rekrutieren Sie. Gebe die beste gefundene Punktzahl und die getroffene Wahl zurück, um sie zu erhalten, falls vorhanden, oder lehne sie ab und verfolge sie.

Die Identifizierung der am stärksten eingeschränkten Anordnung ist für die Leistung entscheidend: Sie stellt eine Form der Fuzzy-Glaubenspropagation dar, die künftige Entscheidungen inkompatibel mit gegenwärtigen Entscheidungen, die durch vorherige Entscheidungen notwendig sind, einschränkt. Abhängig von der Art der Eingabe, die Sie erwarten, kann es sinnvoll sein, weitere Priorisierung / Bereinigung basierend auf erreichbaren Scores durchzuführen.

Meine 35-Zeilen-Python-Implementierung mit einer 10x10-Zufallsmatrix aus kleinen ganzen Zahlen und b_ij einer Konstanten 2 lief in wenigen Sekunden. b_ij = 3 (was bis zu 7 der 10 Werte für jedes Paar von Arrays erlaubt!) dauerte ungefähr eine Minute.