Bildung eines Ausdrucks mit maximalem Wert

Question

Gegeben n Ganzzahlen, gibt es eine O(n) o O(n log n) Algorithmus, der den maximalen Wert eines mathematischen Ausdrucks berechnen kann, der durch Einfügen der Operatoren erhalten werden kann - , + , * und Klammern zwischen den angegebenen Zahlen? Nehmen Sie nur binäre Varianten der Operatoren an, also kein unäres Minus, außer vor dem ersten Element, falls erforderlich.

Zum Beispiel, wenn -3 -4 5 können wir den folgenden Ausdruck bilden (-3) * (-4) * 5 , dessen Wert 60 und maximal möglich.

Hintergrund:

Ich bin vor einiger Zeit beim Studium genetischer Algorithmen über dieses Problem gestolpert und habe gelernt, dass es ziemlich einfach mit einem klassischen genetischen Algorithmus gelöst werden kann. Dieser läuft jedoch langsam, und er ist nur in der Theorie einfach, da der Code in der Praxis ziemlich hässlich wird (Auswertung des Ausdrucks, Überprüfung der korrekten Platzierung von Klammern usw.). Außerdem ist nicht garantiert, dass wir das absolute Maximum finden.

All diese Unzulänglichkeiten genetischer Algorithmen brachten mich dazu, mich zu fragen: Gibt es, da wir uns nicht um Divisionen kümmern müssen, eine Möglichkeit, dies mit einem klassischeren Ansatz, wie dynamischer Programmierung oder einer gierigen Strategie, effizient zu tun?

Aktualisierung:

Hier ist ein F#-Programm, das die von @Keith Randall vorgeschlagene DV-Lösung zusammen mit meiner Verbesserung implementiert, die ich in einem Kommentar zu seinem Beitrag geschrieben habe. Es ist sehr ineffizient, aber ich behaupte, dass es polynomiell ist und kubische Komplexität hat. Es läuft in ein paar Sekunden für ~50-Element-Arrays. Es wäre wahrscheinlich schneller, wenn es vollständig imperativ geschrieben wäre, da wahrscheinlich viel Zeit für den Aufbau und das Durchlaufen von Listen verschwendet wird.

open System
open System.IO
open System.Collections.Generic

let Solve (arr : int array) =
    let memo = new Dictionary<int * int * int, int>()

    let rec Inner st dr last = 
        if st = dr then 
            arr.[st]
        else
            if memo.ContainsKey(st, dr, last) then
                memo.Item(st, dr, last)
            else
                match last with
                | 0 ->  memo.Add((st, dr, last),
                            [
                                for i in [st .. dr - 1] do
                                    for j in 0 .. 2 do
                                        for k in 0 .. 2 do
                                            yield (Inner st i j) * (Inner (i + 1) dr k)
                            ] |> List.max) 
                        memo.Item(st, dr, last)

                | 1 ->  memo.Add((st, dr, last),
                            [
                                for i in [st .. dr - 1] do
                                    for j in 0 .. 2 do
                                        for k in 0 .. 2 do
                                            yield (Inner st i j) + (Inner (i + 1) dr k)
                            ] |> List.max) 
                        memo.Item(st, dr, last)

                | 2 ->  memo.Add((st, dr, last),
                            [
                                for i in [st .. dr - 1] do
                                    for j in 0 .. 2 do
                                        for k in 0 .. 2 do
                                            yield (Inner st i j) - (Inner (i + 1) dr k)
                            ] |> List.max) 
                        memo.Item(st, dr, last)

    let noFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |> List.max

    arr.[0] <- -1 * arr.[0]
    memo.Clear()
    let yesFirst = [ for i in 0 .. 2 do yield Inner 0 (arr.Length - 1) i ] |> List.max

    [noFirst; yesFirst] |> List.max

let _ = 
    printfn "%d" <| Solve [|-10; 10; -10|]
    printfn "%d" <| Solve [|2; -2; -1|]
    printfn "%d" <| Solve [|-5; -3; -2; 0; 1; -1; -1; 6|]
    printfn "%d" <| Solve [|-5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6; -5; -3; -2; 0; 1; -1; -1; 6;|]

Ergebnisse:

1000
6
540
2147376354

