Loesungen
Results 1 to 24 of 24

Thread: Loesungen

  1. #1

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts

    SS 02 Loesungen

    Diese Woche wird es wieder etwas knapp, wieder wegen Datenmodellierung. Zur Zeit kann ich leider nur Loesungen fuer die ersten vier Beispiele anbieten.

    /edit 12.06.02:
    Die restlichen Loesungen werden sich wahrscheinlich bis zum Wochenende (nach der dm-Pruefung) verzoegern.

    /edit 16.06.02:
    - Fuer Aufgabe 5 habe ich zumindest einen sehr viel versprechenden Link: Knapsack with Branch and Bound. An einer eigenen Erklaerung arbeite ich noch.

    Errata fuer die aktuelle Version:
    - Beim 2ten Beispiel sollte man am Anfang des Pseudocodes die ddm initialisieren (s. nachfolgende posts).

    seit 11.06.02, 23:51 ist die Version 0.1 online unter uebung.html
    Last edited by yrucrem; 13-10-2002 at 04:14.

  2. #2
    H2O's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    294
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Trotzdem danke !

  3. #3
    LordOfTheBite's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    191
    Thanks
    2
    Thanked 0 Times in 0 Posts
    ich glaube, dass du da bei bsp 2 die angabe etwas zu leichtfertig interpretiert hast:
    die ddm soll benutzt werden, um die zusammenhangskomponente zu ermitteln

    deshalb musst du sie erstmal aufbauen

    Code:
    für alle v aus V {
     makeset(v);
    }
    für alle e aus E {
     //e = (ve; we) = Kante
     union( findset(ve), findset(we) );
    }
    gehört imho noch vor deinen code

    ansonsten hab ich alles so wie du

    peter
    Last edited by LordOfTheBite; 12-06-2002 at 11:04.

  4. #4
    dj_m.o.h.t.'s Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    428
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Thumbs up Tolle Arbeit!

    @yrucrem: Man muss dich mal wirklich sehr loben, dass du dir die Mühe machst, die ganzen Beispiele für AlgoDat, so wie ich die Mathefiles, zu tippen. Wirklich großes Lob an dich.

  5. #5

    Title
    Principal
    Join Date
    Mar 2002
    Location
    Wien, Innsbruck
    Posts
    79
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Exclamation WICHTIG

    Guten Morgen liebe Leute !

    Bekamm folgentes Email

    ...
    RAIDL: 6. UE Blatt
    Sehr geehrte Studierende,

    leider gab es eine Panne im Zusammenhang mit den Beispielen 8
    und 9 des 6. Übungsblatts, das nächste Woche in den
    Übungsgruppen behandelt wird: Diese beiden Beispiele beziehen
    sich auf das Kapitel "Evolutionäre Algorithmen", das in der
    Vorlesung aber auch erst nächste Woche gemacht wird.

    Natürlich war und ist es nicht unsere Absicht, Inhalte in der
    Übung durchzunehmen, die in der VO erst kommen.

    Bitte ignorieren Sie daher diese beiden Beispiele zunächst
    einmal einfach - sie werden in den Übungsgruppen nicht behandelt
    werden. (Jede/r in der Übungsgruppe Anwesende bekommt trotzdem 2
    Punkte für diese Beispiele gutgeschrieben, als ob sie richtig
    gelöst worden wären.) Die Beispiele werden anstatt dessen in den
    letzten beiden Vorlesungseinheiten kommende Woche besprochen.

    Wir bedauern diese kleine Panne.

    Viele Grüße und viel Erfolg bei der Prüfung!

    Günther Raidl
    (12. Jun 2002)
    .....

    na super -
    Hoffentlich gewinnt Brasilien

    sandrodwh

  6. #6

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    cool... 2 geschenkte punkte! =) *froi*
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  7. #7

    Title
    Principal
    Join Date
    Jun 2002
    Posts
    64
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Thumbs up blatt#6, aufgabe 4, small err0r

    yo!

    es hat sich offensichtlich ein kleiner schreibfehler eingeschlichen, die anzahl der meter der seile sollte, imho, 423 meter sein.
    auf die 6 seile komme ich auch, wenn ich nicht sortiere...es ist also nicht unbedingt notwendig..

    trotzdem thx für die lösungen.

    gibt es eigentlich schon welche für das binpacking-problem(#6) oder subset-sum-problem(#10)?

    greets,
    :-sub(zero)

  8. #8

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Mit den Loesungen wird's ziemlich knapp, naemlichg auch fuer mich, ich habe schon am Montag Uebung.

    ad Bsp 4 (First Fit): peinlicher Rechenfehler, natuerlich sind das nur 423 Meter
    /edit 18.06.02:
    Doch kein Rechenfehler, das fuenfte Seil muss man ja 2mal nehmen.

    ad Bsp 5 (Branch and Bound mit Rucksack Problem): Das wurde doch in einem Repetitorium durchbesprochen, habe ich gehoert. Koennte das nicht jemand zu erklaeren versuchen, der dort war, ich bin mir bei diesem Beispiel noch nicht ganz sicher.

    ad Bsp 6 (Bin Packing): Koennte man vielleicht aus den Kisten zufaellig 0 - 3 Elemente herausnehmen und danach wieder zufaellig auf die Kisten verteilen? Das wuerde sich meiner Meinung nach mit den zwei Bedingungen vertragen (obwohl mir diese "Loesung" irgendwie bloed vorkommt).
    /edit 16.06.02:
    Jup, ist bloed LordOfTheBite hat eine bessere Idee (siehe unten).

    ad Bsp 10 (subset sum): Das ist doch eigentlich ein Rucksack Problem bei dem bei jedem Gegenstand der Wert gleich seinem Gewicht ist. Vielleicht kann man das aehnlich machen wie das Rucksack Problem mit dynamischer Programmierung.
    /edit 16.06.02:
    Habe uebersehen, dass es garnicht exakt zu loesen ist, sondern nur mindestens eine Summe von T/2 herauskommen muss, es geht also auch viel einfacher (siehe nachfolgende Posts).

    Wie gesagt wird es diese Woche ziemlich knapp mit den Loesungen, ich bin froh, wenn ich selbst noch alle zusammen kriege bis zur Uebung. Eine fertige pdf-Datei wird es vermutlich erst Montag oder (eher) Dienstag abend geben.
    Last edited by yrucrem; 18-06-2002 at 01:00.

  9. #9
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ad bsp 2:

    nachdem man die ddm aufgebaut hat (wie LordOfTheBite) könnte man doch einfach folgendes schreiben:

    für i = 1 .... |S| {
    --- für alle Knoten z € Si {
    --------- markiert[z] = i;
    --- }
    }

    oder ?

    mfg, -z0nki-

  10. #10
    LordOfTheBite's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    191
    Thanks
    2
    Thanked 0 Times in 0 Posts
    meine lösung zu 6)

    wähle einen behälter k1 zufällig

    wähle darin einen gegenstand u1 zufällig

    suche den vollsten behälter k2 in den u1 noch passt

    wenn k2 nicht vorhanden, nimm neuen behälter (50% chance) oder starte algorithmus von vorne (50% chance)

    gebe u1 von k1 nach k2

    wenn k1 leer, lösche k1

    beweis erreichbarkeit:
    .)funktion terminiert immer
    .)jede mögliche gültige lösung kann erreicht werden

    beweis lokalität:
    nur 2 oder 3 (wenn einer neu) behälter werden bearbeitet, nur 1 gegenstand wird getauscht

    - kritik erwünscht

    peter

  11. #11
    LordOfTheBite's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    191
    Thanks
    2
    Thanked 0 Times in 0 Posts
    bsp 7:

    das perfect match hab ich hingeschätzt, bin mir ziemlich sicher dass es passt, nämlich:

    a,c
    b,d
    f,g

    mein pfad sieht dann folgendermaßen aus:

    f->d->b->c->a->e->g->f

    peter

  12. #12
    LordOfTheBite's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    191
    Thanks
    2
    Thanked 0 Times in 0 Posts
    ad bsp 10:
    das subset-sum hab ich auch so gelöst, nur ist mir der geniale beweis für die güte >=t/2 nicht eingefallen

    peter

  13. #13

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    57
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ 10

    1. wähle die ersten k Zahlen {a1...ak}, bis die Summe >T

    2. ist ak > T / 2 Ergebnis = { ak }

    3. ist ak < T / 2 Ergebnis = { a1...a(k-1) }

    Beweis folgt direkt aus 2. und 3.
    Last edited by PliniusSecundus; 16-06-2002 at 16:31.

  14. #14
    Georg's Avatar
    Title
    Master
    Join Date
    Mar 2002
    Posts
    162
    Thanks
    0
    Thanked 0 Times in 0 Posts

    kleiner Tippfehler

    ad Bsp 1:

    Glaube bei der Sortierung der Kanten hast Du i mit h vertauscht, und h weggelassen, weshalb sich am Ende auch ein kleiner Unterschied beim Hinzufügen ergibt...

    P.S.:
    @yrucrem: Man muss dich mal wirklich sehr loben, dass du dir die Mühe machst, die ganzen Beispiele für AlgoDat,..., zu tippen.
    Muss mich auch endlich mal für Deine genialen pdfs bedanken, sind eine grosse Hilfe!

  15. #15
    LordOfTheBite's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    191
    Thanks
    2
    Thanked 0 Times in 0 Posts
    Original geschrieben von PliniusSecundus
    @ 10

    1. wähle die ersten k Zahlen {a1...ak}, bis die Summe >T

    2. ist ak > T / 2 Ergebnis = { ak }

    3. ist ak < T / 2 Ergebnis = { a1...a(k-1) }

    Beweis folgt direkt aus 2. und 3.

    `


    und wenn die ersten zahlen die du erwischt größer sind als T, aber noch kleinere folgen würden ... ?

    bsp:

    T = 10

    20, 30, 9, 10


    -> du wählst 20 aus
    -> gibst mit 2) 20 als gültige lösung aus *gg*

    ich würde sie vorher zuerst aufsteigend sortieren, dann klappts auch

    und wenn k=1 dann musst du NULL ausgeben

    peter

  16. #16

    Title
    Master
    Join Date
    Apr 2002
    Posts
    112
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Bsp 7)
    LordOfTheBite: Habs genauso wie du. Sollte passen

    Bsp 6)
    Deine Nachbarschaftsfunktion hat meiner Meinung nach einen kleinen Haken. Was ist, wenn es keinen Gegenstand gibt, der noch irgendwo dazupasst, es aber trotzdem eine optimalere Lösung gibt? (Beispiel: Alle Gegenstände > 4, Freier Platz in allen Behältern <= 3. Ab einer gewissen Anzahl können diese Freiräume ausgefüllt werden bis ein Behälter wegfällt. Doch diese Tatsache wird von deinem Algorithmus nicht gefunden.)

    Deshalb glaube ich, dass folgender Ansatz besser ist:

    a) Wähle einen zufälligen Behälter k1.

    b) Wähle aus k1 einen zufälligen Gegenstand u1.

    c) Wähle einen zufälligen Behälter k2 (k2 != k1).

    d) Suche den größten Gegenstand in k2, der kleiner ist als k1.

    falls d) erfolglos, gehe zu a) sonst

    e) Ist die Differenz der beiden Gegenstand-Größen kleiner oder gleich dem freien Raum in k2, so tausche die beiden Gegenstände.

    sprich:
    u1 € k1 zufällig
    u2 € k2: für u2 < u1 und u2 >= x, für alle (x € k2) < u1
    wenn freier_platz >= u1 - u2 dann tausche u1 mit u2

    So habe ich eine optimalere Ausfüllung des zweiten Behälters gefunden. Irgendwann nach vielen Durchläufen müsste ich dann alle Behälter optimal ausgefüllt haben, da ja auch kleine Gegenstände als u1 gewählt werden und dann in einen anderen Behälter gegeben werden.

    Wie es LordOfTheBite so schön sagte: Kritik erwünscht

  17. #17
    SinusDiabolicus's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Wien
    Posts
    383
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von yrucrem
    ad Bsp 4 (First Fit): peinlicher Rechenfehler, natuerlich sind das nur 423 Meter
    ähm, 423 sinds doch nur wenn man das letzte seil nur einmal zählt, man braucht aber 2 davon, dann passt 519 wieder, oder bin ich jetzt ganz verwirrt? *gg*

  18. #18
    Megabit's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Location
    VIE / AUT
    Posts
    493
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja, 519 sollte stimmen
    "Die letzte Stimme, die man hört, bevor die Welt explodiert, wird die Stimme eines Experten sein, der sagt: 'Das ist technisch unmöglich!'" Peter Ustinov


  19. #19
    Georg's Avatar
    Title
    Master
    Join Date
    Mar 2002
    Posts
    162
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Talking

    ...und ich d8e schon jetzt versteh ich gar nix mehr...
    ja! 519!

  20. #20
    Georg's Avatar
    Title
    Master
    Join Date
    Mar 2002
    Posts
    162
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question ad Aufgabe 7

    also dieser christophides, d.h. mehr seine heuristik ist mir ziemlich unverständlich => ärgerlich, denn ich hab das gefühl das is gar nicht so schwer...

    vielleicht hat jemand die zeit/lust das ganze in einfache worte zu kleiden...

    thx!

  21. #21

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    ad Bsp 4 (First Fit): habe mich verwirren lassen, 519 stimmt.

    ad Christophides:

    Zuerst einen minimalen Spannbaum machen (z.B.: mit Kruskal). Dann fuer die Knoten mit ungeradem Grad ein sogenanntes "perfektes Matching" finden. Das bedeutet jedem der Knoten genau einen anderen Knoten zuordnen so dass die Kantengewichte die man dafuer braucht minimal sind. Dann hat man also die Knoten mit ungeradem Grad zu Paaren zusammengefasst und die entsprechenden Kante auch hinzugefuegt. Jetzt gibt es also keinen Knoten mehr mit ungeradem Grad (ein euler'scher Graph).

    Nun gibt man dem Graph eine Orientierung, ie. jeder Kante eine Richtung zuweisen, natuerlich so, dass man eine Rundtour machen kann.

    Dann beginnt man bei einem beliebigen Knoten und markiert ihn gleich als besucht. Man merkt sich den Knoten von dem man jetzt weggehen will, z.B.: in der variable v. Man folgt nun einer Kante zu einem Nachbarknoten. Ist dieser noch nicht markiert, fuegt man die Kante ueber die man gekommen ist, der Loesungsmenge hinzu und markiert den neu besuchten Knoten. Man laesst v auf diesen Knoten zeigen und beginnt wieder von vorne. Wenn man einen Knoten erreicht der bereits markiert ist, wird die Kante nicht hinzugefuegt, sondern man folgt der naechsten Kante bis man zu einem unmarkierten Knoten w (oder dem Startknoten) kommt. Hat man einen solchen gefunden fuegt man die Kante (v, w) hinzu. Falls w der Startknoten war, ist die Tour fertig.

    Ich hoffe das hat etwas geholfen. Die Loesungen fuer die Beispiele 5 bis 7 werden wohl leider nicht mehr in dieser Woche fertig werden. Ich habe gestern herausgefunden, dass ich morgen Projektmanagement Pruefung habe ;-). Sorry.
    Last edited by yrucrem; 18-06-2002 at 01:25.

  22. #22
    Georg's Avatar
    Title
    Master
    Join Date
    Mar 2002
    Posts
    162
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Vielen Dank! Hab ja gewusst, dass man das auch verständlich formulieren kann...

  23. #23

    Title
    Veteran
    Join Date
    Feb 2002
    Location
    Großebersdorf, im Norden von Wien
    Posts
    11
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Bsp. 6

    @Faceless

    Dein Algorithmus klingt ganz gut, aber ein Problem seh ich schon:
    Dein Algorithmus verringert nicht die Anzahl der Behälter. Die bleiben, da du nur vertauschst, immer gleich. Die Behälter sind zwar maximal ausgelasstet, aber im Prinzip wird die lösung ja nicht "besser" (nur weniger Behälter machen wirklich Sinn)

    oder überseh ich da was ?
    " woher soll ich wissen, was ich denke, bevor ich höre was ich sage?"
    --(Un)bekannt

  24. #24
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    noch zu bsp 10:

    wtf ist ein "polynomieller algorithmus" ?
    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

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
  •