Wie lautet der Name dieses Problems?

Question

Sie erhalten eine Liste von Entfernungen zwischen verschiedenen Punkten in einer einzelnen Zeile.

Zum Beispiel:

• 100 zwischen a und b
• 20 zwischen c und b
• 90 zwischen c und d
• 170 zwischen a und d

Return der sortierte Reihenfolge der Punkte, wie sie auf der Linie mit Abständen zwischen ihnen erscheinen:

Zum Beispiel ergibt der obige Eingang: ein < ---- 80 -----> c < ---- 20 ------> b < ---- 70 -----> d oder die umgekehrte Reihenfolge (spielt keine Rolle)

Wie heißt dieses Problem? Ich würde es gerne recherchieren.

Wenn jemand weiß auch, was sind einige der möglichen asymptotischen Laufzeiten dafür erreicht?

Answer 1

nicht sicher, dass es einen Namen hat; formeller gesagt, wäre es:

|a-b| = 100 
|c-b| = 20 
|c-d| = 90 
|a-d| = 170 

wo |x| steht für die absolute value von x

Was das verallgemeinerte System geht, wenn man N Gleichungen dieser Art mit k Unbekannten haben, haben Sie N Wahlmöglichkeiten des Zeichens. Ohne Verlust der Allgemeinheit (weil jede Lösung eine zweite Lösung mit umgekehrter Ordnung ergibt) können Sie ein Vorzeichen für die erste Gleichung und einen bestimmten Wert für eine der Unbekannten wählen (da das Ganze in der Position nach links und rechts verschoben werden kann). Dann haben Sie 2 ^N-1 Möglichkeiten für die restlichen Gleichungen, und alles, was Sie tun müssen, ist durch sie gehen, um zu sehen, welche, wenn überhaupt, Lösungen haben. Da die Koeffizienten alle +/- 1 sind und jede Gleichung hat zwei Unbekannten, gehen Sie einfach durch sie eins nach dem anderen:

Step 1: Without loss of generality, 
    choose a sign for one equation 
    and pick a value for one unknown: 
a-b = 100, a = 0 

Step 2: Choose signs for the remaining absolute values. 
a = 0 
a-b = 100 
c-b = 20 
c-d = 90 
a-d = 170 

Step 3: go through them one by one to solve/verify there aren't conflicts 
(time = N steps). 
0-b = 100 => b = -100 
c-b = 20 => c = -80 
c-d = 90 => d = -170 
a-d = 170 => OK  => (0,-100,-80,-170) is a solution 

Step 4: if this doesn't work, go back through the possible choices of sign 
and try again, starting at step 2. 

Full set of solutions is (0,-100,-80,-170) 
and its negation (0,100,80,170) and any number x<sub>0</sub> added to all terms. 

So eine obere Schranke für die Laufzeit O (N * 2 ^N-1 ist) ≡ O (N * 2 ^N).

Ich nehme an, es könnte eine Abkürzung geben, aber keine offensichtliche kommt in den Sinn.

Answer 2

Algebra ...

oder es kann eine Vereinfachung des Reiseproblem

Answer 3

Ich habe nicht ein Algorithmen buchen praktisch sein, aber das klingt wie ein graph search problem wo die Pfade beschränkt sind. Sie könnten wahrscheinlich Dijkstra's Algorithm oder eine Variante davon verwenden.

Answer 4

Wie geschrieben, ist Ihr Problem nur ein System von nichtlinearen Gleichungen (ausgedrückt mit absoluten Werten oder quadratischen Gleichungen). Es ähnelt jedoch den Problemen, Golomb-Herrscher oder perfekte Herrscher zu finden.

Wenn Sie Ihre Einschränkungen als quadratische Gleichungen z.(a-b)^2 = 100^2, dann können Sie dies als ein quadratisches Programmierproblem formulieren und einige der gut untersuchten Techniken für diese Klasse von Problemen verwenden.

Answer 5

Unter Berücksichtigung des Vorzeichens der Richtung jedes Segments X[i] -> X[i+1] wird es zu boolean satisfiability problem. Ich kann keine offensichtliche Vereinfachung sehen. Die Laufzeit ist O (2^N) - speziell 2^(N-2) Tests mit N Werten und einem O (1) Ausdruck zum Testen.

Angenommen a = 0 und Fixieren der Richtung a -> b:

a = 0 
b = 100 
c = b + 20 X[0] = 100 + 20 X[0] 
d = c + 90 X[1] = 100 + 20 X[0] + 90 X[1] 
test d == 170 

wo X[i] entweder +1 oder -1.

Obwohl der Ausdruck für d wird durch die Verwendung eines Gray code oder anderen solchen Mechanismus zum Ändern des Zustands von nur einem X O (N) Operationen ((N-2) Multiplikationen und (N-2), Additionen) erfordern zuzumin eine Zeit, so können die Kosten O (1) pro Test sein. (obwohl für N = 4 ist es wahrscheinlich nicht wert)

Vereinfachungen können auftreten, wenn Sie entweder mehr Einschränkungen als Punkte haben - wenn Sie |b-d| == 70 gegeben wurden, dann brauchen Sie nur Tests zwei Fälle statt vier - im Wesentlichen b, c und d werden zu ihrem eigenen vollständig eingeschränkten Teilproblem.

Vereinfachungen auch aus dem dreieckigen Eigenschaft

| |a-b| - |b-c| | <= |a-c| <= |a-b| + |b-c| für alle a, b und c entstehen können.

Also, wenn Sie viele Punkte haben, und Sie kennen die Summe der Abstände zwischen den Punkten bis zu einem bestimmten Punkt, wenn die Zuweisungen an X vorgenommen werden, und diese Summe ist weiter vom Zielwert als die Summe der Abstände zwischen die verbleibenden Punkte können Sie daraus ableiten, dass es keine Kombination von Zuweisungen der verbleibenden Punkte gibt, die funktionieren werden.