Das letzte ist höchstwahrscheinlich ein Fehler aufgrund eines Überlaufs, ich versuche nur zu zeigen, dass ein relativ großer Test zu schnell läuft, um exponentiell zu sein.

Answer 1

Hier ist ein Lösungsvorschlag:

def max_result(a_):
  memo = {}
  a = list(a_)
  a.insert(0, 0)
  return min_and_max(a, 0, len(a)-1, memo)[1]

def min_and_max(a, i, j, memo):
  if (i, j) in memo:
    return memo[i, j]
  if i == j:
    return (a[i], a[i])
  min_val = max_val = None
  for k in range(i, j):
    left = min_and_max(a, i, k, memo)
    right = min_and_max(a, k+1, j, memo)
    for op in "*-+":
      for x in left:
        for y in right:
          val = apply(x, y, op)
          if min_val == None or val < min_val: min_val = val
          if max_val == None or val > max_val: max_val = val
  ret = (min_val, max_val)
  memo[i, j] = ret
  return ret

def apply(x, y, op):
  if op == '*': return x*y
  if op == '+': return x+y
  return x-y

max_result ist die Hauptfunktion, und min_and_max ist eine Hilfsfunktion. Letztere gibt das minimale und maximale Ergebnis zurück, das mit der Teilfolge a[i..j] erreicht werden kann.

Es geht davon aus, dass sich die maximalen und minimalen Ergebnisse von Sequenzen aus den maximalen und minimalen Ergebnissen von Teilsequenzen zusammensetzen. Unter dieser Annahme hat das Problem eine optimale Substruktur und kann mit dynamischer Programmierung (oder Memoisierung) gelöst werden. Die Ausführungszeit ist O(n^3).

Ich habe die Korrektheit nicht bewiesen, aber ich habe die Ausgabe gegen eine Brute-Force-Lösung mit Tausenden von kleinen, zufällig generierten Eingaben geprüft.

Es behandelt die Möglichkeit eines führenden unären Minus, indem es eine Null am Anfang der Sequenz einfügt.

EDIT

Ich habe etwas mehr über dieses Problem nachgedacht, und ich glaube, es lässt sich auf ein einfacheres Problem reduzieren, bei dem alle Werte (streng) positiv sind und nur die Operatoren * und + erlaubt sind.

Entfernen Sie einfach alle Nullen aus der Folge und ersetzen Sie negative Zahlen durch ihren absoluten Wert.

Wenn es in der resultierenden Folge keine Einsen gibt, ist das Ergebnis einfach das Produkt aller Zahlen.

Nach dieser Reduzierung würde der einfache dynamische Programmieralgorithmus funktionieren.

EDIT 2

Aufgrund der bisherigen Erkenntnisse glaube ich, dass ich eine lineare Lösung gefunden habe:

def reduce(a):
  return filter(lambda x: x > 0, map(abs, a))

def max_result(a):
  b = reduce(a)
  if len(b) == 0: return 0
  return max_result_aux(b)

def max_result_aux(b):
  best = [1] * (len(b) + 1)
  for i in range(len(b)):
    j = i
    sum = 0
    while j >= 0 and i-j <= 2:
      sum += b[j]
      best[i+1] = max(best[i+1], best[j] * sum)
      j -= 1
  return best[len(b)]

best[i] ist das maximale Ergebnis, das mit der Teilsequenz b[0 (i-1)] erzielt werden kann.

EDIT 3

Hier ist ein Argument für die O(n) Algorithmus auf der Grundlage der folgenden Annahme:

Sie können das maximale Ergebnis immer mit einem Ausdruck der Form

+/- (a_1 +/- ... +/- a_i) * ... * (a_j +/- ... +/- a_n)

Das heißt: ein Produkt von Faktoren, das aus einer algebraischen Summe von Termen besteht (einschließlich des Falles, dass nur ein Faktor vorhanden ist).

Ich werde auch die folgenden Lemmata verwenden, die leicht zu beweisen sind:

Lemma 1: x*y >= x+y für alle x,y tal que x,y >= 2

Lemma 2: abs(x_1) + ... + abs(x_n) >= abs(x_1 +/- ... +/- x_n)

Jetzt geht's los.

Das Vorzeichen der einzelnen Faktoren spielt keine Rolle, da man das Produkt immer positiv machen kann, indem man das führende unäre Minus verwendet. Um das Produkt zu maximieren, müssen wir also den absoluten Wert jedes Faktors maximieren.

