Algorithmus split ein array in P subarrays der Summe ausgeglichen

Lassen Sie uns zuerst formalisieren Ihre Optimierungsproblem durch Angabe der Eingabe -, Ausgabe -, und der Maßstab für jedes mögliche Lösung (ich hoffe das ist in deinem Interesse):

Gegeben ein array Eine von positiven ganzen zahlen und eine positive ganze Zahl P, trennen Sie das array Eine in P nicht-überlappende subarrays, so dass die Differenz zwischen der Summe der einzelnen subarray und die perfekte Summe der subarrays (Summe(Eine)/P) minimal ist.

Eingang: Array Eine von positiven ganzen zahlen; P ist eine positive ganze Zahl.

Ausgabe: Array SA von P nicht-negativen ganzen zahlen, die die Länge jedes subarray von Eine, wo die Summe dieser subarray Längen ist gleich der Länge der Eine.

Messen: abs(sum(sa)-Summe(Eine)/P) minimal ist für jeden sa ∈ {sa | sa = (Eine_ich, ..., Eine_ich+SAj) für ich = (Σ SA_j), j von 0 bis P-1}.

Den Eingang und Ausgabe definieren Sie die Menge der gültigen Lösungen. Die Messen definiert ein Maß für den Vergleich mehrerer Lösungen. Und da sind wir auf der Suche nach einer Lösung mit dem geringsten Unterschied zu der perfekten Lösung (minimierungsproblem), Messen sollte auch minimal sein.

Mit diesen Informationen ist es Recht einfach zu implementieren, die measure Funktion (hier in Python):

def measure(a, sa):
    sigma = sum(a)/len(sa)
    diff = 0
    i = 0
    for j in xrange(0, len(sa)):
        diff += abs(sum(a[i:i+sa[j]])-sigma)
        i += sa[j]
    return diff

print measure([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], [3,4,4,5]) # prints 8

Nun das finden einer optimalen Lösung ist ein wenig härter.

Können wir die Backtracking-Algorithmus für die Suche nach gültigen Lösungen und nutzen Sie die Messen Funktion zu bewerten. Wir haben im Grunde versuchen alle möglichen Kombinationen von P nicht-negative ganze zahlen, die Summe bis zu der Länge(Eine) sind, um alle möglichen gültigen Lösungen. Dies stellt zwar sicher, nicht zu verpassen eine gültige Lösung, es ist im Grunde ein brute-force-Ansatz mit dem Vorteil, dass wir die weglassen können, einige Zweige, die kann nicht besser sein als unsere noch die beste Lösung. E. g. in dem obigen Beispiel, würden wir nicht testen müssen, die Lösungen mit [9,...] (Messen > 38), wenn wir schon eine Lösung mit Messen ≤ 38.

Folgenden pseudocode-Muster von Wikipedia, unser bt Funktion sieht wie folgt aus:

def bt(c):
    global P, optimum, optimum_diff
    if reject(P,c):
        return
    if accept(P,c):
        print "%r with %d" % (c, measure(P,c))
        if measure(P,c) < optimum_diff:
            optimum = c
            optimum_diff = measure(P,c)
        return
    s = first(P,c)
    while s is not None:
        bt(list(s))
        s = next(P,s)

Den globalen Variablen P, optimum, und optimum_diff stellen die problem-Instanz hält die Werte für Eine, P, und sigma, sowie die optimale Lösung und Maß:

class MinimalSumOfSubArraySumsProblem:
    def __init__(self, a, p):
        self.a = a
        self.p = p
        self.sigma = sum(a)/p

Nächstes legen wir die reject und accept Funktionen, die sind ziemlich geradlinig:

def reject(P,c):
    return optimum_diff < measure(P,c)
def accept(P,c):
    return None not in c

Diese einfach ablehnt, ein Kandidat, dessen Maß ist schon mehr als unsere noch die optimale Lösung. Und wir akzeptieren jede gültige Lösung.

Den measure Funktion ist auch leicht verändert, aufgrund der Tatsache, dass c enthalten nun None Werte:

