Dynamische Programmierung: Sum-of-Produkte

https://stackoverflow.com/questions/1814466

06-07-2019
|

Frage

Angenommen, Sie haben zwei Listen haben, L1 und L2, die gleiche Länge, N. Wir definieren prodSum wie:

def prodSum(L1, L2) :
    ans = 0
    for elem1, elem2 in zip(L1, L2) :
        ans += elem1 * elem2

    return ans

Gibt es einen effizienten Algorithmus zu finden, L1 unter der Annahme, sortiert ist, die Anzahl der Permutationen von L2, so dass prodSum (L1, L2)

Wenn es um das Problem vereinfachen würde, können Sie davon ausgehen, dass L1 und L2 sind beide Listen von ganzen Zahlen von [1, 2, ..., N].

Edit: Managu Antwort hat mir davon überzeugt, dass dies ohne die Annahme unmöglich ist, dass L1 und L2 sind Listen von ganzen Zahlen von [1, 2, ..., N]. Ich würde immer noch in Lösungen interessiert sein, dass diese Einschränkung übernehmen.

Lösung

Ich möchte zunächst eine gewisse Verwirrung über die Mathematik dispell, dann zwei Lösungen diskutieren und geben Code für einen von ihnen.

Es gibt eine Zählklasse genannt #P, die viel wie die Ja-Nein-Klasse NP ist. In qualitativer Hinsicht ist es noch schwieriger als NP. Es gibt keinen besonderen Grund zu glauben, dass dieses Zählproblem ist besser als # P-hart, obwohl es schwierig sein könnte, oder einfach, das zu beweisen.

viele # P-harte Probleme und NP-harte Probleme jedoch variieren enorm, wie lange dauern sie in der Praxis zu lösen, und sogar ein bestimmtes kann hart sein Problem leichter oder schwere Abhängigkeit von den Eigenschaften des Eingangs. Was NP-hard oder # P-Fest Mittel ist, dass es harte Fälle sind. Einige NP-hard und # P-schwere Probleme haben auch weniger harte Fälle oder sogar ganz leicht Fälle. (Andere haben nur sehr wenige Fälle, die viel einfacher scheinen als die härtesten Fälle).

So ist die praktische Frage eine Menge auf dem Eingang von Interesse abhängen könnte. Nehmen wir an, dass der Schwellenwert auf der hohen Seite oder auf der unteren Seite ist, oder Sie haben genug Speicher für eine anständige Anzahl der zwischengespeicherten Ergebnisse. Dann gibt es einen nützlichen rekursive Algorithmus, die Verwendung von zwei Ideen, einer von ihnen bereits erwähnt macht: (1) Nach dem teilweise einige der Werten zuweisen, die verbleibenden Schwellenwert für die Liste Fragmente alle Permutationen ausschließen kann, oder er kann sie alle ermöglichen. (2) Speicher erlauben, sollten Sie die Zwischensummen für einige verbleibende Schwelle und einige Liste Fragmente zwischenzuspeichern. Um das Caching zu verbessern, dann kann man auch die Elemente aus einer der Listen, um auszuwählen.

Hier ist ein Python-Code, der diesen Algorithmus implementiert:

list1 = [1,2,3,4,5,6,7,8,9,10,11]
list2 = [1,2,3,4,5,6,7,8,9,10,11]
size = len(list1)
threshold = 396     # This is smack in the middle, a hard value

cachecutoff = 6     # Cache results when up to this many are assigned

def dotproduct(v,w):
    return sum([a*b for a,b in zip(v,w)])

factorial = [1]
for n in xrange(1,len(list1)+1):
    factorial.append(factorial[-1]*n)

cache = {}

# Assumes two sorted lists of the same length

def countprods(list1,list2,threshold):
    if dotproduct(list1,list2) <= threshold:            # They all work
        return factorial[len(list1)]
    if dotproduct(list1,reversed(list2)) > threshold:   # None work
        return 0
    if (tuple(list2),threshold) in cache:               # Already been here
        return cache[(tuple(list2),threshold)]
    total = 0
    # Match the first element of list1 to each item in list2
    for n in xrange(len(list2)):
        total += countprods(list1[1:],list2[:n] + list2[n+1:],
            threshold-list1[0]*list2[n])
    if len(list1) >= size-cachecutoff:
        cache[(tuple(list2),threshold)] = total
    return total

print 'Total permutations below threshold:',
print countprods(list1,list2,threshold)
print 'Cache size:',len(cache)

Wie die Kommentarzeile sagt, testete ich diesen Code mit einem harten Wert der Schwelle. Es ist durchaus ein bisschen schneller als eine naive Suche über alle Permutationen.

