Sortieralgorithmus Aufteilung einer Menge

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo,

ich habe folgendes Problem und wollte Fragen, ob es dafür einen Standard-Algorhitmus gibt wie z.B. Bubblesort:

Gegeben sei eine Menge A mit n Elementen. Diese Menge soll entweder in beliebig viele Mengen mit einer fixen Zahl an Elementen oder in eine fixe Zahl an Mengen mit beliebig vielen Elementen aufgeteilt werden, und zwar unter der Prämisse, dass die Summen der Elemente der neuen Mengen möglichst gleich groß sein sollen, bzw. einen vorgegebenen Wert nicht überschreiten dürfen.

Zur Veranschaulichung die eigentliche Anwendung aus meinem Tätigkeitsfeld: Ich habe eine bestimmte Anzahl von elektrischen Verbrauchern unterschiedlicher Leistung, die ich auf eine Anzahl von Transformatoren fester Leistung aufteilen muss. Dabei sollen alle Transformatoren möglichst gleichmässig belastet werden. Zur Zeit mache ich das noch „zu Fuß“, möchte das aber mittelfristig mit Hilfe eines Programmes automatisieren.

Vielen Dank im Voraus für Eure Unterstützung!

Gruß

Alex

#2

Zur Veranschaulichung die eigentliche Anwendung aus meinem
Tätigkeitsfeld: Ich habe eine bestimmte Anzahl von
elektrischen Verbrauchern unterschiedlicher Leistung, die ich
auf eine Anzahl von Transformatoren fester Leistung aufteilen
muss. Dabei sollen alle Transformatoren möglichst gleichmässig
belastet werden. Zur Zeit mache ich das noch „zu Fuß“, möchte
das aber mittelfristig mit Hilfe eines Programmes
automatisieren.

Hallo Alex,

ein verwandtes Problem, für das es einfache Strategien gibt, ist das Zuschneiden von Holzbalken nach geforderter Länge, allerdings geht es dabei darum, möglichst wenig übrigzulassen, was bei dir ja umgekehrt ist.

Klar ist jedenfalls der erste Schritt: der grösste Verbraucher kommt an den grössten Trafo, damit liegt schon die untere Grenze der Auslastung fest. Ich würde dann einfach so weitermachen: der nächstgrösste Verbraucher kommt an den Trafo, der am meisten Leistung übrig hat, und so weiter bis keiner mehr da ist.

Gruss Reinhard

#3

Rucksackproblem
Hallo,

ein verwandtes Problem ist das sog. eindimensionale Rucksackproblem. Wenn du danach suchst, wirst du sicher ein paar Lösungsansätze finden, die sich auf dein Problem übertragen lassen.

Grüße,
Moritz

#4

Hallo,

vielen Dank für Eure Antworten! Ihr habt mich auf jeden Fall in die richtige Richtung gestoßen. Das mit dem Holzzuschnitt müsste eine Art Greedy Algorithmus sein. Der bringt allerdings nur lokale Optima hervor, ich suche ja das globale.

Mit dem Rucksack kommen wir der Sache schon näher. Das ist es zwar auch nicht exakt, aber es ist ebenfalls ein Problem aus dieser Liste der 21 NP-vollständigen Probleme, nämlich das Partitionsproblem: http://de.wikipedia.org/wiki/Partitionsproblem

Ich muss mal darüber grübeln, wie ich dieses Problem mit einer ungeraden Anzahl an Trafos löse…und dann brauch ich noch den Code für den Lösungsalgorithmus in VB… ;o)

Gruß

Alex

#5

Hi,

bei der Theorie kann ich Dir nicht helfen, aber …

Ich muss mal darüber grübeln, wie ich dieses Problem mit einer
ungeraden Anzahl an Trafos löse…und dann brauch ich noch den
Code für den Lösungsalgorithmus in VB… ;o)

