PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Name eines Algorithmus' gesucht

Xanatos
2008-06-03, 12:25:43
Hallo,
ich suche grade einen Algorithmus, mir faellt aber der Name nicht mehr ein. Der Algorithmus soll folgendes machen:
Man hat eine Liste, deren Elemente sortiert sind. z.b. (1,3,4,5,7,8,9)
Man soll diese Liste nun so in Gruppen aufteilen, dass keine Grunde mehr als einen gewissen Wert hat. z.B. 11
In diesem Bsp ware es dann so:
Gruppe 1: 9,1
Gruppe 2: 8,3
Gruppe 3: 7,4
Gruppe 4: 5

Wie heisst dieser Algorithmus?
wry
2008-06-03, 15:28:44
Sieht aus wie eine spezielle Variante des Rucksackproblems (Knapsack problem).

Ich kenne leider auch keinen Algorithmus dazu aus dem Stand, aber eventuell solltest welche finden, wenn du nach dem Rucksackproblem suchst.

Falls du das schon wusstest, dann ignorieren wir den Post einfach :biggrin:
Xanatos
2008-06-03, 15:39:15
Alles was ich zum googlen benutzen kann, hilft;)
Gnafoo
2008-06-03, 16:25:28
Meine Klausurnotizen von Info3 sagen: das Problem (oder zumindest ein sehr ähnliches) hieß bei uns "Bin Packing"/Behälterproblem (aka BINPACK). Verteile optimal n Gegenstände der Größe w_i auf k Dosen der Größe b. Das Problem selber ist NP-vollständig und ich kenne jetzt auch keinen besonders schlauen Algorithmus dafür. ;)

Ich vermute mal da gibt es mehrere verschiedene heuristische Algorithmen.

Edit: naja ist nicht ganz deine Aufgabe, hilft dir aber vielleicht auch weiter:
http://de.wikipedia.org/wiki/Behälterproblem
http://en.wikipedia.org/wiki/Bin_packing_problem
Xanatos
2008-06-03, 16:34:39
Danke, das Bin packing problem wars und die zwei genanten heuristischen Algorithmen hatte ich auch schonmal...
Senior Sanchez
2008-06-03, 17:46:04
Oje, das war mal ne Topcoderaufgabe :D
Da musste man Kinder so auf einer Schaukel verteilen, dass die möglichst ausgeglichen ist.

Hmm, aber es ist ja NP-vollständig und zumindest für ganze Zahlen (die auch nicht allzuhoch sind) gibts bestimmt nen dynamischen Programmieransatz, ähnlich dem Rucksackproblem.
Dr.Doom
2008-06-03, 20:04:58
Was NP-Vollständig sein soll, habe ich bis heute nicht verstanden. *g*
Senior Sanchez
2008-06-03, 20:20:55
Was NP-Vollständig sein soll, habe ich bis heute nicht verstanden. *g*

Was NP bedeutet weißt du aber, oder?
RattuS
2008-06-03, 21:08:32
Das ist das "Rucksack-Problem". Es gibt viele Algorithmen dazu, die aber alle bei mehr als 30 Gegenständen aufgrund der Rechenzeit als effektives Instrument scheitern. Ich denke, dass es keine effektive Lösung gibt (TSP lässt grüßen).
Senior Sanchez
2008-06-03, 22:46:18
Das ist das "Rucksack-Problem". Es gibt viele Algorithmen dazu, die aber alle bei mehr als 30 Gegenständen aufgrund der Rechenzeit als effektives Instrument scheitern. Ich denke, dass es keine effektive Lösung gibt (TSP lässt grüßen).

Naja, in der NP-Klasse ist alles das "Rucksack-Problem" :D (naja, okay, mit einer gewissen Transformation werden sie das ;) ).

Ich glaube das ein dynamisch programmierter Ansatz dafür schon recht gut performed. Nur dazu müssen die Werte ganzzahlig sein, ansonsten funktionierts nicht.

Es gibt eine effektive Lösung, aber keine effiziente ;) Zumindest wurde bisher keine gefunden.
RattuS
2008-06-05, 18:16:55
Es gibt eine effektive Lösung, aber keine effiziente ;) Zumindest wurde bisher keine gefunden.
Also die "Schweden Tour" ist schon recht ordentlich. ;)
Senior Sanchez
2008-06-05, 23:27:55
Also die "Schweden Tour" ist schon recht ordentlich. ;)

Mit Lösung meinte ich ein Algorithmus der es für jeden Fall schnell berechnen kann. Und zwischen effektiv und effizient besteht ein Unterschied ;)