Es gibt einen anderen Algorithmus, der besser als diese ist, wenn drei Bedingungen erfüllt sind: (1) Sie haben nicht genug Speicher haben für einen guten Cache, (2) die Listeneinträge sind kleine nicht-negativen ganzen Zahlen, und (3 ) sind Sie in den härtesten Schwellen interessiert. Eine zweite Situation dieses zweiten Algorithmus zu verwenden ist, wenn Sie gilt für alle Schwellen flat-out wollen, ob die anderen Bedingungen erfüllt sind. Um diesen Algorithmus für die zwei Listen der Länge n verwendet werden, zunächst eine Basis x holen, die eine Leistung von 10 oder 2 ist, die größer als n faktoriellen sind. Jetzt macht die Matrix

M[i][j] = x**(list1[i]*list2[j])

Wenn Sie die permanente dieser Matrix M berechnet unter Verwendung der Ryser Formel , dann die k-te Ziffer die permanent in der Basis x sagen Ihnen, die Anzahl der Permutationen, für die das Punktprodukt genau k ist. Darüber hinaus ist die Ryser Formel ziemlich viel schneller als die direkt alle Permutationen Summieren über. (Aber es ist immer noch exponentiell, so dass es nicht im Widerspruch zu der Tatsache, dass die Berechnung der permanent # P-hart).

Auch ja, es ist wahr, dass der Satz von Permutationen die symmetrische Gruppe ist. Es wäre toll, wenn Sie Gruppentheorie in irgendeiner Weise verwenden könnte dieses Zählproblem zu beschleunigen. Aber soweit ich weiß, nichts alles, was tief kommt aus dieser Beschreibung der Frage.

Schließlich, wenn statt genau die Anzahl der Permutationen unter einem Schwellenwert zu zählen, Sie wollten nur ungefähre diese Zahl, dann ist wahrscheinlich das Spiel komplett ändert. (Sie können die permanent in Polynomzeit annähern, aber das hilft hier nicht.) Ich würde darüber nachdenken, was zu tun ist; in jedem Fall ist es nicht die Frage gestellt.

Ich erkennen, dass es eine andere Art von Caching / dynamischer Programmierung, die aus der obigen Diskussion und dem obigen Code fehlt. Das Caching im Code implementiert ist im Frühstadium Caching: Wenn nur die ersten paar Werte von list1 zu list2 zugeordnet sind, und wenn ein verbleibender Schwelle mehr als einmal auftritt, dann kann der Cache der Code das Ergebnis wieder zu verwenden. Dies funktioniert gut if die Einträge von list1 und list2 ganze Zahlen sind, die nicht zu groß sind. Aber es wird ein gescheiterter Cache sein, wenn die Einträge sind typisch Gleitkommazahlen.

Sie können jedoch auch am anderen Ende vorauszuberechnen, wenn die meisten Werte von list1 zugewiesen wurden. In diesem Fall können Sie eine sortierte Liste der Teilergebnisse für alle übrigen Werte machen. Und denken Sie daran, können Sie list1 um aufbrauchen, und alle Permutationen auf der list2 Seite tun. Angenommen, dass die letzten drei Einträge von list1 sind [4,5,6], und nehmen wir an, dass drei der Werte in list2 (irgendwo in der Mitte) sind [2.1,3.5,3.7]. Dann würden Sie eine sortierte Liste der sechs Punktprodukte Cache:

endcache[ [2.1, 3.5, 3.7] ] = [44.9, 45.1, 46.3, 46.7, 47.9, 48.1]

Was bedeutet das für Sie tun? Wenn Sie in den Code anschauen, die ich Post hat die Funktion countprods (list1, list2, Schwelle) rekursiv seine Arbeit mit einer Untergrenze. Das erste Argument, list1, könnte als globalen Variable besser gewesen als Argument. Wenn list2 kurz genug ist, countprods kann seine Arbeit viel schneller tun, indem eine binäre Suche in der Liste endCache tun [list2]. (Ich habe gerade erfahren, von Stackoverflow, dass dies im bisect Modul in Python implementiert ist, obwohl eine Leistung Code sowieso nicht in Python geschrieben werden würde.) Im Gegensatz zu der Kopf-Cache kann das Ende Cache den Code viel schneller, auch wenn es keine numerischen Zufälle unter den Einträgen von list1 und list2. Ryser Algorithmus stinkt auch für dieses Problem ohne numerische Zufälle, so für diese Art von Eingang I nur zwei Beschleunigungen sehen: Absägen einen Zweig der Suchbaum mit dem „alle“ Test und die „keine“ Test, und das Ende Cache.

Andere Tipps

Wahrscheinlich nicht (ohne die vereinfachende Annahme): Ihr Problem ist NP-Hard. Hier ist eine triviale Reduktion auf SUBSET-SUM . Lassen Sie count_perms(L1, L2, x) die Funktion repräsentieren "die Anzahl der Permutationen von L2 zählen, so dass prodSum (L1, L2)

SUBSET_SUM(L2,n): # (determine if any subset of L2 adds up to n)
    For i in [1,...,len(L2)]
        Set L1=[0]*(len(L2)-i)+[1]*i
        calculate count_perms(L1,L2,n+1)-count_perms(L1,L2,n)
        if result positive, return true
    Return false

Wenn es also eine Art und Weise ist Ihre Funktion count_perms(L1, L2, x) effizient zu berechnen, dann würden wir einen effizienten Algorithmus haben SUBSET_SUM (L2, n) zu berechnen.

Damit wird auch ein abstraktes Algebra Problem erwiesen. Es war für mich eine Weile, aber hier ist ein paar Dinge, um loszulegen. Es gibt nichts schrecklich signifikant über die folgenden (es ist alles sehr einfach, eine Erweiterung auf der Tatsache, dass jede Gruppe eine Permutation Gruppe isomorph ist)., Aber es gibt eine andere Art und Weise auf dem Problem der Suche

Ich werde versuchen, ziemlich Standard-Notation zu bleiben: " x " ist ein Vektor, und " x _i" ist die i ^th Komponente von x . Wenn "L" eine Liste, L ist das Äquivalent Vektor. " 1 ⁿ" ist ein Vektor mit allen Komponenten = 1. Die Menge der natürlichen Zahlen n genommen wird die positiven ganzen Zahlen zu sein. "[A, b]" ist die Menge der ganzen Zahlen von a bis b, inklusive. "Θ ( x , y )" ist der Winkel, gebildet durch x und y

Hinweis prodSum ist das Punktprodukt. Die Frage ist, äquivalent zu finden, alle Vektoren L , die durch eine Operation (Permutieren Elemente) auf L2 derart, daß θ ( L1 , L ) von weniger als einen bestimmten Winkel α. Der Betrieb ist äquivalent einen Punkt in n zu reflektieren ⁿ durch einen Unterraum mit Darstellung:

n | ( x _i x _j ^-1) _{(i, j ) ∈ A}>

, wobei i und j sind in [1, n], hat A mindestens ein Element und keine (i, i) ist in A (dh A ist eine nicht-reflexive Teilmenge von [1, n] ², wo | A |> 0). Angegebene deutlicher (und mehrdeutig), sind die Unterräume die Punkte, wo eine oder mehrere Komponenten gleich zu einer oder mehreren anderen Komponenten sind. Die Reflexionen entsprechen Matrizen sind, deren Spalten alle Standard-Basisvektoren.

Lassen Sie uns die Reflexionsgruppe Name "RP _n" (es einen anderen Namen haben sollte, aber das Gedächtnis versagt). RP _n isomorph zu der symmetrischen Gruppe S _n. So

| RP _n | = | S _n | = N!

in 3 Dimensionen, Dies ergibt eine Gruppe der Ordnung 6. Die Reflexionsgruppe sind D ₃, die Dreieck Symmetriegruppe, als eine Untergruppe der Würfel Symmetriegruppe. Es stellt sich heraus, Sie können auch die Punkte erzeugen durch Rotation L2 in Schritten von π / 3 um die Linie entlang 1 ⁿ. Dies ist die die Modulgruppe z ₆ und dies weist auf eine mögliche Lösung: eine Gruppe der Ordnung n finden! mit einer minimalen Anzahl von Generatoren und verwendet, die die Permutationen von L2 als Sequenzen mit zunehmendem, dann abnimmt, mit Winkel L2 zu erzeugen. Von dort aus können wir versuchen, die Elemente L mit θ ( L1 , L ) n .

RP '₄ besteht aus 4 Subräume isomorph z konstruiert ₆. Allgemeiner gesagt, RP '_n n von Unterräumen isomorph RP aufgebaut ist,' _n-1.

Dies ist, wo meine abstrakten Algebra Muskeln wirklich beginnt zu scheitern. Ich werde versuchen, auf dem Bau zu arbeiten zu halten, aber Managu Antwort bleibt nicht viel Hoffnung. Ich befürchte, dass RP ₃ zu z ₆ ist die einzige nützliche Reduktion reduziert wir machen können.

Es sieht aus wie wenn l1 und l2 sind bestellt sowohl Hoch- als> niedrig (oder niedrig> hoch, was auch immer, wenn sie die gleiche Ordnung haben), wird das Ergebnis maximiert, und wenn sie oposite bestellt werden, wird das Ergebnis minimiert erscheinen, und andere Veränderungen, um einige Regeln zu folgen; zwei Zahlen in einer fortlaufenden Liste von ganzen Zahlen Swapping reduziert immer die Summe von einer Höhe befestigt, die ihren Abstand voneinander verbunden zu sein scheint (dh Swapping 1 und 3 oder 2 und 4 die gleiche Wirkung haben). Dies war nur von einem kleinen rumgespielt, aber die Idee ist, dass es ein Maximum, ein Minimum, und wenn einiger-vorgegebenem-Wert zwischen ihnen ist, gibt es Möglichkeiten, die Permutationen zu zählen, die das möglich machen (obwohl, wenn die Liste ist nicht in gleichmäßigem Abstand, dann gibt es nicht. Nun ja, nicht dass ich wüsste. Wenn l2 (1 2 4 5) Swapping 1 2 und 2 4 würden unterschiedliche Auswirkungen haben)

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow