Gruppiertes Sortieren

[Lee500]

Hallo Delphi-Freunde,

Ich bräuchte mal wieder eure Hilfe.

Folgendes Problem:
Ich habe eine endliche Anzahl an Werten. Jetzt sollen immer 4 Werte in der Summe als Satz zusammengesetzt werden. Ziel ist es eine vorher festgelegte Anzahl Sätze zu erzeugen. Diese Sätze sollen untereinander minimale abweichungen haben.

Beispiel:
1 2 3 4 5 6 7 8 9 10

Satz 1: 2 4 7 9 = 22
Satz 2: 3 5 6 8 = 22

Die Werte außerhalb der Reihe (hier 1 und 10) sollen einfach ignoriert werden. Bei diesem Beispiel ist das sortieren noch vergleichsweise einfach, da der Abstand der Werte untereinander immer genau 1 beträgt. Die tatsächlichen Werte haben größere Abweichungen. Die Werte 1 und 10 sind später auch noch weiter vom Hauptfeld entfernt.

Ich hoffe ihr könnt mir weiterhelfen.

Danke im Voraus
Lee500

[ak-ac]

hi,

ich glaube es geht nicht um ein Sortierungsproblem, wenn ich das richtig verstanden habe, sondern eher um ein Optimierungsproblem:
Du willst dein Elemente auf eine Anzahl von Töpfen verteilen, so dass die Unterschiede minimal sind. Die entsprechenden Algorithmen sind schon komplizierter, insbesondere wenn du das ganze in kürzerer Zeit lösen willst. Kannst Dich ja mal beim Travelings Salesman insprieren lassen...

Gruss
Alex

[Lee500]

Hallo

Die Lösung des Travelling Salesman finde ich nicht so passend, da ich nicht die 4 Werte in einem "Topf" nah beieinander haben möchte, sondern die Entfernung von einem Topf zum anderen Topf soll minimal sein. Wie die Werte innerhalb des Topfes angeordnet sind ist zwar nicht völlig egal, aber erstmal zu vernachlässigen.

Man könnte natürlich einen Wert mit jedem anderen Wert paaren und dann die geringsten entfernungen zum Mittelwert als Anhaltspunkt nehmen. Die mit den geringsten Abweichungen werden dann wiederum mit den anderen paaren gepaart. Das würde zu einer annähernd optimalen Lösung führen, aber ich denke diese lässt sich noch weiter optimieren.

Gruß
Lee500

[sx2008]

Das Problem ist wohl eine Variante des Rucksackproblems.
Ich würde es so probieren:
Bei 20 Elementen werden 20/4 = 5 Töpfe gebildet.
Jeder Topf erhält am Anfang zufällig ausgewählt 4 Elemente.
[ Start ]
Die Summen aller 5 Töpfe werden berechnet.
Dann werden die beiden Töpfe mit der grössten Abweichung ausgewählt.
Sollte die Abweichung geringer als ein vorgegebener Maximalwert sein, wird der Algorithmus beendet.
Diese beiden Töpfe tauschen nun ihre Elemente.
Bei 4 Elementen gibt es 4 *4 = 16 Tauschmöglichkeiten.
Alle Tauschmöglichkeiten werden durchprobiert und der Tausch durchgeführt,
bei dem der Unterschied der Summe minimal wird.
Die nächste Iteration wird eingeleitet (Goto [ Start ]) oder der Algorithmus nach einer max. Anzahl von Iterationen beendet.

Die ideale Lösung wird so vielleicht nicht gefunden, aber es wird doch ein relativ guter Ausgleich erreicht.

[Lee500]

Danke sx2008,

Das ist eine Lösung die sich erstmal ganz gut anhört, aber heute nacht habe ich nicht mehr die Motivation dazu

Ich werd das mal ausprobieren.

Gruß
Lee500

//EDIT: Ich habe es jetzt am laufen. Ist nicht ganz so gelöst wie oben, da er dann immer zwischen den selben Töpfen hin und hergetauscht hat. Jetzt sucht er sich den schlechtesten Topf und sucht sich dann ein Element eines anderen Topfes, dessen Tausch beide Töpfe näher an den Optimalwert bringen. Diese Schleife läuft dann solange, bis kein Tausch mehr gefunden wird, von dem beide Töpfe profitieren würden.