/effiziente/ Lösung??

Ogridi
Neuling
Neuling
Beiträge: 2
Registriert: 28. Apr 2007 22:01
Kontaktdaten:

/effiziente/ Lösung??

Beitrag von Ogridi »

Hi!

Nach einer geschlagenen Zeit auf der Suche nach einer geeigneten Lösung frage ich mich doch langsam, ob es bei dieser Praktikumsaufgabe (oder vielleicht sogar bei allen?) wirklich darum geht, einen effizienten Weg zur Problemlösung zu finden oder ob wir es nur irgendwie (ok, meinetwegen in endlicher Zeit ;)) lösen sollen.

Würde mich sehr freuen, wenn sich diese Frage schnell beantworten ließe. Vielen Dank!

Ogridi

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Beitrag von Maradatscha »

das ding hat ne komplexität von 2^n
wat weiss ich ob du das effizient nennst, es gibt wohl mit ein paar vorbedingungen eine etwas bessere lösung, aber ich weiss nicht ob die hier gewollt ist

RomanSoldier
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 220
Registriert: 1. Dez 2005 20:32

Beitrag von RomanSoldier »

Ogridi kannst ja mal versuche zu beweisen, dass Knapsack in der Klasse P liegt - viel Spaß!

Ogridi
Neuling
Neuling
Beiträge: 2
Registriert: 28. Apr 2007 22:01
Kontaktdaten:

Beitrag von Ogridi »

Vielen Dank für den Spaß dabei...

Wenn Ihr das nächste mal ne triviale Lösung hören wollt (um das schöne Wort mal wieder zu benutzen), sagt das doch bitte gleich. Dann macht man sich zumindest nicht ewig Gedanken, wie das funktioniert, bzw. wo der Trick liegt.

Im übrigen /gibt/ es effizientere Algorithmen zu diesem Problem (s. z.B. Wikipedia). Ich hab nur nicht den blassesten Schimmer, wie sie funktionieren und ehrlich gesagt auch atm keinen Elan mehr, das herauszufinden.

Schönen Abend noch,
Ogridi

Benutzeravatar
unschuldslamm
Kernelcompilierer
Kernelcompilierer
Beiträge: 422
Registriert: 28. Okt 2004 09:24

Re: /effiziente/ Lösung??

Beitrag von unschuldslamm »

Ogridi hat geschrieben:Hi!

Nach einer geschlagenen Zeit auf der Suche nach einer geeigneten Lösung frage ich mich doch langsam, ob es bei dieser Praktikumsaufgabe (oder vielleicht sogar bei allen?) wirklich darum geht, einen effizienten Weg zur Problemlösung zu finden oder ob wir es nur irgendwie (ok, meinetwegen in endlicher Zeit ;)) lösen sollen.

Würde mich sehr freuen, wenn sich diese Frage schnell beantworten ließe. Vielen Dank!

Ogridi
Im Praktikum werden selbstverständlich nur solche Sachen abgeprüft, die mit bisher in der Vorlesung behandelten Stoff lösbar sind!
Wurden bisher (1. Woche) spezielle Algorithmen oder Datenstrukturen behandelt?
Was wurde hingegen in der 1. Vorlesung thematisiert?

...
Maybe in Ohio, but not in America!

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Der Algorithmus auf Wikipedia benutzt Dynamic Programming. Der "Trick" hierbei ist mal wieder, das Problem in kleinere Teilprobleme zu zerlegen und hieraus dann die Lösung zu konstruieren. Wenn n die Objektanzahl ist und B die Rucksackgröße, dann ist das Ausgangsproblem, mit n Objekten den Stauplatz B effizient zu füllen. Ein Teilproblem (i, R) wäre dann, mit den ersten i Objekten den Stauplatz R optimal zu füllen (i < n, R < B).
Für die Ergebnisse der Teilprobleme nutzt man einen Cache (also eine Matrix n x B), damit man sie nur einmal berechnen muss. Dann kann man recht effizient rekursiv in die Teilprobleme gehen und zusammensetzen. Oder man kann die Berechnungen gleich noch in die richtige Reihenfolge bringen, dann kann man wie bei Wikipedia direkt mit zwei verschachtelten Schleifen die Matrix schrittweise bis zum Endergebnis aufbauen. Das sind dann n*B Rechenschritte. Das Vorgehen liefert einem allerdings nur den optimalen Befüllungswert, die tatsächlich verwendeten Gegenstände muss man dann in einem separaten Schritt aus diesem Wert und dem Cache rekonstruieren, das ist allerdings kein Problem.

