6.4

[Friend or Foe ?]

r-Opt Laufzeit analysieren:

1) Wie groß ist Z?

Z ist die Menge aller r-elementigen Teilmengen von |T| (T ist die Anzahl der Kanten, wobei das in diesem Fall der vollständige Graph ist, also:
|T| = n * (n-1) / 2 (Bemerkung: n = |V|)

Menge aller r-Elementigen Teilmengen ist eine Kombination C(n,k) = (|T|! / ((|T|-k)! * k!)


2) Wieviele Möglichkeiten gibt es, um die r-Kanten wieder neu zu verbinden:
Naja, links (L) hat man r-Knoten, rechts (R) r-Knoten:
1. L kann mit r-Knoten R verbunden werden
2. L kann mit r-1 Knoten R verbunden werden
...
r. L kann nur mehr mit 1 Knoten R verbunden werden

= r! Möglichkeiten

=> Gesamtaufwand:

(so wie schreib ich das jetzt, irgendwie hätte ich jetzt schon gerne einen Bruchstrich ;)


Aufwand = ( (|T|! / ((|T|-r)! * r!) ) * r!)
= |T|! / (|T|-r)! .... das enspricht einer Variation V(n, r)
nachdem wir schon wissen, dass |T| rund n^2
= (n^2)! / ((n^2) - r)!
= (n^2) * (n^2 - 1) * ... * (n^2 - r + 1)
= (n^2) ^ r

Wenn man r = 3 ergibt sich somit ein Aufwand von (n^2)^3 = n^6
(Ich weiß, es steht im Skriptum anders, aber ich wüsste erstens nicht wie ich auf das n^3 kommen kann, bzw. hab ich auch den Vorlesungs-Chef (wie heißt er doch gleich) gefragt, der hat gemeint, dass die Argumentation richtig wäre

ich denke, dass im Skriptum (S. 155) ein Fehler ist, dass das nicht O(n^3) sondern O(|E|^3) heißen sollte...

[fuxi17]

Z ist die Menge aller r-elementigen Teilmengen von |T| (T ist die Anzahl der Kanten, wobei das in diesem Fall der vollständige Graph ist.

Ich glaube das ist nicht ganz korrekt. |T| ist nicht die Menge aller Kanten des vollständigen Graphen, sondern die Menge aller Kanten der Anfangslösung. Und das sind genau V(x) (Anzahl der Knoten).

Dann stimmt das auch mit dem Ergebnis aus dem Skript überein:

|T| = n und nicht n^2 ==> O(n^3)

[b_evil]

auch das is glaub ich noch nicht alles. die kanten dürfen nicht zusammenhängen und damit wirds kompliziert :\

[_logonoff_]

ad fof mit fuxi-korrektur: kann dem nur voll und ganz zustimmen (passt wunderbar ins mathe2-lernen ;-)

auch das is glaub ich noch nicht alles. die kanten dürfen nicht zusammenhängen und damit wirds kompliziert :\

was meinst du damit genau? wir haben die menge aller ungeordneten r-tupel aus T und multiplizieren deren kardinalität mit der anzahl der möglichkeiten der pfadkombination pro tupel - ich find schöner gehts gar nicht :-)

[b_evil]

ja, aber richtig isses trotzdem nicht:

wenn du 3 knoten nimmst, kannst du im prinzip nichts mit 2-opt optimieren, weil du nie 2 _nicht zusammenhängende_ kanten finden wirst. mit der methode von oben kommt man aber immerhin noch auf auf 3 kombinationen die falsch sind.
und bei r-opt wird das ganze nachher sogar noch ärger

[nonamenobody]

@fof: Das mit den Knoten links/rechts stimmt meiner Meinung nach nicht, denn du kannst auch Knoten "verkehrt herum" verbinden (bei 2-opt klarerweise nicht, aber höher schon), und zwar immer so, dass du keinen Kreis kriegst. Dann hast du noch einen Faktor 2^(r-1) und insgesamt 2^(r-1)(r-1)!. Im O ändert sich klarerweise dadurch nichts.

@b_evil: Es steht so bei der Beschreibung von r-opt im Skriptum: Sei Z die Menge aller r-elementigen Teilmengen von T. Somit ist das genau Binomial(n,r). Das ist wirklich anders als bei 2-opt.

lg
Philipp

[panzi]

wrum soll |T| rund n^2 sein? meinst damit das N aus dem bsp., also die anzahl der knoten. dann ist aber die anzahl der kanten in T gleich der anzahl der knoten, also genau N.