def measure(P, c):
    diff = 0
    i = 0
    for j in xrange(0, P.p):
        if c[j] is None:
            break;
        diff += abs(sum(P.a[i:i+c[j]])-P.sigma)
        i += c[j]
    return diff

Den verbleibenden zwei Funktion first und next sind ein wenig komplizierter:

def first(P,c):
    t = 0
    is_complete = True
    for i in xrange(0, len(c)):
        if c[i] is None:
            if i+1 < len(c):
                c[i] = 0
            else:
                c[i] = len(P.a) - t
            is_complete = False
            break;
        else:
            t += c[i]
    if is_complete:
        return None
    return c

def next(P,s):
    t = 0
    for i in xrange(0, len(s)):
        t += s[i]
        if i+1 >= len(s) or s[i+1] is None:
            if t+1 > len(P.a):
                return None
            else:
                s[i] += 1
            return s

Grundsätzlich first entweder ersetzt die nächste None Wert in der Liste, die entweder mit 0 wenn es nicht der Letzte Wert in der Liste oder der restliche stellen eine gültige Lösung (wenig Optimierung hier), wenn es den letzten Wert in der Liste, oder es zurück None wenn es keine None Wert in der Liste. next einfach Schritten die Rechte integer, die von einem oder zurück None wenn eine Erhöhung würde einen Verstoß gegen das Gesamt-limit.

Nun alles, was Sie brauchen, ist zum erstellen einer problem-Instanz initialisiert die globalen Variablen und rufen bt mit der Wurzel:

P = MinimalSumOfSubArraySumsProblem([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], 4)
optimum = None
optimum_diff = float("inf")
bt([None]*P.p)

@Gumbo 's Antwort ist eindeutig und umsetzbar, aber verbraucht viel Zeit, wenn die Länge(A) größer als 400 und P größer als 8. Dies ist da dieser Algorithmus ist eine Art brute-forcing mit Leistungen, wie er sagte.

In der Tat, eine sehr schnelle Lösung ist mit dynamische Programmierung.

Gegeben ein array A von positiven ganzen zahlen und eine positive ganze Zahl P, trennen Sie das array A in P nicht-überlappende subarrays, so dass die Differenz zwischen der Summe der einzelnen subarray und die perfekte Summe der subarrays (sum(A)/P) minimal ist.

Maßnahme: ist der Durchschnitt von P subarray' Summen.

Dies kann sicherstellen, dass das Gleichgewicht der Summe, da es die definition von Standardabweichung.

Halten, dass Ein array hat N Elemente; Q(i,j) bedeutet, dass die Mindest-Maß-Wert, wenn die split die letzten i Elemente von A in j subarrays. D(i,j) bedeutet (sum(B)-sum(A)/P)^2 wenn array B aus der i~jth Elemente Einer ( 0<=i<=j<N ).

Mindestmaß der Frage ist die Berechnung von Q(N,P). Und wir finden, dass:

Q(N,P)=MIN{Q(N-1,P-1)+D(0,0); Q(N-2,P-1)+D(0,1); ...; Q(N-1,P-1)+D(0,N-P)}

So, wie es gelöst werden kann dynamische Programmierung.

 Q(i,1) = D(N-i,N-1)

 Q(i,j) = MIN{ Q(i-1,j-1)+D(N-i,N-i); 
               Q(i-2,j-1)+D(N-i,N-i+1); 
               ...; 
               Q(j-1,j-1)+D(N-i,N-j)}

Also der Algorithmus Schritt ist:

 1. Cal j=1:

    Q(1,1), Q(2,1)... Q(3,1)

 2. Cal j=2:

    Q(2,2) = MIN{Q(1,1)+D(N-2,N-2)};

    Q(3,2) = MIN{Q(2,1)+D(N-3,N-3); Q(1,1)+D(N-3,N-2)}

    Q(4,2) = MIN{Q(3,1)+D(N-4,N-4); Q(2,1)+D(N-4,N-3); Q(1,1)+D(N-4,N-2)}

 ... Cal j=...

 P. Cal j=P:

    Q(P,P), Q(P+1,P)...Q(N,P)