einen bekannten Algorithmus VB-verständlich umschreiben? Fingerübung! :->> (Mail, wenn Du selbst keine Lust hast. Das könnte 'ne Mittagspause füllen.)

Gruß, Rainer

#6

Hallo Alex,

ein verwandtes Problem, für das es einfache Strategien gibt,
ist das Zuschneiden von Holzbalken nach geforderter Länge,
allerdings geht es dabei darum, möglichst wenig übrigzulassen,
was bei dir ja umgekehrt ist.

Klar ist jedenfalls der erste Schritt: der grösste Verbraucher
kommt an den grössten Trafo, damit liegt schon die untere
Grenze der Auslastung fest. Ich würde dann einfach so
weitermachen: der nächstgrösste Verbraucher kommt an den
Trafo, der am meisten Leistung übrig hat, und so weiter bis
keiner mehr da ist.

Gruss Reinhard

Hallo!

Ich finde den Algorithmus von Reinhard schon sehr gut, weil die Implementierung auch relativ einfach ist. Dennoch möchte ich anmerken, dass er nicht „optimal“ ist.

Beispiel:
Zwei Transformatoren: T[1,2]={4W,3W}
Drei Verbraucher: V[1,2,3]={3W,2W,2W}

Reinhards Algorithmus würde folgende Zuteilung erzeugen:
V[1] wird T[1] zugeteilt
V[2] wird T[2] zugeteilt
V[3] würde somit keinem der beiden Transformatoren zugeteilt werden können, weil beide jeweils nur noch eine Restkapazität von 1W aufweisen würden.

In diesem Fall wäre diese Lösung günstiger:
V[1] wird T[2] zugeteilt und V[2,3] werden T[1] zugeteilt.

Leider habe ich gerade keine Zeit, um nach einem „optimalen“ Alg. zu suchen… aber vielleicht brauchst du auch keinen optimalen und der von Reinhard reicht dir…

=============================

Mir ist auch noch eine andere Möglichkeit eingefallen, falls die Verbaucher die ganze Zeit KOMMEN UND GEHEN und, falls die Kapazität eines Transformators VIEL GRÖSZER ist, als die Anforderung eines einzelnen Verbauchers.

Also, falls gilt:
m ist Anzahl der Transformatoren, n ist Anzahl der Verbaucher und es gilt
T[1,…,m] >> V[1,…,n] für alle m,n und natürlich auch
V[1]+…+V[n]

#7

Hallo zusammen,

dummer Anfängerfehler meinerseits: ich habe zwei Antwortenbäume geöffnet, würde den Thread aber gerne hier weiterführen.

@lukas: Die Lasten und die Trafos liegen in etwa nur eine Größenordnung auseinander. Daher passt Lösung zwei nicht, aber interessanter Gedanke.

Vom Rucksack habe ich schon gestern Abschied genommen, da ich nach ein wenig Recherche ja auf das Partitionsproblem gestossen bin, was meinem Problem an nächsten kommt. Besonders wichtig ist mir ja, dass die Summenlasten pro Trafo (die Trafos sind übrigens i.d.R. alle gleich groß, wegen Ersatzteilhaltung und so) möglichst identisch sind.

@Rainer: Das coden in VB an sich sollte das Problem nicht sein, wenn ich denn a) Zeit dafür finde und b) erst mal weiß, was ich programmieren soll. Ich habe ja zunächst nur das mathematische Problem gefunden, nicht aber den Lösungsalgorithmus. Aber ganz ehrlich: ich finde es super, dass jemand tendenziell bereit ist, seine Mittagspause zu opfern, um meine Faulheit zu unterstützen :o))))

Gruß
Alex

#8

Hallo!

@lukas: Die Lasten und die Trafos liegen in etwa nur eine
Größenordnung auseinander. Daher passt Lösung zwei nicht, aber
interessanter Gedanke.

Wenn ich nach meinen Klausuren Zeit habe, dann werde ich mich auf jeden Fall um ne Lösung bemühen, wenn du bis dahin noch keine hast, weil mich das Problem auch reizt.
Ich denke da wird in der Fachliteratur schon genau dieses Problem irgendwo Mal drin sein, das Problem ist recht allgemein denke ich.
Wenn ich was hab, dann meld ich mich auf jeden Fall…

Gruß
Lukas

#9

Wenn ich nach meinen Klausuren Zeit habe, dann werde ich mich
auf jeden Fall um ne Lösung bemühen, wenn du bis dahin noch
keine hast, weil mich das Problem auch reizt.
Ich denke da wird in der Fachliteratur schon genau dieses
Problem irgendwo Mal drin sein, das Problem ist recht
allgemein denke ich.
Wenn ich was hab, dann meld ich mich auf jeden Fall…

