Frage zu Algorithmus: "Finde ähnlichste Paare"

[parrybear]

Frage: Bei den Listen

1 7
6 9

Ist die Lösung 7-6, 1-9 oder 1-6, 7-9?

Für beide Fälle gibt es bessere Ansätze wie deiner, aber ich mache mir nicht die Mühe, beide sauber aufzuschreiben.

[happystudent]

parrybear schrieb:

Frage: Bei den Listen

1 7
6 9

Ist die Lösung 7-6, 1-9 oder 1-6, 7-9?

Meinst du die Listen jetzt vertikal oder horizontal gelesen? Ich gehe mal von horizontal aus, also

a = 1, 7
b = 6, 9

Lösung wäre dann entsprechend 7-6 und 1-9, also

c = 1, -8

parrybear schrieb:

Für beide Fälle gibt es bessere Ansätze wie deiner, aber ich mache mir nicht die Mühe, beide sauber aufzuschreiben.

Ok, und unsauber?
Komplexität ist ja momentan ungefähr O(n^3) (a und b sind meistens ziemlich gleich lang)... wäre schön wenn man das irgendwie drücken könnte.

[parrybear]

Ok, dann also greedy die besten Paare suchen.

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

std::vector<int> most_common_pairs(std::vector<int> a, std::vector<int> b)
{
  std::vector<std::tuple<int, std::size_t, std::size_t>> pairs;
  for (std::size_t i=0; i<a.size(); ++i)
    for (std::size_t j=0; j<b.size(); ++j)
      pairs.emplace_back(std::abs(a[i]-b[j]), i, j);
  std::sort(pairs.begin(), pairs.end());
  std::vector<bool> used_a(a.size());
  std::vector<bool> used_b(b.size());
  std::vector<int> result;
  for (auto& t : pairs) {
    int d, i, j;
    std::tie(d, i, j) = t;
    if (!used_a[i] && !used_b[j]) {
      result.push_back(d);
      used_a[i] = used_b[j] = true;
    }
  }
  return result;
}

Laufzeit ist O(n^2 log n).

Geht vielleicht noch besser, aber vielleicht reicht das ja schon?

[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).