Frage zu Algorithmus: "Finde ähnlichste Paare"

[xgrif]

Und was soll die Lösung bei

1 4
3 5

sein?

[happystudent]

xgrif schrieb:

Und was soll die Lösung bei

1 4
3 5

sein?

Optimalerweise 4-5 und 1-3, also

-1, -2

Mein Algorithmus macht das aber auch noch falsch merke ich gerade, das scheint noch komplizierter zu werden...

EDIT:

parrybear schrieb:

Mein Vorschlag wäre alle Paare generieren, sortieren und der Reihe nach durchgehen.

Erst jetzt gesehen, werd ich mir gleich mal anschauen, danke

[komplex]

Wieso ist der Greedy n^2 log n? Für mich ist der n^2...

[xgrif]

und warum bevorzugst du in parrybears beispiel die abstaende (1,-8) gegenueber der anderen loesung mit abstaenden (-2,-5)? die summe der absolut abstaende ist im zweiten fall (7) kleiner als im ersten (9), ebenso wie die summe der quadratischen abstaende (29 zu 65), die du im op mal erwaehnst.

was ist das genaue(!) guetekriterium, nach dem zwei potentielle loesungen verglichen werden sollen um die bessere loesung zu ermitteln?

[TGGC]

parrybears Idee geht wohl schon in die richtige Richtung, wenn du denn wirklich einen Algorithmus haben willst der greedy ist. Nur so ein Algorithmus wird nicht immer die Paare finden, die in der Summe am aehnlichsten sind. Mein Gefuehl sagt mir, das diese Aufgabe NP vollstaendig ist weil mir das dem TSP verwandt erscheint (Paare von Staedten suchen die geringen Abstand haben mit einer etwas anderen Randbedingung). Von daher waere die Frage erstmal ob du die beste Loesung brauchst oder eine die ihr nur nahe kommt.

[Jester]

Mein Gefühl sagt mir, dass Du da falsch liegst, da das ein Matching-Problem ist und diese polynomiell lösbar sind -- allerdings im Allgemeinen nicht mit einem einfachen Greedy-Verfahren. Der Hauptunterschied zum TSP ist, dass man hier nicht fordert, dass die ausgewählten Verbindungen (Paare) einen zusammenhängenden Graphen ergeben... und das macht alles leichter.

Hier dürfte der Fall deutlich einfacher sein: Beide Listen sortieren und dann die kleinere in die größere matchen mittels dynamischem Programm. Vorher mal irgendwann beweisen, dass wenn a<b in Liste A und c<d in Liste B, dass dann ac und bd besser ist als ad und bc, die Paare also in beiden Listen sortiert vorliegen. Das schränkt den Suchraum deutlich ein, sodass man sich eigentlich nur noch merken muss bis zu welchem Element der langen Liste man schon vorgerückt ist.

[TGGC]

Jester schrieb:

Der Hauptunterschied zum TSP ist, dass man hier nicht fordert, dass die ausgewählten Verbindungen (Paare) einen zusammenhängenden Graphen ergeben... und das macht alles leichter.

Ja, wenn man eine Methode findet, die zeigt, das der zusammenhaengene Graph nicht die beste Loesung sein wird.

[happystudent]

xgrif schrieb:

und warum bevorzugst du in parrybears beispiel die abstaende (1,-8) gegenueber der anderen loesung mit abstaenden (-2,-5)? die summe der absolut abstaende ist im zweiten fall (7) kleiner als im ersten (9), ebenso wie die summe der quadratischen abstaende (29 zu 65), die du im op mal erwaehnst.

Ja, das stimmt, dieses Problem hatte ich nicht bedacht...

Problem bei meinem jetzigen (und parrybears) Algorithmus ist, dass wenn es mehrere gleichgute Lösungen gibt es nicht egal ist welche man nimmt (wie in deinem Beispiel).

Das Ganze ist Teil einer Kostenfunktion für einen Optimierungsalgorithmus zur Auslegung von Bauteilen, deswegen ist mir das bis jetzt noch gar nicht aufgefallen (der Algorithmus optimiert schon, allerdings wahrscheinlich nicht so gut wie wenn der Algorithmus richtig wäre)...

Am besten wäre wohl wenn am Ende die Summe der Quadrate über den result vector minimal wäre. Allerdings darf ein einmal gebildetes Paar nicht weiter verwendet werden (sonst könnte man ja einfach alle Kombinationsmölichkeiten in O(n^2) erstellen und die n besten nehmen)... Weiß gerade nicht wie ich das lösen soll

[Jester]

TGGC schrieb:

Jester schrieb:

