Registriert seit: 23. Jan 2008
3.686 Beiträge
Delphi 2007 Enterprise
|
Re: Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteil
24. Dez 2009, 02:21
Ein recht naiver Ansatz, der jedoch nicht immer zur optimalen Lösung führt, wäre einfach so zu beginnen wie sx2008 schrieb: Erst in jede Liste ein Wert. Die Liste, die die kleinste Summe hat, bekommt den nächsten Wert, und das so lange bis alles verteilt ist.
Ein möglicher Schritt um das zu optimieren wäre noch, die Ausgangsliste vor ab absteigend zu sortieren. So dass zuerst alle größten Werte verteilt werden, und zum Ende die kleineren kommen, welche dann keine brachialen Unterschiede ("Summensprünge") verusachen.
Das macht es zwar besser, aber die wirklich optimale Lösung wird man nur via Backtracking erhalten können wenn ich das richtig sehe. Das Problem scheint mir NP-vollständig zu sein.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
|