Immer diese alten Leute mit ihren Golf-Flight-Problemen ...

[abgemeldeter Benutzer]

Hallo,
also ich hab' hier 'mal ein Problemchen. Da mir das auf den ersten Blick zu stressig scheint, poste ich das einfach:

- 5 Tage
- 12 Personen
- täglich: 3 Flights mit je 4 Personen

Gesucht wird eine (oder mehrere, falls einer 'nen Algo. findet) Konstellation in der das ganze an den fünf Tagen möglichst gut durchgemischt wird. Sprich gleiche Leute sollen so selten wie möglich zusammenspielen. Ideen?
Falls es nur heuristisch irgendwie gehen sollte, würde ich mich auch hier über Ansätze freuen, 'nen kleines Programm kriege ich noch gerade hin.

ciao
Philip

[mugen]

du brauchst ne adjazenzmatrix wo an den entsprechenden stellen die häufigkeit steht wie oft die schon zusammen gespielt haben


bsp

A B C D
Ax 1 0 1
Bxxx 0 1
C xxxx 1
D xxxx x

versuchs mal mit dem prim algorithmus auf der adjazenzmatrix, musst nur dann halt abbrechen sobald du 4 knoten verbunden hast. dann nochmal prim algo nur halt die 4 knoten die du schon belegt hast auslassen und die restlichen 4 die dann über bleiben sind ja klar.

und natürlich nicht vergessen die entsprechenden stellen in der adjazenzmatrix zu inkrementieren.

für den startknoten würd ich einfach n zufallsgenerator nehmen. ebenso wenn 2 oder mehr knotne gleich billig zu erreichen sind.

http://de.wikipedia.org/wiki/Algorithmus_von_Prim

[Coolcat]

Sofern es bei den kleinen Zahlen bleibt, sollte doch BruteForce (== alles ausprobieren) kein Problem sein, oder? Sind doch nur Möglichkeiten...

P.S. Was ist ein Golf-Flight??

[mugen]

seit wann löst man probleme mit würfeln^^

edit:
habs grad mal kurz überschlagen, bei den anforderungen ist die chance 1:11 dass eine gruppe zwei mal die selbe ist, und 1:2,8 dass zweimal 3 gleiche in ner 4er gruppe sind, das is nicht akzeptabel

[Coolcat]

seit wann löst man probleme mit würfeln^^

Wenn es nur darum geht gerade mal eben für dieses eine mal genau dieses eine Problem zu lösen, lohnt eine aufwendige Implementierung nicht. Man sollte nur da optimieren wo es auch Sinn macht. Meine Lösung sollte sich ja ganz simpel mit einer Doppelschleife implementieren lassen.

Edit:
Mir fällt gerade auf das es wesentlich mehr Möglichkeiten gibt...man muss ja die beste Kombination aus 15 dieser 495 Möglichkeiten finden.


Also vielleicht sollte man doch keinen BruteForce-Ansatz wählen

[mugen]

prim algo implementierungen findet man wie sand am meer muss man nur bisl tunen.

ist die frage ob man sich die halbe stunde mehr nimmt oder lieber 2h lang sich geschichten von alten leuten anhört

edit:

ah du willst garnicht würfeln, aber ok wenn man das brute force mässig angeht hat man ein paar das 3x hinternander immer in der selben gruppe ist am ersten tag

erläuter mal bitte deine rechnung oben. ah ok ist die beste, eben^^

[abgemeldeter Benutzer]

Hi,
schonmal danke für eure Antworten ...

Hab' das mit der Matrix umgesetzt, funzt super und da kann ich auch relativ gefahrlos alle Variablen parametrisieren ohne mir allzu große Laufzeitsorgen machen zu müssen.

ciao
Philip