Der Hauptunterschied zum TSP ist, dass man hier nicht fordert, dass die ausgewählten Verbindungen (Paare) einen zusammenhängenden Graphen ergeben... und das macht alles leichter.

Ja, wenn man eine Methode findet, die zeigt, das der zusammenhaengene Graph nicht die beste Loesung sein wird.

Nein, es sagt niemand, dass die Lösung für ein einfacheres Problem nicht auch mal zufällig eine Lösung für ein schwierigeres Problem sein darf.

Hier tritt aber selbst dieser Fall nicht auf, da ja nur Paare gebildet werden und damit kein Knoten zweimal vorkommt -- also können auch keine Kreise entstehen.

[TGGC]

Jester schrieb:

Nein, es sagt niemand, dass die Lösung für ein einfacheres Problem nicht auch mal zufällig eine Lösung für ein schwierigeres Problem sein darf.

Ja, das stimmt. Ich hatte mir das so vorgestellt, das ich die Paare dann aneinanderhaenge und sich so ein Kreis ergibt, fuer den Fall das zufaelligerweise genau diese restlichen Kosten 0 waeren.

[Jester]

@happystudent: Versuch mal zu beweisen dass man Paare nicht verdrehen sollte. Also wenn ich a<b in Liste A und c<d in Liste B habe, dass dann die Paare ac und bd immer genauso gut oder besser als die Paarung ad und bc ist.

Wenn das gilt, löst es direkt das Problem wenn die Listen gleich lang sind, weil Du einfach nur sortieren musst und den kleinsten Eintrag aus A mit dem kleinsten Eintrag aus B paaren musst usw.

[happystudent]

Jester schrieb:

@happystudent: Versuch mal zu beweisen dass man Paare nicht verdrehen sollte. Also wenn ich a<b in Liste A und c<d in Liste B habe, dass dann die Paare ac und bd immer genauso gut oder besser als die Paarung ad und bc ist.

Ok. Sei

$a < b, c < d \text{ und } a,b,c,d \neq 0$

Dann folgt daraus für die Summe der Abstandsquadrate:

(a - c)^2 + (b - d)^2 \leq (a - d)^2 + (b - c)^2 \\ a^2 - 2ac + c^2 + b^2 - 2bd + d^2 \leq a^2 - 2ad + d^2 + b^2 - 2bc + c^2 \\ -2ac - 2bd \leq -2ad - 2bc \\ ac + bd \geq ad + bc \\ ac - ad \geq bc - bd \\ a(c -d) \geq b(c - d) \\ a \geq b \\

und damit ein Widerspruch zu unserer ursprünglichen Annahme dass a < b.
Die Bedingung ist somit nicht erfüllt und zwar für allgemeine a, b, c, d.

Hilft es vielleicht dass die vectoren streng monoton sind?

[Jester]

Und jetzt finde den Fehler. Tipp: was ist das Vorzeichen von (c-d)?

[happystudent]

Jester schrieb:

Und jetzt finde den Fehler. Tipp: was ist das Vorzeichen von (c-d)?

Hm, ungünstig ungeformt. Wie wärs damit:

\vdots \\ ac + bd \geq ad + bc \\ bd - ad \geq bc - ac \\ d(b - a) \geq c \underbrace{(b - a)}_{b - a > 0} \\ d \geq c\\

was widerum ein Widerspruch wäre, da c < d gefordert war.

[Nathan]

happystudent schrieb:

d \geq c\\
was widerum ein Widerspruch wäre, da c < d gefordert war.

Wenn c < d, ist d > c...

[Jester]

Wo genau findet sich der Widerspruch zwischen c<=d und c<d?

edit: mit anderen Worten, eigentlich hast Du die Aussage bewiesen. Es kommt nämlich eine Bedingung heraus, die nach Eingangsvoraussetzung erfüllt ist.

[happystudent]

Nathan schrieb:

Wenn c < d, ist d > c...

Jester schrieb:

Wo genau findet sich der Widerspruch zwischen c<=d und c<d?

edit: mit anderen Worten, eigentlich hast Du die Aussage bewiesen. Es kommt nämlich eine Bedingung heraus, die nach Eingangsvoraussetzung erfüllt ist.

Oh verdammt, ihr habt recht

Gut, dann ist das jetzt bewiesen, aber das bringt ja nur was bei gleichlangen Listen, richtig? Weil meistens sind die Listen halt unterschiedlich lang (die Länge ist zwar ungefähr gleich, aber fast nie identisch).

[xgrif]

Das bringt viel! Jetzt ist die Frage nur noch, welche Elemente du aus der langen Liste rausschmeißt. Welche Paare zusammen gehören ergibt sich dann von ganz alleine. Und die Aufgabe ist ratz fatz mit einem dynamischen Programm gelöst.