Abgesehen von dem trivialen Fall, dass alle Zahlen Nullen sind, wird bei einer optimalen Lösung kein Faktor nur aus Nullen bestehen. Da Nullen innerhalb jeder Summe von Termen keine Wirkung haben und jeder Faktor mindestens eine von Null verschiedene Zahl enthält, können wir alle Nullen entfernen. Von nun an nehmen wir an, dass es keine Nullen gibt.

Konzentrieren wir uns auf jede Summe der Begriffe einzeln:

(x_1 +/- x_2 +/- ... +/- x_n)

Unter Lemma 2 ist der maximale absolute Wert, den jeder Faktor erreichen kann, die Summe der absoluten Werte der einzelnen Terme. Dies kann auf folgende Weise erreicht werden:

Wenn x_1 positiv ist, addiere alle positiven Terme und subtrahiere alle negativen Terme. Wenn x_1 negativ ist, subtrahiere alle positiven Terme und addiere alle negativen Terme.

Dies bedeutet, dass das Vorzeichen der einzelnen Terme keine Rolle spielt, wir können den absoluten Wert jeder Zahl berücksichtigen und nur den Operator + innerhalb der Faktoren verwenden. Von nun an gehen wir davon aus, dass alle Zahlen positiv sind.

Der entscheidende Schritt, der zu einer O(n) Algorithmus ist es, zu beweisen, dass das maximale Ergebnis immer mit Faktoren erreicht werden kann, die höchstens 3 Terme haben.

Angenommen, wir haben einen Faktor von mehr als 3 Termen, durch Lemma 1 können wir ihn in zwei kleinere Faktoren von jeweils 2 oder mehr Termen zerlegen (die sich also jeweils zu 2 oder mehr addieren), ohne das Gesamtergebnis zu verringern. Wir können sie so lange zerlegen, bis keine Faktoren mit mehr als 3 Termen mehr übrig sind.

Damit ist die Argumentation abgeschlossen. Ich habe immer noch keine vollständige Rechtfertigung für die ursprüngliche Annahme gefunden. Aber ich habe meinen Code mit Millionen von zufällig generierten Fällen getestet und konnte ihn nicht brechen.

Answer 2

Ein vernünftig großer Wert kann in O(N) gefunden werden. Betrachten Sie dies als einen gierigen Algorithmus.

1. Finde alle positiven Zahlen 2. Speichern Sie das Ergebnis als A .
2. Zähle alle "-1 "s . Speichern Sie das Ergebnis als B .
3. Finde alle negativen Zahlen -2. Speichere das Ergebnis als C .
4. Zähle alle "1 "s. Speichern Sie das Ergebnis als D .
5. Initialisieren Produkt zu 1.
6. Wenn A nicht leer ist, multiplizieren Sie Produkt durch das Produkt aus A .
7. Wenn C nicht leer ist und eine gerade Anzahl hat, multiplizieren Sie Produkt durch das Produkt aus C .
8. Wenn C eine ungerade Zahl ist, nehmen Sie die kleinste Zahl in der Größenordnung von C weg (speichern Sie es als x ), und multiplizieren Produkt durch das Produkt aus dem Rest von C .
9. Wenn x eingestellt ist und B ungleich Null ist, vergleiche Produkt × -x con Produkt - x + 1 .
   • Ist der erste Wert deutlich größer, verringern Sie B mit 1 und multiplizieren Produkt von - x dann entfernen x .
   • Wenn letztere größer ist, unternehmen Sie nichts.
10. Satz Ergebnis auf 0. Wenn Produkt 1, hinzufügen zu Ergebnis .
11. hinzufügen D à Ergebnis , was der Addition von D "1 "s.
12. hinzufügen B à Ergebnis , was die Subtraktion von B "-1 "s.
13. Wenn x gesetzt ist, subtrahieren x de Ergebnis .

Die Zeitkomplexe sind:

1. O(N), 2. O(N), 3. O(N), 4. O(N), 5. O(1), 6. O(N), 7. O(N), 8. O(N), 9. O(1), 10. O(1), 11. O(1), 12. O(1), 13. O(1),