The final minimum Measure value is stored as Q(N,P)! 
To trace each subarray's length, you can store the 
MIN choice when calculate Q(i,j)=MIN{Q+D...}

Platz für D(i,j);

Zeit für berechnen Sie F(N,P)

im Vergleich zu den Reine brute-forcing Algorithmus verbraucht Zeit.

Frage ich mich, ob Folgendes funktionieren würde:

Gehen von der linken Seite, sobald sum > sigma, Zweig, in, zwei, eins, darunter der Wert, der drückt ihn über, und eine, die nicht. Rekursiv verarbeiten Daten auf der rechten Seite mit rightSum = totalSum-leftSum und rightP = P-1.

So, am Anfang, Summe = 60

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

Dann für 2 4 6 7, Summe = 19 > sigma, also aufgeteilt in:

2 4 6     7 6 3 3 3 4 3 4 4 4 3 3 1

2 4 6 7     6 3 3 3 4 3 4 4 4 3 3 1

Dann verarbeiten wir 7 6 3 3 3 4 3 4 4 4 3 3 1 und 6 3 3 3 4 3 4 4 4 3 3 1 mit P = 4-1 und sum = 60-12 und sum = 60-19 bzw.

Diese Ergebnisse, ich denke, O(P*n).

Kann es ein problem werden, wenn ein 1-oder 2-Werte ist mit Abstand der größte, aber für jeden Wert >= sigma, können wir wohl nur setzen, dass es in seiner eigenen partition (Vorverarbeitung der Arrays zu finden ist diese vielleicht die beste Idee (und reduzieren die Summe angemessen)).

Wenn es funktioniert, sollte es hoffentlich Minimierung der sum-of-squared-error (oder Nähe), die scheint, wie Sie die gewünschten Messen.

Dein problem ist sehr ähnlich oder die gleichen wie die, die minimum makespan scheduling problem, je nachdem, wie Sie definieren Ihr Ziel. In dem Fall, dass Sie wollen, um zu minimieren die maximale |sum_i - sigma| ist es genau das problem.

Als auf die in dem Wikipedia-Artikel, dieses problem ist NP-vollständig für p > 2. Graham list-scheduling-Algorithmus ist optimal für p <= 3 wird, und liefert eine Näherung Verhältnis von 2 - 1/p. Sie können check out Wikipedia für weitere algorithmen und deren Annäherung.

Alle algorithmen, die auf dieser Seite sind entweder die Lösung für ein anderes Ziel, falsche/nicht optimal, oder kann verwendet werden, um zu lösen jedes problem in NP 🙂

Vor kurzem musste ich das und habe wie folgt;

1. erstellen, die eine erste sub-arrays array mit der Länge gegeben, sub-arrays zählen. sub-arrays muss die eine Summe-Eigenschaft zu. ie [[sum:0],[sum:0]...[sum:0]]
2. Sortieren Sie die Haupt-array absteigend.
3. Suche nach dem sub-array mit den kleinsten Summe und legen Sie ein Element aus Haupt-array und erhöhe den sub-arrays, die sum-Eigenschaft des eingefügten Elements der Wert.
4. wiederholen Sie Punkt 3 bis zum Ende der Haupt-array erreicht ist.
5. Rückkehr der initial array.

Dies ist der code in JS.

JS:

function groupTasks(tasks,groupCount){
  var  sum = tasks.reduce((p,c) => p+c),
   initial = [...Array(groupCount)].map(sa => (sa = [], sa.sum = 0, sa));
  return tasks.sort((a,b) => b-a)
              .reduce((groups,task) => { var group = groups.reduce((p,c) => p.sum < c.sum ? p : c);
                                         group.push(task);
                                         group.sum += task;
                                         return groups;
                                       },initial);
}

var tasks = [...Array(50)].map(_ => ~~(Math.random()*10)+1), //create an array of 100 random elements among 1 to 10
   result = groupTasks(tasks,7);                             //distribute them into 10 sub arrays with closest sums

console.log("input array:", JSON.stringify(tasks));
console.log(result.map(r=> [JSON.stringify(r),"sum: " + r.sum]));