kosten minimieren
-
Hallo
ich habe mehrere N dimensionale vektoren. diese möchte ich nach einem gewissen
kriterium sortieren: das aktuelle element soll dem vorgänger so ähnlich wie
möglich sein, sprich möglichst viele elemente sollen gleich sein. dazu
habe ich einen weiteren vektor der eine art "kostenfaktor" darstellt.das ganze ist recht schwer zu verstehen daher ein beispiel:
ausgangsvektoren:
{1, 2, 3, 4} // vek1 {1, 2, 3, 3} // vek2 {2, 5, 3, 4} // vek3
kostenvektor
{1, 2, 4, 8} // letztes element hat die höchste priorität
nach diesem vektor bewertet sähe das so aus:
{1, 2, 3, 4} // vek1 {1, 2, 3, 3} // vek2 // element 4 ändert sich: kosten = 8 {2, 5, 3, 4} // vek3 // element 1, 2 und 4 ändert sich: kosten = 1 + 2 + 8 = 11
insgesamt also 19. wenn man das ganze umsortiert hat man:
{2, 5, 3, 4} // vek3 {1, 2, 3, 4} // vek1 // element 1 und 2 ändert sich: kosten = 1 + 2 = 3 {1, 2, 3, 3} // vek2 // element 4 ändert sich: kosten = 8
insgesamt macht das 11
ich will jetzt eine beliebige anzahl von vektoren nach diesem prinzip sortieren.
dabei spielt es keine rolle wieweit der wert sich ändert. nur ob er sich
ändert ist relevant.ich hoffe da gibt es einen algorithmus für
vielen dank an euch schon mal fürs durchlesen und im voraus
MfG keksdoser
-
Falls N und die Zahl der Vektoren wirklich groß sind und es nicht so wichtig ist, ob tatsächlich das Minimum oder nur etwas in der Nähe des Minumums gefunden wird, dann könnte man eine Monte Carlo Methode anwenden.
Für den Fall eines exakten Ergebnisses fällt mir spontan nichts besseres als systematisches Durchprobieren mit Nebenbedingungen ein, muss mal länger darüber Nachdenken.
-
N liegt so um die 6, die anzahl der vektoren kann jedoch leicht ~10000 werden.
muss nicht 100% exakt sein, aber gut sollte es schon werden
-
Also du berechnest die Kosten fuer alle Paare und speicherst sie in einer Adjazenzmatrix (Nachbarschaftsmatrix). Da sie symmetrisch ist, sollte es etwa O( 0.5 n(n-1) ) Schritte benoetigen. Danach loest du das Traveling Salesman Problem fuer deine 10.000 Staedte. Eine gute Uebersicht laesst sich hier finden: http://www.tsp.gatech.edu/index.html . Wikipedia ist sowieso immer dein Freund, einige Heuristiken werden dort genannt. Das Ganze ist zwar NP-vollstaendig, kann aber lokal approximiert werden. Es gibt einige Programmbibliotheken, die dir vielleicht weiterhelfen: http://www.tsp.gatech.edu/concorde/index.html . Trotzdem sind 10.000 vollstaendig verbundene "Staedte" eine harte Nuss. Hilfreich ist dann vielleicht, auch eine untere Schranke abzuschaetzen und mit dem tatsaechlichen Wert zu vergleichen. Dann kann abgebrochen werden, wenn man ihn als gut genug empfindet.
-
hm das hatte ich befürchtet.
nun ja ich werde mir das mal angucken und wohl auch so machen.
hoffe es wird nicht zu langsam *schauder*vielen dank dir nocheinmal
wenn ich wo nicht weiterkomme,melde ich mich
nocheinmalMfG keksdoser