Der gesamte Algorithmus läuft also in O(N)-Zeit.

---

Eine Beispielsitzung:

-3 -4 5

1. A \= [5]
2. B \= 0
3. C \= [-3, -4]
4. D \= 1
5. Produkt \= 1
6. A nicht leer ist, also Produkt \= 5.
7. C ist gerade, also Produkt \= 5 × -3 × -4 = 60
8. -
9. -
10. Produkt 1, also Ergebnis \= 60.
11. -
12. -
13. -

5 × -3 × -4 = 60

-5 -3 -2 0 1 -1 -1 6 

1. A \= [6]
2. B \= 2
3. C \= [-5, -3, -2]
4. D \= 1
5. Produkt \= 1
6. A nicht leer ist, also Produkt \= 6
7. -
8. C ist ungerade, also x \= -2, und Produkt \= 6 × -5 × -3 = 90.
9. x eingestellt ist und B ungleich Null ist. Vergleiche Produkt × -x \= 180 und Produkt - x + 1 \= 93. Da der erste Wert größer ist, setzen wir B zu 1, Produkt auf 180 und entfernen x .
10. Ergebnis \= 180.
11. Ergebnis \= 180 + 1 = 181
12. Ergebnis \= 181 + 1 = 182
13. -

6 × -5 × -3 × -2 × -1 + 1 - (-1) + 0 = 182

2 -2 -1

1. A \= [2]
2. B \= 1
3. C \= [-2]
4. D \= 0
5. Produkt \= 1
6. Produkt \= 2
7. -
8. x \= -2, Produkt ist unverändert.
9. B ungleich Null ist. Vergleiche Produkt × -x \= 4 und Produkt - x + 1 \= 5. Da letztere größer ist, tun wir nichts.
10. Ergebnis \= 2
11. -
12. Ergebnis \= 2 + 1 = 3
13. Ergebnis \= 3 - (-2) = 5.

2 - (-1) - (-2) = 5.

Answer 3

Sie sollten in der Lage sein, dies mit dynamischer Programmierung zu tun. Sei x_i Ihre Eingangszahlen sein. Dann lassen Sie M(a,b) sei der maximale Wert, den man mit der Teilsequenz x_a über x_b . Sie können dann berechnen:

M(a,a) = x_a
M(a,b) = max_i(max(M(a,i)*M(i+1,b), M(a,i)+M(i+1,b), M(a,i)-M(i+1,b))

éditer :

Ich denke, Sie müssen sowohl den maximalen als auch den minimalen berechenbaren Wert für jede Teilsequenz berechnen. Also

Max(a,a) = Min(a,a) = x_a
Max(a,b) = max_i(max(Max(a,i)*Max(i+1,b),
                     Max(a,i)*Min(i+1,b),
                     Min(a,i)*Max(i+1,b),
                     Min(a,i)*Min(i+1,b),
                     Max(a,i)+Max(i+1,b),
                     Max(a,i)-Min(i+1,b))
...similarly for Min(a,b)...

Answer 4

Arbeiten Sie in umgekehrter Reihenfolge - so müssen Sie nicht mit Klammern arbeiten. Als Nächstes setzen Sie ein - vor jede -ve Zahl (wodurch sie positiv wird). Schließlich multiplizieren Sie alle Zahlen miteinander. Ich bin mir nicht sicher, was die Komplexität angeht, wahrscheinlich etwa O(N) .

EDIT: Ich habe die 0 vergessen. Wenn sie in Ihrer Eingabemenge vorkommt, fügen Sie sie dem Ergebnis hinzu.

Answer 5

Das fühlt sich für mich nach NP Complete an, obwohl ich noch nicht herausgefunden habe, wie man eine Reduktion vornimmt. Wenn ich richtig liege, dann könnte ich sagen

• Niemand auf der Welt weiß, ob ein polynomieller Algorithmus existiert, geschweige denn O(n log n) Die meisten Informatiker vermuten jedoch, dass es keine gibt.
• Es gibt Polyzeit-Algorithmen zur Schätzung der Antwort, wie der von Ihnen beschriebene genetische Algorithmus.
• Ich denke, die Frage, die Sie stellen wollen, lautet: "Gibt es eine einigermaßen nützliche O(n) o O(n log n) Algorithmus zur Schätzung des Maximalwerts?"