OE sei A die längere Liste. Entweder A[1] spielt mit, und (A[1], B[1]) ist das erste Paar und du musst nur noch den Rest A[2...] und B[2...] prüfen, oder A[1] fliegt raus und du vergleichst A[2...] gegen B[1...]. Das ganze bricht ab, wenn A und B gleich lang sind, dann müssen alle Paare rein. Da in jedem Schritt A ein Element kürzer wird, bricht der Algorithmus auch schnell ab.

happystudent schrieb:

Das Ganze ist Teil einer Kostenfunktion für einen Optimierungsalgorithmus [...]

Meinst du nicht, dass die Kostenfunktion ein wesentlicher Teil des Problems ist, und du genau mit der mal rausrücken solltest? Und zwar am besten schon im Anfangspost!

Obiger Algorithmus funktioniert auch nur mit der Summe der quadratischen Abstände als Kostenfunktion, denn du hast ja eine Eigenschaft der quadratischen Abstände in deinem letzten Beweis genutzt, um zu diesem Algorithmus zu kommen.

Wenn du jetzt endlich mal mit der Kostenfunktion rausrückst und es dann nicht die Summe der quadratischen Abstände ist, war u. U. bisher alles für die Katz.

[happystudent]

xgrif schrieb:

Wenn du jetzt endlich mal mit der Kostenfunktion rausrückst und es dann nicht die Summe der quadratischen Abstände ist, war u. U. bisher alles für die Katz.

Naja, also der Algorithmus ist eigentlich schon die Kostenfunktion. Man hat halt zwei unterschiedlich lange Vektoren, die möglichst "ähnlich" zueinander gemacht werden sollen.

Da sie unterschiedlich lang sind, läuft das in zwei Schritten: Zuerst werden die ähnlichsten Paare bestimmt. Das ergibt dann zwei gleich lange Vektoren, die auf klassische Art und Weise verglichen werden können und einen Kostenwert x liefern.

Im zweiten Schritt wird dann mittels einer Heuristik noch ein zusätzlicher Kostenwert y bestimmt, der berücksichtigt wie unterschiedlich die Länge der beiden Vektoren ist. Die Gesamtkosten ergeben sich dann als z = x + y. Am besten wäre nämlich, wenn die beiden Vektoren genau gleich lang wären und identische Einträge hätten.

Es handelt sich dabei um eine physikalisches Model, das so parametriert werden soll, dass die von ihm produzierten Outputs einem vom Benutzer vorgegebenen Wunsch-Output entsprechen (bei gleichem Input). Im Prinzip sieht das so aus:

input = user input 1 // Model input
x_set = user input 2 // Gewünschter Model output

while (error is big)
    p = determine new parameters // Irgendeine Optimierungsmethode
    x_cur = ModelFunction(p, input) // Output des Models mit den aktuellen Parametern p
    error = CalculateErrorBetween(x_cur, x_set) // Fehlerberechnung
endwhile

Problem ist eben dass die Länge des Outputs des Modells (also die Länge des Vektors x_cur ) abhängig von den Parametern p ist.

Mit der oben beschriebenen Methode funktioniert es in einigen Fällen schon ziemlich gut, in anderen aber schlecht bis gar nicht. Außerdem ist die Laufzeit sehr hoch.

So, ich hoffe das waren dann alle relevanten Infos. Letztendlich sollte das Grundproblem sich dadurch aber nicht ändern?

[xgrif]

happystudent schrieb:

Das ergibt dann zwei gleich lange Vektoren, die auf klassische Art und Weise verglichen werden können

Und warum sagst du nicht einfach, wie du sie genau vergleichst? Das ist immerhin das entscheidende Kriterium und macht den Unterschied aus, ob der Algorithmus passt oder nicht. Ich hab zwar eine Kristallkugel, die mir zu "auf klassische Art und Weise" ein trübes Bild liefert, aber das tut doch nun wirklich nicht Not hier auf so nebulöse Angaben aufzubauen.

Im zweiten Schritt wird dann mittels einer Heuristik noch ein zusätzlicher Kostenwert y bestimmt, der berücksichtigt wie unterschiedlich die Länge der beiden Vektoren ist.

Eine Heuristik wovon? Von dem Kostenwert der unterschiedlich langen Listen? Wenn du direkt an den ran kommst, wozu der Umweg?

Mit der oben beschriebenen Methode funktioniert es in einigen Fällen schon ziemlich gut, in anderen aber schlecht bis gar nicht.

Was kommt bei einem Beispiel raus, bei dem es nicht gut funktioniert? Und woher weißt du, dass es nicht gut funktioniert hat?