Hallo,
ich habe ein kleines Problem bei einem PC-Programm:
Ich habe eine Gruppe von Objekten mit Eigenschaften 1 | a= 1,3,6,8,4
| 2 | b= 2,5,4,8
| 3 | c= 2,4,9
|
Nun möchte ich diese Objekte gruppieren.
Dabei sollen die Objekte nach den Eigenschaften, also den Zahlen
gruppiert werden.
Zum Beispiel
Zu einem bestimmten Zeitpunkt darf jedes Objekt nur
in einer Gruppe sein, sodass sich die Gruppen
auf mehrere Zeitpunkte verteilen werden.
Dabei sollen natürlich so viele Gruppen
wie möglich gleichzeitig existieren,
und jedes Objekt soll einmal in jeder Gruppe gewesen sein,
die einer seiner Eigenschaften entspricht.
Bisher hatte ich die Idee, einfach die Reihenfolge der abgefragten
Eigenschaften zu ändern, also immer wieder durchzuprobieren.
Das ist aber viel zu langsam...
Könnt ihr mir da weiterhelfen,
ich habe da gerade einen Knoten im Hirn.
Mit freundlichen Grüßen,
Valentin Buck
Wenn dein Knoten wieder raus ist, könntest es vielleicht nochmal so
erklären, daß ich es auch verstehe?
Wieso sollte sich von Zeit zu Zeit die Grupppierung ändern?
Wieviele Eigenschaften gibt es denn?
Womit soll es gelöst werden?
Wozu das Ganze überhaupt?
Also:
die Gruppierung soll sich von Zeit zu Zeit ändern, da jedes Element
einmal in jeder Gruppe, die zu seinen Eigenschaften passt gewesen sein
muss,
aber immer nur in einer Gruppe sein soll.
Wie viele Eigenschaften es gibt, ist variabel.
Ich kann mal versuchen es als Beispiel zu formulieren:
Eine größere Menge Kinder will innerhalb kürzester Zeit alle ihre
Lieblingseissorten essen, jedes Kind hat pro Tag aber nur Geld für eine
Kugel.
Nun wollen die Kinder nicht alleine da hin gehen, sondern sie Gruppieren
sich nach ihren Eissorten.
Damit sie alle in kürzester Zeit ihre Eissorten durch haben, gehen immer
so viele Gruppen wie möglich gleichzeitig los.
Wann müssen welche Gruppen losgehen?
Gegeben sind die Kinder, ihre Eissorten und die Vorgabe der kürzesten
Zeit.
Ist das Problem jetzt klarer?
Die genaue Aufgabe kann ich hier leider aus Datenschutzgründen nicht
reinstellen.
Mit freundlichen Grüßen,
Valentin Buck
Valentin Buck schrieb:
> Ich kann mal versuchen es als Beispiel zu formulieren:
>
> Eine größere Menge Kinder will innerhalb kürzester Zeit alle ihre
> Lieblingseissorten essen, jedes Kind hat pro Tag aber nur Geld für eine
> Kugel.
> Nun wollen die Kinder nicht alleine da hin gehen, sondern sie Gruppieren
> sich nach ihren Eissorten.
> Damit sie alle in kürzester Zeit ihre Eissorten durch haben, gehen immer
> so viele Gruppen wie möglich gleichzeitig los.
>
> Wann müssen welche Gruppen losgehen?
> Gegeben sind die Kinder, ihre Eissorten und die Vorgabe der kürzesten
> Zeit.
>
> Ist das Problem jetzt klarer?
Noch nicht wirklich.
Aber das Problem hat etwas an sich, was mich sofort an Backtracking
denken lässt.
ja, schöne Übungsaufgabe.
Valentin Buck schrieb:
> Die genaue Aufgabe kann ich hier leider aus Datenschutzgründen nicht
> reinstellen.
Weil sie vom Dozenten ist?
Ich versuch mal die Aufgabenstellung so zu formulieren, wie ich sie bis
jetzt verstanden habe.
Gegeben ist eine Menge von Objekten ( a, b, c ), wobei jedes Objekt über
Eigenschaften verfügt.
Gesucht ist eine Aufteilung dieser Objekte in Gruppen
* jedes Objekt muss in einer Gruppe vorkommen
* kein Objekt darf in mehr als einer Gruppe vorkommen
* alle Objekte einer Gruppe sind dadurch charakterisiert, dass sie
über dieselbe Eigenschaft verfügen.
Diese gemeinsame Eigenschaft ist es auch, die eine Gruppe
charakterisiert
Von allen überhaupt möglichen Gruppenzerlegungen, die mögliche sind,
sind diejenigen Zerlegungen gesucht, bei der die Anzahl der Gruppen
maximal ist.
Wie da jetzt die Zeit noch mit reinspielt, ist mir noch nicht klar. Die
Zeit war in der ursprünglichen Aufgabenstellung so noch nicht drinnen.
Wie gesagt: das stinkt für mich nach Backtracking. Auch wenn es nicht
identisch ist, das könnte eine gewisse Ähnlichkeit mit dem
Rucksackproblem haben. Wobei es mehrere Rucksäcke gibt und jeder
Rucksack nur eine bestimmte Art von Objekten aufnehmen kann.
So über den Daumen gepeilt.
Oder einfach nur Listen abhaken.
Vielleicht gibt es ja nichts zu optimieren,
zumindest sehe ich nichts.
Ich denke es geht nur darum, die Regeln einzuhalten
und zum Schluß jedem Kind sein Eis zukommen zu lassen.
Karl heinz Buchegger schrieb:
> Wie da jetzt die Zeit noch mit reinspielt, ist mir noch nicht klar. Die
> Zeit war in der ursprünglichen Aufgabenstellung so noch nicht drinnen.
Naja, wenn das Kind c die Sorten 2, 4 und 9 braucht,
dann muß es einmal in einer Gruppe für 2 sein, einmal in einer
Gruppe für 4 und einmal in einer für 9.
Egal in welcher Reihenfolge, Hauptsache es wird ihm von 2, 4
und 9 schlecht.
Weil es aber nicht in drei Schlangen gleichzeitig stehen kann,
kann es nur jeweils in einer Gruppe sein - zu einem Zeitpunkt.
Ich habe eine Idee:
Ich gebe die Sorten in ein FIFO.
Dann erstelle ich einen neuen Termin.
Nun gebe ich alle Kinder mit einer Eissorte,
die ich noch nicht hatte in eine Gruppe.
Dann gucke ich, ob es noch Gruppenmöglichkeiten gibt,
die keines der Kinder brauchen, dass schon in der Gruppe ist.
Wenn es welche gibt, dann kommen die Gruppen auch noch an dem Termin.
Wenn es keine Möglichkeiten mehr gibt,
dann erstelle ich einen neuen Termin und habe wieder alle Kinder zur
Verfügung...
Ich probiers mal aus.
Mit freundlichen Grüßen,
Valentin Buck
Klaus Wachtler schrieb:
> Karl heinz Buchegger schrieb:
>> Wie da jetzt die Zeit noch mit reinspielt, ist mir noch nicht klar. Die
>> Zeit war in der ursprünglichen Aufgabenstellung so noch nicht drinnen.
>
> Naja, wenn das Kind c die Sorten 2, 4 und 9 braucht,
> dann muß es einmal in einer Gruppe für 2 sein, einmal in einer
> Gruppe für 4 und einmal in einer für 9.
> Egal in welcher Reihenfolge, Hauptsache es wird ihm von 2, 4
> und 9 schlecht.
>
> Weil es aber nicht in drei Schlangen gleichzeitig stehen kann,
> kann es nur jeweils in einer Gruppe sein - zu einem Zeitpunkt.
Das ist mir noch klar.
Es ist der Teil hier
[quote]
Damit sie alle in kürzester Zeit ihre Eissorten durch haben, gehen immer
so viele Gruppen wie möglich gleichzeitig los.
Wann müssen welche Gruppen losgehen?
Gegeben sind die Kinder, ihre Eissorten und die Vorgabe der kürzesten
Zeit.
[/quote]
den ich noch nicht einordnen kann.
Ich spinne mal weiter.
Eine komplette mögliche Lösung sieht so aus
1 | Eigenschaften: Erdbeer (E), Vanille (V), Schoko (S)
| 2 |
| 3 | Hans will Erdbeer, Vanille und Schoko
| 4 | Franz will Schoko und Vanille
| 5 | Sabine will Vanille und Erdbeer
| 6 | Gustav will Erdbeer, Vanille und Schoko
| 7 |
| 8 | eine mögliche Lösungssequenz lautet
| 9 |
| 10 | G( E ) = { Hans, Gustav } G( V ) = { Sabine } G( S ) = { Franz )
| 11 | G( E ) = { Sabine } G ( V ) = { Hans, Franz, Gustav }
| 12 | G( S ) = { Hans } G( S ) = { Gustav }
| 13 |
| 14 | d.h. in 3 Durchgängen sind alle 'Aufträge' abgearbeitet.
| 15 |
| 16 | Diese Reihung ist besser als
| 17 |
| 18 | G( E ) = { Hans } G( V ) = { Franz } G( S ) = { Gustav }
| 19 | G( E ) = { Sabine } G( V ) = { Hans }
| 20 | G( E ) = { Gustav }
| 21 | G( V ) = { Sabin }
| 22 | ....
| 23 |
| 24 | weil diese Sequenz länger ist.
|
Gesucht ist als die Sequenz, bei der man die wenigsten Teilschritte
braucht, sodass jedes Objekt mit all seinen Eigenschaften einmal
irgendwo in der Sequenz vorgekommen ist. (Das dann in jedem Schritt
möglichst viele Gruppen entstehen werden folgt automatisch)
Klingt das logisch?
Hört sich gut an.
Die Frage ist, ob du die Note dafür bekommst :-)
Klaus Wachtler schrieb:
> Hört sich gut an.
Ich denke das wars auch.
Ein analoges Problem ist IMHO auch:
In einer Spedition gibt es Frachtgüter (Objekte)
Diese müssen zu bestimmten Orten (Eigenschaften)
Es steht eine (unbegrenzte) Anzahl an LKW
zur Verfügung (Gruppeneinteilung)
In welcher Reihenfolge werden die LKW mit welcher Fracht beladen, so
dass möglichst wenig Fahrten notwendig sind um alle Frachtstücke
auszuliefern.
Klingt für mich immer mehr nach Backtracking.
Mit einer vernünftigen Datenstruktur sollte das relativ einfach zu
machen sein.
> Die Frage ist, ob du die Note dafür bekommst :-)
:-)
Klaus Wachtler schrieb:
> Hört sich gut an.
> Die Frage ist, ob du die Note dafür bekommst :-)
Welche Note?
Das hier ist privat!
Ich bin Schüler,
und in Informatik sind wir gerade bei for-Schleifen in PASCAL!
Das hier schreibe ich in JAVA!
@Karl Heinz Buchegger:
DANKE!!! Das hat mir noch mal sehr geholfen!
Mit freundlichen Grüßen,
Valentin Buck
Valentin Buck schrieb:
> Das hier schreibe ich in JAVA!
So eine Info wäre hilfreich gewesen.
Valentin Buck schrieb:
> Die genaue Aufgabe kann ich hier leider aus Datenschutzgründen nicht
> reinstellen.
Valentin Buck schrieb:
> Das hier ist privat!
hm.
Valentin Buck schrieb:
> @Karl Heinz Buchegger:
> DANKE!!! Das hat mir noch mal sehr geholfen!
Wenn es das trifft, dann fang damit an, dir eine Datenstruktur zurecht
zu legen, mit der du eine Sequenz komplett und vollständig beschreiben
kannst.
Also eine Liste bestehend aus Teilschritten
Ein Teilschritt ist selbst wieder eine Liste, nämlich eine Liste von
Gruppen
Eine Gruppe ist selbst wieder eine Liste, nämlich eine LIste von
Elementen
Und der Rest: systematisch durchprobieren ob und wie die Objekte in die
Listen eingeordnet werden können. Es ist genau dieses systematische
Durchprobieren, worum es beim Backtracking geht.
Als Vorübung mal einfachere, dokumentiere BT Probleme lösen
8-Damen, Rucksackproblem, Problem der stabilen Heirat.
Dadurch kriegst du ein Gefühl dafür, wie sowas aussieht, auch wenn es
dem Prinzip nach immer gleich aussieht
bool Try()
{
while es gibt noch einen Kandidaten {
verbaue den Kandidaten
if Problem vollständig gelöst
return true
if try()
return true
nimm diesen Kandidaten aus der Lösungsmenge raus
}
return false
}
Der interessantere Teil besteht darin, Wege zu finden, wie man das BT
durch offensichtliche Dinge abkürzen kann.
Ich hatte auch mal ein Problem, bei dem es theoretisch 10 hoch 27
mögliche Lösungen gab. Gegeben sind Teilnehmer an einer Veranstaltung
bei der Fernsteuerungen eine wichtige Rolle spielen. Jeder Teilnehmer
hat eine Anzahl an Quarzen (Frequenzen) mit. Gesucht ist eine Zuteilung
eines Quarzes zu einem Teilnehmer, so dass es zu keinen Überschneidungen
kommt.
Bei 3 Leuten und je 2 Quarzen ist das kein Problem. Bei 70 Teilnehmern
und im Schnitt 8 Quarzen pro Teilnehmer ist es das aber schon.
Meine erste Programmversion hat eine ganze Nacht am Problem gearbeitet
und den Suchbaum abgegrast. Die letzte Version, die Baumbeschneidung des
Suchbaumes betrieb, aber immer noch garantiert eine Lösung findet wenn
es eine gibt, schafft das Problem in weniger als 5 Sekunden. Im Prinzip
also immer noch der gleiche Algorithmus aber Teilzweige des Suchbaums
die offensichtlich nicht besser als das bisher gefundene sein können
ignoriert.
Echt, DANKE!
Hier im Forum hab ich bisher zu JEDEM Problem eine Lösung bekommen.
Echt toll!
Mit freundlichen Grüßen,
Valentin Buck
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
|
Thread beobachten
Seitenaufteilung abschalten