Das Problem für DP ist halt der Speicherverbrauch des Caches. Wenn B sehr groß wird, dann ist die Matrix schnell so groß, dass sie nicht mehr in den Speicher passt. Da in dieser Aufgabenstellung die Rucksackgröße B sogar noch als long übergeben wird, wären solche Fälle eigentlich ohne Weiteres denkbar gewesen in den Testcases. Tatsächlich treten sie allerdings nicht auf, meine DP-Lösung ist akzeptiert worden.

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

Hi Ogridi, nett dich auch ma hier zu sehen ;)


Es gibt einen effizienteren Weg, aber wenn ich Herrn Gallenbacher glauben darf, nicht den von HolgerF vorgeschlagenen. Das Rucksackproblem aus der wikipedia sei ein anderes als das hier, meinte er. (Fragt nicht, ich hab den Unterschied auch (noch) nicht gerafft.)

Der effizientere Weg, den ich meine, geht über pareto-optimale Teilmengen - ist zwar immer noch 2^n, aber im Mittel wesentlich kleiner, weil nur wenige Teilmengen pareto-optimal sind. Und nein ich habe ihn /nicht/ implementiert. Weil da das gleiche Speicherplatzproblem wie das von HolgerF geschilderte auftritt, hab ichs dann doch lieber gelassen ;)

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Doch, das Problem ist das gleiche wie auf Wikipedia :) Da bin ich mir ziemlich sicher, meine Lösung ist ja auch akzeptiert worden. Man kann ja auch die Problembeschreibung auf Wikipedia mit der der Aufgabe vergleichen, das stimmt überein.
Das einzige Problem an der Wikipedia-Lösung ist halt, dass sie einem nur den Wert der Befüllung liefert, aber nicht ihre Zusammensetzung. Aber wie gesagt, das kann man anschließend sehr einfach ermitteln.

jm1035
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 28. Okt 2005 09:26

Beitrag von jm1035 »

Das Problem ist ein ganz anderes wie das auf Wikipedia geschilderte. (Zumindest wenn es um den deutschen Wikipediaartikel geht, den man unter "Rucksackproblem" findet)
Der Unterschied liegt darin, dass bei dem Problem auf Wikipedia jedes Objekt beliebig oft in den Rucksack gesteckt werden kann. Bei unserem Problem kann jedoch ein Objekt nur einmal oder keinmal eingesackt werden.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Sorry, aber das stimmt nicht. Aus der mathematischen Beschreibung von Wikipedia:
Gegeben sind eine endliche Menge von Objekten U. Durch eine Gewichtsfunktion w und der Nutzenfunktion v wird den Objekten ein Gewicht und ein Nutzenwert zugeordnet. Des Weiteren gibt es eine vorgegebene Gewichtsschranke B
Gesucht ist eine Teilmenge K von U, die die Bedingung Summe(w(u)) <= B einhält und die Zielfunktion Summe(v(u)) maximiert. [Summen über alle Elemente von K]
Da ist nichts mit Mehrfachziehung drin, das geht auch nicht, weil in die Menge K ein Objekt aus U nun mal nur genau einmal auftauchen kann. Ergo ist das exakt dasselbe Problem wie aus unserer Aufgabe.

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Beitrag von yourmaninamsterdam »

Das stimmt doch überhaupt nicht. Da wird in der äußeren Schleife über alle Elemente iteriert. Einmal über jedes. Und nicht beliebig oft.

jm1035
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 28. Okt 2005 09:26

Beitrag von jm1035 »

Sorry, du hast Recht. Da hab ich wohl nicht genau genug hingeschaut.

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

Hm wie kann das ganze denn dann ein NP-Problem sein? Wenn es einen Algorithmus gibt, der O(n*B)-Komplexität hat? Oder spielt bei der Bewertung "P oder NP" die Speicherkomplexität wieder eine Rolle?
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Sind Gewichte und Nutzen ganzzahlig, so lässt sich der optimale Wert des Rucksackproblems auch mittels dynamischer Programmierung lösen.
Dieser Algorithmus funktioniert ausschließlich für diesen Spezialfall. Die NP-Vollständigkeit dürfte sich auf allgemeinere Gewichts- und Nutzenfunktionen beziehen.

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

HolgerF hat geschrieben:us funktioniert ausschließlich für diesen Spezialfall. Die NP-Vollständigkeit dürfte sich auf allgemeinere Gewichts- und Nutzenfunktionen beziehen.
Das ist Pseudopolynomiell. Das steht in keinem Widerspruch zur NP-Schwere. Es gibt keinen Algorithmus, der nur polynomiell von der Anzahl der Eingaben abhängt. Weiteres hierzu im Laufe der Vorlesung (oder in der theoretischen Informatik).

Antworten

Zurück zu „Archiv“