Optimierung kartesische Anfragen mit affin Kosten

StackOverflow https://stackoverflow.com/questions/1403933

Frage

Ich habe eine Anfrage Kostenoptimierung, die ich weiß nicht, wie wenn es Literatur. Es ist ein bisschen schwer zu erklären, so dass ich entschuldige mich im Voraus für die Länge der Frage.

Es ist ein Server ich zugreife, das funktioniert so:

  • wird eine Anforderung an Datensätzen (r1, ... rn) hergestellt und Felder (f1, ... fp)
  • Sie können nur fordern das kartesische Produkt (r1, ..., rp) x (f1, ... fp)
  • Die Kosten (Zeit und Geld) mit einer solchen Anforderung zugeordnet ist affin in der Größe der Anfrage:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

Ohne Beschränkung der Allgemeinheit (nur durch Normalisieren), können wir diese b=1 annehmen, so sind die Kosten:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

  • Ich brauche nur eine Teilmenge von Paaren (r1, f(r1)), ... (rk, f(rk)) zu beantragen, eine Anforderung, die von den Benutzern kommt. Mein Programm fungiert als Vermittler zwischen dem Nutzer und dem Server (der extern ist). Ich habe viele Anfragen wie diese, die kommen in (Zehntausende pro Tag).

Graphisch können wir daran denken als n x p Sparse Matrix, für die ich die Nicht-Null-Werte mit einem rechteckigen Submatrix abdecken will: 

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

Mit:

  • die Anzahl der Untermatrizen wegen der konstant Kosten vernünftig gehalten werden
  • alle 'x' innerhalb einer Submatrix liegen muss
  • die Gesamtfläche bedeckt darf nicht zu groß sein, da der linear Kosten

