rucksackproblem (laufzeit)
Results 1 to 5 of 5
  1. #1
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts

    rucksackproblem (laufzeit)

    zum 0/1-Rucksackproblem:

    wird eigentlich angenommen dass der Wertebereich der Gewichte beschränkt ist (sowie wie im Rep. nur ganze Zahlen ??) Bei der Wahl beliebig genauer Real-Zahl (für die Gewichte) ist G.'s Argumentation über die Laufzeit von

    F1: Gegenständen * auftretende Gewichtswerte von Teilmengen

    ziehmlich wirkungslos (zur Erinnerung: das war das Tabellenbeispiel).
    Wähle ich die Gewichte als irrationale Zahlen (also sodass alle möglichen Permutationen unterschiedliches Gewicht haben) und setzte die Kosten der Gegenstände so, dass alle Gegenstände den Nutzen ( edit: zur Erinnerung: Nutzen=Gewinn pro Gewichtseinheit !! ) von c haben, läuft die lineare Optimierung exponentiell.

    Meiner Meinung nach müßte auch das Branch&Bound hiermit Probleme haben ( da die Sortierung keine Information beinhaltet, müßte die upper-bound Funktion an Wirkung verlieren), ganz Sicher bin ich mir hier allerdings nicht.


    Heißt dass alles jetzt, dass:
    a)Nur Integerwerte beim 0/1 Problem erlaubt sind.
    b)Nur Werte mit einer bestimmten Genauigkeit.
    c) Dass die Laufzeit durch F1 beschränkt ist, wobei die möglichen Gewichtswerte für jede Probleminstanz neu zu bestimmen sind ???

    btw: rep war nett, nur ich hätt lieber simulated annealing oder evolutionäre gmacht, das 0/1 hatten wir eh schon tausend mal bei den Übungen.

    MfG
    Last edited by shabby; 20-06-2002 at 11:05.

  2. #2

    Title
    Böser Wolf
    Join Date
    May 2002
    Location
    Institut 186
    Posts
    814
    Thanks
    0
    Thanked 0 Times in 0 Posts
    > wird eigentlich angenommen dass der
    > Wertebereich der Gewichte beschränkt ist > (sowie wie im Rep. nur ganze Zahlen ??)

    Nein.

    > Bei der Wahl beliebig genauer Real-Zahl > (für die Gewichte) ist G.'s Argumentation
    > über die Laufzeit von
    >
    > F1: Gegenständen * auftretende Gewichtswerte von Teilmengen
    >
    > ziehmlich wirkungslos

    Nein. Solange du nur mit endlich vielen Gegenständen arbeitest, wirst du immer einen gewissen "Mindestabstand" zwischen zwei Gewichten bzw. Kombinationen von Gewichten haben -- er ist vielleicht sehr klein, aber er existiert. Und ob dieser Mindestabstand jetzt 1 ist (so wie im Beispiel gestern) oder 0.01 oder sonstwas, ist für die Ordnung der Laufzeit im Endeffekt egal.

    Den formalen Beweis für die Polynomialität (geiles Wort!) dieses und anderer Verfahren kannst du im Garey/Johnson nachlesen.

    > Wähle ich die Gewichte als irrationale
    > Zahlen (also sodass alle möglichen
    > Permutationen unterschiedliches Gewicht
    > haben) und setzte die Kosten der
    > Gegenstände so, dass alle Gegenstände > den Nutzen von 1 haben, läuft die lineare > Optimierung exponentiell.

    Nein, im Gegenteil. Dieser Speziellfall ist sogar in O(n log n) exakt lösbar.

    > btw: rep war nett, nur ich hätt lieber
    > simulated annealing oder evolutionäre
    > gmacht, das 0/1 hatten wir eh schon
    > tausend mal bei den Übungen.

    Ich habe die Sachen erklärt, nach denen meiner Kenntnis nach am meisten Nachfrage bestanden hat. Zu dynamischem Programmieren und Branch&Bound habe ich eine Tonne von "Bitte bitte"-Mails bekommen, für Annealing und Genetik hat sich irgednwie keiner interessiert.

    Grüße,
    Georg

  3. #3
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    Danke
    Aber

    >> Wähle ich die Gewichte als irrationale
    >> Zahlen (also sodass alle möglichen
    >> Permutationen unterschiedliches Gewicht
    >> haben) und setzte die Kosten der
    >> Gegenstände so, dass alle Gegenstände
    >> den Nutzen von 1 haben, läuft die lineare
    >> Optimierung exponentiell.
    > Nein, im Gegenteil. Dieser Speziellfall ist sogar in O(n log > n) exakt lösbar.

    ich möcht wirklich nicht streiten und steh vielleicht auf der Leitung aber hier ein Gegenbeispiel:

    Gegenstände seien A..
    Gewichte seien Wurzeln aus Primzahlen
    Gewinn sei doppeltes Gewicht
    Kosten seien also 2 für alle Gegenstände.

    Für die Cut-Bedingunen der linearen Optimierung gilt:
    Cut bei gleichem Gewicht: Kann nie auftreten (irrationale Zahlen !!!)
    Cut bei gleichem Gewinn: Ebenfalls nicht möglich (sic!)
    Auch die anderen zwei Cut-Bedingungen können nie erfüllt sein, denn für alle Permutationen I und J:
    Der Nutzen ist gleich, also folgt aus geringerem Gewicht auch geringerer Gewinn -> kein einziger Cut.

    Deshalb eskaliert die Liste/der Baum exponentiell

    Vielleicht hab ich mich beim ersten Mal einfach schlecht ausgedrückt.

    In dem von mir angesprochenen Fall wird aus dem 0/1 Rucksackproblem ein Art Bin-Packing: Räum soviel Gegenstände wie Möglich in den Rucksack, der Wert kann im Prinzip IGNORIERT werden.
    Last edited by shabby; 20-06-2002 at 11:07.

  4. #4
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    ach ja, ein ganz nettes online-skript hab ich auch noch gefunden:

    http://or-online.informatik.fh-augsburg.de/

  5. #5
    RoadRash's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Oberwart / Wien
    Posts
    274
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hab das Thema vom UE-Forum ins VO-Forum verschoben, da das dort besser aufgehoben sein sollte...

    So long,

    RoadRash
    Ceterum censeo, carthaginem esse delendam.

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
  •