Christophides Heuristik
Results 1 to 6 of 6
  1. #1
    Calida's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Posts
    128
    Thanks
    6
    Thanked 0 Times in 0 Posts

    Christophides Heuristik

    Ich habe noch ein paar Fragen zur Chridtopides-Heuristik

    Aus den Prüfungsangaben vom 19.01.2001 habe ich folgende Angaben:

    Angabe

    Daraus ist die Christophides Heurisik angewendet werden.
    Ich würde nun hergehen und mit Union Find einen Minimalen Spannbaum aufzeichnen. Der schaut dann so aus

    MST

    Nun ist die Frage, wie genau komme ich auf meine Knotenpaare. Mittels Perfekt Matching muss ich ja den Knoten mit ungeradem Grad einen eindeutige Partner zuordnen oder?
    Kann ich sie da bekiebig verbinden? z.b. ec und ad oder ad und ab, cb?
    Das mach ich ja nur damit ich eine Eulertour finden kann?
    Und vor allem wenn ich das habe wie kommen ich dann auf den Lösungsgrafen. Leider ist das Skriptum da nicht hilfreich. Schon alleine Deshalb weil die Kanten der Graphen nicht gewichtet sind.

    Ich hoffe ihr könnt mir weiterhelfen. Vielen Dank
    Last edited by Calida; 30-09-2002 at 12:44.
    Ich gehe jetzt ein Byte trinken. Das sind acht Bit.

  2. #2
    Wings-of-Glory's Avatar
    Title
    CO-Administrator
    Join Date
    Jan 2002
    Posts
    4,001
    Thanks
    347
    Thanked 504 Times in 266 Posts

    Re: Christophides Heuristik

    die bilder sind nicht zu sehn. tripod erlaubt wohl "fremden" webseiten nicht auf die bilder zuzugreifen. am besten du ersetzt den IMG-tag mit dem URL-Tag... oder noch besser: uni-account verwenden.
    ======================
    Original geschrieben von Calida
    Ich habe noch ein paar Fragen zur Chridtopides-Heuristik

    Aus den Prüfungsangaben vom 19.01.2001 habe ich folgende Angaben:

    http://reinhardtmuehlwerth.tripod.com/forum.bmp


    Daraus ist die Christophides Heurisik angewendet werden.
    Ich würde nun hergehen und mit Union Find einen Minimalen Spannbaum aufzeichnen. Der schaut dann so aus

    http://reinhardtmuehlwerth.tripod.com/Forum_MST.bmp

    Nun ist die Frage, wie genau komme ich auf meine Knotenpaare. Mittels Perfekt Matching muss ich ja den Knoten mit ungeradem Grad einen eindeutige Partner zuordnen oder?
    Kann ich sie da bekiebig verbinden? z.b. ec und ad oder ad und ab, cb?
    Das mach ich ja nur damit ich eine Eulertour finden kann?
    Und vor allem wenn ich das habe wie kommen ich dann auf den Lösungsgrafen. Leider ist das Skriptum da nicht hilfreich. Schon alleine Deshalb weil die Kanten der Graphen nicht gewichtet sind.

    Ich hoffe ihr könnt mir weiterhelfen. Vielen Dank
    Last edited by Wings-of-Glory; 30-09-2002 at 09:56.

  3. #3
    Calida's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Posts
    128
    Thanks
    6
    Thanked 0 Times in 0 Posts
    Was für einen Uni Account?

    Aber es geht leider nicht also werde ich die Files mal Anhängen.
    Attached Files Attached Files
    Last edited by Calida; 30-09-2002 at 12:49.
    Ich gehe jetzt ein Byte trinken. Das sind acht Bit.

  4. #4
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    @uni-account:

    du bekommst von der Uni 100MB webspace, zugänglich per SSH (=secure shell, so eine art sichereres FTP bzw. Telnet), client für windows gibts u.a. auf gd.tuwien.ac.at zum download (oder im Google nach "PuTTY" suchen.

    username: e1234567
    pass: deinpasswort
    server: stud3 bzw. stud4.tuwien.ac.at
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  5. #5
    Calida's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Posts
    128
    Thanks
    6
    Thanked 0 Times in 0 Posts
    Danke für die Information. Fast schon beeindruckend was mir die Uni alles gibt
    Also eines von zwei Themen ist dann geklärt
    Ich gehe jetzt ein Byte trinken. Das sind acht Bit.

  6. #6

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Perfect Matching bedeutet, dass man jedem Knoten mit ungeradem Grad (deren Anzahl ja immer gerade ist), genau einen anderen Knoten mit ungeradem Grad zuordnet. Dabei muss das Gesamtgewicht, der hinzugefuegten Kanten minimal sein.

    Wenn man die Knoten aus dem Beispiel "Zeilenweise" von links nach rechts numeriert, haben die Knoten 1, 2, 4 und 5 ungeraden Grad. Das heiszt man koennte folgende Paare bilden:

    - (1, 2) und (4, 5): Gesamtgewicht 36 + 54 = 90
    - (1, 4) und (2, 5): Gesamtgewicht 36 + 50 = 86
    - (1, 5) und (2, 4): Gesamtgewicht 71 + 51 =122

    Man sieht also, dass es am billigsten ist, wenn man die Kanten (1, 4) und (2, 5) hinzufuegt.

    Danach hat jeder Knoten einen geraden Grad -> es existiert ein euler'scher Kreis.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •