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


  • Mod

    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
    nocheinmal

    MfG keksdoser


Anmelden zum Antworten