mikrocontroller.net

Forum: PC-Programmierung Gruppierungsproblem


Autor: Valentin Buck (nitnelav) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich habe ein kleines Problem bei einem PC-Programm:
Ich habe eine Gruppe von Objekten mit Eigenschaften
a= 1,3,6,8,4
b= 2,5,4,8
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
G8 = {a,b}
G9 = {c}
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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Valentin Buck (nitnelav) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ja, schöne Übungsaufgabe.

Valentin Buck schrieb:
> Die genaue Aufgabe kann ich hier leider aus Datenschutzgründen nicht
> reinstellen.

Weil sie vom Dozenten ist?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Valentin Buck (nitnelav) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
Eigenschaften: Erdbeer (E), Vanille (V), Schoko (S)

Hans will Erdbeer, Vanille und Schoko
Franz will Schoko und Vanille
Sabine will Vanille und Erdbeer
Gustav will Erdbeer, Vanille und Schoko

eine mögliche Lösungssequenz lautet

  G( E ) = { Hans, Gustav }  G( V ) = { Sabine }  G( S ) = { Franz )
  G( E ) = { Sabine }  G ( V ) = { Hans, Franz, Gustav }
  G( S ) = { Hans }  G( S ) = { Gustav }

d.h. in 3 Durchgängen sind alle 'Aufträge' abgearbeitet.

Diese Reihung ist besser als

  G( E ) = { Hans }  G( V ) = { Franz }  G( S ) = { Gustav }
  G( E ) = { Sabine }  G( V ) = { Hans }
  G( E ) = { Gustav }
  G( V ) = { Sabin }
  ....

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?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hört sich gut an.
Die Frage ist, ob du die Note dafür bekommst :-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-)

:-)

Autor: Valentin Buck (nitnelav) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Valentin Buck (nitnelav) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Echt, DANKE!

Hier im Forum hab ich bisher zu JEDEM Problem eine Lösung bekommen.
Echt toll!

Mit freundlichen Grüßen,
Valentin Buck

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.