Ich nenne g die Kargheit Koeffizient meines Problems (Anzahl der benötigten Paare über insgesamt mögliche Paare, g = k / (n * p). I die Koeffizienten a kennen.

Es gibt einige offensichtliche Beobachtungen:

  • wenn ein klein ist, ist die beste Lösung, jedes (record, Feld) Paar unabhängig, und die Gesamtkosten zu verlangen: k * (a + 1) = g * n * p * (a + 1)
  • , wenn ein groß ist, ist die beste Lösung, um das ganze cartesianischen Produkt, und die Gesamtkosten zu verlangen: a + n * p
  • die zweite Lösung ist besser, sobald g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
  • natürlich die Aufträge in den cartesianischen Produkten sind unwichtig, so kann ich die Zeilen und die Spalten meiner Matrix transponieren, um es zu machen leicht abdeckbar, zum Beispiel: 
   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

als neu geordnet werden 

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

Und es ist eine optimale Lösung, die (f1,f3) x (r1,r3) + (f2) x (r2) ist anfordern

  • all Lösungen Versuch und für die niedriger Kosten suchen, ist keine Option, da die Kombinatorik explodieren: 
for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

so ich bin für eine Näherungslösung. Ich habe bereits eine Art von Greedy-Algorithmus, der eine Abdeckung einer Matrix gegeben findet (es beginnt mit einheitlichen Zellen verschmilzt sie dann, wenn der Anteil der leeren Zelle in der Zusammenführung unter einem gewissen Schwellenwert liegt).

Um ein paar Zahlen in den Köpfen zu setzen, ist mein n irgendwo zwischen 1 und 1000, und mein p irgendwo zwischen 1 und 200. Das Abstrahlverhalten ist wirklich ‚blockartig‘, da die Datensätze, für die in den Klassen kommen die gefragt Felder ähnlich sind . Leider kann ich nicht die Klasse eines Datensatz zugreifen ...

Frage 1 : Hat jemand eine Idee, eine kluge Vereinfachung oder eine Referenz für ein Papier, das nützlich sein könnte? Da ich viele Wünsche haben, einen Algorithmus, der auch im Durchschnitt arbeitet ist das, was ich suche (aber ich kann es sich nicht leisten, sehr schlecht auf einigen Extremfall zu arbeiten, zum Beispiel die ganze anfordernden Matrix, wenn n und p ist groß, und die Anforderung ist in der Tat recht spärlich).

Frage 2 : In der Tat, das Problem noch komplizierter ist: die Kosten in der Tat eher wie die Form: a + n * (p^b) + c * n' * p', wobei b eine Konstante <1 (einmal ein Datensatz für ein gefragt Feld, ist es nicht zu teuer für andere Felder zu fragen) und n' * p' = n * p * (1 - g) ist die Anzahl der Zellen ich will nicht verlangen (weil sie ungültig sind, und es gibt eine zusätzliche Gebühr für ungültig Dinge in anfordern). Ich kann nicht einmal von einer schnellen Lösung für dieses Problem träumen, aber immer noch ... jemand eine Idee?

War es hilfreich?

Lösung

die Untermatrizen Auswahl der gewünschten Werte zu decken ist eine Form des gesetzt Problem abdeckt und daher NP vollständig. Ihr Problem fügt dieses bereits schwer Problem, dass die Kosten der Sätze unterscheiden.

Dass Sie erlauben die Zeilen und Spalten permutieren ist nicht so ein großes Problem, weil Sie gerade nicht angeschlossen Untermatrizen betrachten können. Row ein, Spalten vier bis sieben und Reihe fünf, Säulen vier zwei sieben sind ein gültiger Satz, weil Sie gerade Reihe zwei tauschen können und die Reihe fünf und erhalten die angeschlossenen Submatrix Zeile eins, Spalte vier zwei Zeile, Spalte sieben. Natürlich wird dies einige Einschränkungen hinzufügen - nicht alle Sätze unter allen Permutationen gültig sind -. Aber ich glaube nicht, das ist das größte Problem

Der Wikipedia-Artikel gibt die Nichtapproximierbarkeitsresultate, dass das Problem nicht besser als mit einem Faktor 0.5 * log2(n) in Polynomialzeit gelöst werden, wo n die Anzahl der Sätze ist. In Ihrem Fall 2^(n * p) ist eine (recht pessimistisch) Ober für die Anzahl der Sätze gebunden und ergibt, dass Sie nur eine Lösung bis zu einem Faktor von 0.5 * n * p in Polynomzeit finden (neben N = NP und ignoriert die unterschiedlichen Kosten).

Ein optimistische untere Schranke für die Anzahl von Sätzen Permutationen von Zeilen und Spalten zu ignorieren, ist 0.5 * n^2 * p^2 einen viel besseren Faktor log2(n) + log2(p) - 0.5 ergibt. In der Folge erwarten Sie können nur eine Lösung in Ihrem schlimmsten Fall von n = 1000 zu finden und zu einem Faktor von etwa p = 200 im optimistischen Fall und bis zu einem Faktor von etwa 17 im pessimistischen Fall 100.000 oben (immer noch die unterschiedlich Kosten zu ignorieren).

Also das Beste, was Sie tun können, ist einen heuristischen Algorithmus zu verwenden (der Wikipedia-Artikel erwähnt einen fast optimalen Greedy-Algorithmus) und akzeptiert, dass es so sein wird, wo der Algorithmus führt (sehr) schlecht. Oder Sie den anderen Weg zu gehen und einen Optimierungsalgorithmus verwenden und versuchen, eine gute Lösung zu finden, mehr Zeit verwenden. In diesem Fall würde vorschlagen, ich A * Suche zu verwenden versuchen.

Andere Tipps

Ich bin sicher, es gibt einen wirklich guten Algorithmus für diese irgendwo da draußen, aber hier sind meine eigenen intuitiven Ideen:

  1. Toss-some-Rechtecke Ansatz:

    • Bestimmen Sie eine "grob optimal" Rechteck Größe basierend auf a .
    • Legen Sie diese Rechtecken (vielleicht zufällig) über die erforderlichen Punkt, bis alle Punkte abgedeckt werden.
    • Geben Sie nun jedes Rechteck nehmen und es so weit wie möglich schrumpfen, ohne zu „verlieren“, um alle Datenpunkte.
    • Finden Rechtecke nahe beieinander und entscheiden, ob die Kombination von ihnen billiger wären als sie getrennt zu halten.

  2. Grow

    • mit jedem Punkt in seinem eigenen 1x1 Rechteck Start.
    • Suchen Sie alle Rechtecke innerhalb von n Zeilen / Spalten (wobei n auf basieren a ); sehen, wenn Sie sie in ein Rechteck für keine Kosten kombinieren (oder negativ Kosten: D).
    • Wiederholen.

  3. Shrink

    • Starten Sie mit einem großen Rechteck aus, dass alle Punkte abdeckt.
    • Suchen Sie nach einem Unter Rechteck, das ein Paar Seiten mit dem groß man teilt, enthält aber nur sehr wenige Punkte.
    • es aus den großen einem Schnitt, zwei kleinere Rechtecken zu erzeugen.
    • Wiederholen.

  4. Quad

    • Teilen Sie die Ebene in vier Rechtecke. Für jeden diesen finden Sie, wenn Sie durch Rekursion weiter ein besser Kosten bekommen, oder nur durch das gesamte Rechteck mit.
    • Geben Sie nun Ihre Rechtecke und sehen, ob Sie einen von ihnen mit wenig / keine Kosten zusammenführen können. \

Auch: beachten , dass manchmal ist es besser, zwei zu haben, überlappende Rechtecken als ein großes Rechteck, das ein Ober von ihnen. Z.B. der Fall, wenn zwei Rechtecken nur in einer Ecke überlappen.

Ok, mein Verständnis der Frage hat sich geändert. Neue Ideen:

  • Speichern Sie jede Zeile als eine lange Bit-String. Und Paare von Bit-Strings zusammen und versuchen, Paare zu finden, die die Anzahl von 1-Bits zu maximieren. Wachsen diese Paare in größeren Gruppen (sortiert und versuchen, die wirklich Großen miteinander übereinstimmen). Dann eine Anforderung konstruieren, die die größte Gruppe treffen wird und dann mit all den Bits vergessen. Wiederholen, bis alles erledigt. Vielleicht wechselt von Zeilen in Spalten manchmal.

  • Geben Sie für alle Zeilen / Spalten mit Null oder nur in geringer Punkte in ihnen. „Löschen“, um sie vorübergehend. Nun betrachten Sie, was eine Aufforderung würde, die sie auslässt. Nun vielleicht eine der anderen Techniken anwenden, und befassen sich mit den ignorierten Zeilen / Spalten danach. Ein anderer Weg, um darüber zu denken ist. Deal mit dichten Punkten zuerst, und dann auf spärlich diejenigen bewegen

Da Ihre Werte spärlich sind, könnte es sein, dass viele Nutzer für Ähnliche Werte fragen? Ist das Caching eine Option in Ihrer Anwendung? Die Anforderungen könnten durch eine Hash-indiziert werden, die eine Funktion von (x, y) Position ist, so dass Sie leicht im Cache gespeicherten Sätze identifizieren, die in dem richtigen Bereich des Gitters fallen. Das Speichern im Cache-Sets in einem Baum, zum Beispiel, würde erlauben Sie mindestens gecached Subsets zu finden, der die Anfrage Bereich sehr schnell ab. Sie können dann auf die Teilmenge eine lineare Lookup, die klein ist.

würde ich die n Datensätze (Zeilen) und p-Felder (cols) überlegen in der Benutzeranforderung als n Punkte in p-dimensionalen Raum ({0,1} ^ p) mit dem eingestellten genannten ith wobei 1 iff es Koordinaten hat eine X und eine Hierarchie von Clustern zu identifizieren, mit dem gröbsten Cluster an der Wurzel einschließlich aller X. Für jeden Knoten in der Cluster-Hierarchie, prüfen, um ein Produkt, das die Säulen all benötigten umfasst (dies ist Zeilen (jeder Unterknoten) x cols (any Subknoten)). Dann wird aus dem Boden fest, bis, ob das Kind Beläge (Zahlung für die gesamte Abdeckung) verschmelzen, oder sie als separate Anfragen halten. (Die Abdeckungen sind nicht von zusammenhängenden Spalten, sondern genau die, die benötigt wird; das heißt denken Sie an einen Bit-Vektor)

ich mit Artelius einig, dass Produkt-Anfragen überlappende billiger sein könnte; mein hierarchischer Ansatz würde verbessert werden muß, dass zu übernehmen.

Ich habe ein bisschen daran gearbeitet, und hier ist eine offensichtliche, O (n ^ 3) gierig, Symmetriebrechung Algorithmus in Python-ähnlichen Pseudocode (Datensätze und Felder werden getrennt behandelt).

Die Idee ist trivial: Wir starten durch eine Anfrage pro Datensatz versucht, und wir tun, um die am meisten verdienen merge bis nichts mehr übrig ist würdig, zu verschmelzen. Diese algo hat den offensichtlichen Nachteil, dass es nicht erlaubt Anfragen überlappen, aber ich erwarte, dass es ganz gut auf realen Fall arbeiten (mit der a + n * (p^b) + c * n * p * (1 - g) Kostenfunktion): 

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

Das ist O (n3 * p), weil:

  • nach der Initialisierung beginnen wir mit n Anfragen
  • die while Schleife entfernt genau eine Anfrage aus dem Pool bei jeder Iteration.

  • der innere for Schleife iteriert auf dem (ni^2 - ni) / 2 verschiedene Paare von Anfragen, mit ni von n auf einen im schlimmsten Fall gehen (wenn wir alles in eine großen Anforderung merge).

    1. Kann mir jemand helfen, die sehr schlimmen Fällen des Algorithmus zeigt. Klingt es reasonnable, diese zu benutzen?
    2. Es ist O (n ^ 3), die viel zu teuer für große Eingänge ist. Jede Idee zu optimieren?

Vielen Dank im Voraus!

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top