AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Gruppiertes Sortieren

Ein Thema von Lee500 · begonnen am 31. Okt 2010 · letzter Beitrag vom 1. Nov 2010
Antwort Antwort
Benutzerbild von Lee500
Lee500

Registriert seit: 18. Sep 2006
39 Beiträge
 
Delphi 2010 Architect
 
#1

Gruppiertes Sortieren

  Alt 31. Okt 2010, 14:03
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
  Mit Zitat antworten Zitat
ak-ac

Registriert seit: 10. Apr 2009
26 Beiträge
 
#2

AW: Gruppiertes Sortieren

  Alt 31. Okt 2010, 16:53
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
  Mit Zitat antworten Zitat
Benutzerbild von Lee500
Lee500

Registriert seit: 18. Sep 2006
39 Beiträge
 
Delphi 2010 Architect
 
#3

AW: Gruppiertes Sortieren

  Alt 31. Okt 2010, 18:03
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
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 15. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#4

AW: Gruppiertes Sortieren

  Alt 31. Okt 2010, 22:37
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.
  Mit Zitat antworten Zitat
Benutzerbild von Lee500
Lee500

Registriert seit: 18. Sep 2006
39 Beiträge
 
Delphi 2010 Architect
 
#5

AW: Gruppiertes Sortieren

  Alt 1. Nov 2010, 00:55
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.

Geändert von Lee500 ( 1. Nov 2010 um 19:57 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 20:57 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz