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

Dies ist mein erster Beitrag auf Stackoverflow, daher entschuldige ich mich im Voraus für fehlende Umgangsformen. Im Interesse einer vollständigen Offenlegung hat Dave mich auf dieses Problem aufmerksam gemacht.

Hier ist ein O(N^2logN) Lösung, vor allem wegen des wiederholten Sortierschritts in der for-Schleife.

1. Absolute Werte: Null-Elemente entfernen und nach dem absoluten Wert sortieren. Da Sie Ihrem Endergebnis ein negatives Vorzeichen voranstellen dürfen, spielt es keine Rolle, ob Ihre Antwort negativ oder positiv ist. Es zählen nur die absoluten Werte aller Zahlen in der Menge.

2. Multiplikation nur für Zahlen > 1: Wir stellen fest, dass für jede Menge positiver ganzer Zahlen größer als 1 (z. B. {2,3,4} ), das größte Ergebnis stammt aus einer Multiplikation. Dies kann durch eine Aufzählungstechnik oder ein Widerspruchsargument über die erlaubten Operationen + und - gezeigt werden. z.B. (2+3)*4 = 2*4 + 3*4 < 3*4 + 3*4 = 2*(3*4) . Mit anderen Worten: Die Multiplikation ist die "mächtigste" Operation (abgesehen von den 1en).

3. Addition der 1en zu den kleinsten Nicht-1-Zahlen: Da die Multiplikation bei den 1en eine nutzlose Operation ist, ist es besser, sie zu addieren. Auch hier zeigen wir eine vollständige Ordnung für das Ergebnis einer Addition. Der Rhetorik halber betrachten wir wieder die Menge {2,3,4} . Wir stellen fest, dass: 2*3*(4+1) <= 2*(3+1)*4 <= (2+1)*3*4 . Mit anderen Worten: Wir erhalten den größten "Nutzen" aus einer 1, indem wir sie zum kleinsten vorhandenen Nicht-1-Element in der Menge hinzufügen. Bei einer sortierten Menge lässt sich dies folgendermaßen bewerkstelligen O(N^2logN) .

So sieht der Pseudocode aus:

S = input set of integers;

S.absolute();
S.sort();

//delete all the 0 elements
S.removeZeros();

//remove all 1 elements from the sorted list, and store them
ones = S.removeOnes();

//now S contains only integers > 1, in ascending order S[0] ... S[end]
for each 1 in ones:
   S[0] = S[0] + 1; 
   S.sort();
end

max_result = Product(S);

Answer 2

Ich weiß, ich bin zu spät dran, aber ich habe das als Herausforderung für mich selbst angenommen. Hier ist die Lösung, die mir eingefallen ist.

type Operation =
    | Add
    | Sub
    | Mult

type 'a Expr =
    | Op of 'a Expr * Operation * 'a Expr
    | Value of 'a

let rec eval = function
    | Op (a, Add, b)  -> (eval a) + (eval b)
    | Op (a, Sub, b)  -> (eval a) - (eval b)
    | Op (a, Mult, b) -> (eval a) * (eval b)
    | Value x -> x

let rec toString : int Expr -> string = function
    | Op (a, Add, b)  -> (toString a) + " + " + (toString b)
    | Op (a, Sub, b)  -> (toString a) + " - " + (toString b)
    | Op (a, Mult, b) -> (toString a) + " * " + (toString b)
    | Value x -> string x

let appendExpr (a:'a Expr) (o:Operation) (v:'a) =
    match o, a with
    | Mult, Op(x, o2, y) -> Op(x, o2, Op(y, o, Value v))
    | _                  -> Op(a, o, Value v)

let genExprs (xs:'a list) : 'a Expr seq =
    let rec permute xs e =
        match xs with
        | x::xs ->
            [Add; Sub; Mult]
            |> Seq.map (fun o -> appendExpr e o x)
            |> Seq.map (permute xs)
            |> Seq.concat
        | [] -> seq [e]
    match xs with
    | x::xs -> permute xs (Value x)
    | [] -> Seq.empty

let findBest xs =
    let best,result =
        genExprs xs
        |> Seq.map (fun e -> e,eval e)
        |> Seq.maxBy snd
    toString best + " = " + string result

findBest [-3; -4; 5]
gibt zurück. "-3 * -4 * 5 = 60"

findBest [0; 10; -4; 0; 52; -2; -40]
gibt zurück. "0 - 10 * -4 + 0 + 52 * -2 * -40 = 4200"

Es sollte mit jedem Typ funktionieren, der Vergleiche und die grundlegenden mathematischen Operatoren unterstützt, aber FSI wird es auf ints beschränken.