Gruß
Lukas

Das wäre super, bis dahin viel Erfolg!

Ich werd’ mich bis dahin schon mal um Quicksort kümmern, denn ich denke, die Menge zu sortieren ist eh der erste Schritt. Der eigentliche Algorithmus ist ja eher das (Iterations-)Verfahren, wie ich auf die Trafos aufteile, z.B. von groß nach klein reihum auf die Trafos verteilen, etc. Vermutlich gibt es mathematische Methoden, einen Algrotihmus auf zeitliche Optimierung abzuklopfen, mit denen es eleganter geht als mit try-and-error. Wenn jemandem was dazu einfällt - immer her damit!

Gruß
Alex

#10

Beispiel:
Zwei Transformatoren: T[1,2]={4W,3W}
Drei Verbraucher: V[1,2,3]={3W,2W,2W}

Hallo Lukas,

auf diesen Einwand hin ist mir klargeworden, dass es nicht um eine einfache Optimierung geht, sondern die Aufgabe, alles unterzubringen, muss als Nebenbedingung oder als weiteres (vorrangiges) Optimierungsziel eingeführt werden. Dazu fallen mir auf die Schnelle 2 Lösungen ein:

  1. Backtracking. Ist die weitere Verteilung blockiert, gehe zurück zum Anfang und nehme nicht den grössten, sondern den zweitgrössten Trafo für den grössten Verbraucher.

  2. Heuristische Abschätzung. Die durchschnittliche Auslastung kann ja leicht vorab berechnet werden, z.B. 70%. Man ordnet jetzt jeden Verbraucher (absteigend nach der Grösse) dem Trafo zu, der damit am nächsten an diese Auslastung herankommt. M.a.W. die Zuordnung beruht auf den 70% der Leistung, aber natürlich ist eine Zuordnung bis 100% erlaubt. Da es sich um einen Mittelwert handelt, müssen ja einige darunter und einige darüber liegen.

Beides würde für deinen Fall funktionieren, aber sicher nicht für alle beliebigen.

Zur Optimalität allgemein:

Das Bohren von Leiterplatten ist TSP in Reinkultur. Es gibt von IBM dazu einen erwiesenermassen optimalen Bohrweg für eine Leiterplatte mit 25000 Bohrlöchern. Im Lieferzustand sind die Bohrkoordinaten meistens nach X-Werten sortiert (wenn überhaupt), was zur Folge hat, dass der Bohrkopf erst über die gesamte Breite alle Löcher auf gleicher Höhe bearbeitet und dann erst die nächste Linie, damit kann der Weg leicht zehn bis hundertmal länger werden als notwendig.

Ich habe dazu folgende Optimierung angewendet: fang links unten an (min X/Y, aber der Start ist eigentlich egal) und bohre immer das nächstgelegene, noch nicht gebohrte Loch.

Das ist so lächerlich einfach, dass ich das schon vor 20 Jahren auf einem Z80 programmiert habe zur Reduzierung der Bohrzeiten in unserer Fertigung. Die Erfahrungen damit: ein Durchlauf reduziert den Weg schlecht angeordneter Löcher auf einen kleinen Bruchteil, ein 2. Durchgang bringt manchmal noch eine Verbesserung um 2 oder 5% und weitere Durchgänge bringen keine Verbesserung mehr bzw. nur im Promille-Bereich. Keine später gekaufte Software auf Sun-Workstations o.ä. hat je merklich bessere Ergebnisse gebracht. D.h. eine erste primitive Optimierung leistet 90% oder mehr der gesamt möglichen Verbesserung, von da an steigt der Aufwand exponentiell mit gegen Null gehendem Ergebnis.

So gesehen war die obige IBM-Lösung ein Meilenstein für TSP, hat aber die Fertigungskosten der betreffenden Leiterplatte sicher nicht fühlbar gesenkt. Meine Meinung dazu ist, dass optimale Lösungen theoretisch sehr interresant sind, aber in der Praxis braucht man sie selten - man sollte nur ungefähr wissen, wie weit man davon entfernt ist.

Gruss Reinhard