jemand ahnung von dynamischer programmierung?

[kane]

also noch kann ich net garantieren, dass meine lösung korrekt ist, aber ich bin mir relativ sicher.

eigentlich ist es ähnlich deinem, count y, aber es kopiert keine arrays^^ benötigt dafür aber vermutlich ca. n/k mal mehr speicher.

ich werds wohl heute abend noch reintippen, jetzt grad muss ich noch was anderes erledigen

[Prinegon]

1110101000101000101

exceptions: 9

1p110101000101000101q | p_ex=0
11p10101000101000101q | p_ex=0
111p0101000101000101q | p_ex=0
1110p101000101000101q | p_ex=1
1110p10100010100010q1 | p_ex=1 q_ex=0
1110p1010001010001q01 | p_ex=1 q_ex=1
1110p101000101000q101 | p_ex=1 q_ex=1
1110p10100010100q0101 | p_ex=1 q_ex=2
11101p0100010100q0101 | p_ex=1 q_ex=2
111010p100010100q0101 | p_ex=2 q_ex=2
111010p10001010q00101 | p_ex=2 q_ex=2
111010p1000101q000101 | p_ex=2 q_ex=2
111010p100010q1000101 | p_ex=2 q_ex=3
1110101p00010q1000101 | p_ex=2 q_ex=3
11101010p0010q1000101 | p_ex=3 q_ex=3
11101010p001q01000101 | p_ex=3 q_ex=3
11101010p00q101000101 | p_ex=3 q_ex=4
111010100p0q101000101 | p_ex=4 q_ex=4
1110101000pq101000101 | p_ex=5 q_ex=4
break;
1110101000 + 101000101

1p110101000q | p_ex=0
11p10101000q | p_ex=0
111p0101000q | p_ex=0
1110p101000q | p_ex=1
1110p10100q0 | p_ex=1 q_ex=0
1110p1010q00 | p_ex=1 q_ex=0
1110p101q000 | p_ex=1 q_ex=0
1110p10q1000 | p_ex=1 q_ex=1
1110p1q01000 | p_ex=1 q_ex=1
1110pq101000 | p_ex=1 q_ex=2
break;
1110 + 101000

Insofern würde bei deinem Beispiel mein Algorithmus den String in die Teilstrings:
1110 + 101000 + 101000101
zerteilen, mit den Exceptions: 1, 2, und 4, also insgesamt 7 exceptions.

Eine optimale Antwort wäre hier:
111 + 010100010100010 + 1 mit den Exceptions: 0, 5 und 0
oder11101 + 0100010100010 + 1 mit den Exceptions: 1, 4 und 0
oder 1110101 + 00010100010 + 1 mit den Exceptions: 2,3 und 0

Insofern hast du recht, mein Algorithmus ist falsch, da ich zu früh einen Teil des Strings vollkommen unberücksichtigt lasse.
Sorry

[kane]

da muss kein sorry her ^^
passt schon. keine sorge, an einen local approach algo wie den deinen hab ich auch gedacht ^^ aber relativ schnell verworfen,w enn ich ehrlich bin.
ich hab eigentlich jetzt sehr lange immer nen O(k*n^2) algo gehabt, der aber auf jeden fall immer unter garantie ne optimale lösung ausgespuckt hat.

[damh]

Ich habe jetzt ein paar Tests gemacht und einfach mal die Operationen zählen lassen. Das Ergebnis zeigt das mein Algo. in etwa O(k*n) (vielleicht auch O(ln(k)*n)) hat. Einen Beweis dafür kann ich allerdings nicht liefern:

Code: Alles auswählen

Beispiel 1: Parameter 1101001.....1001 490 2 0 0 10
Also Version 2; nur 1 optimale Lösung wird im Speicher behalten; keine Ausgabe; Schrittweite 1 und 10
n=490; k=1; Gesamte Operationen= 490; k*n=490    
n=490; k=2; Gesamte Operationen= 1340; k*n=980   
n=490; k=3; Gesamte Operationen= 3319; k*n=1470  
n=490; k=4; Gesamte Operationen= 4359; k*n=1960   
n=490; k=5; Gesamte Operationen= 6250; k*n=2450   
n=490; k=6; Gesamte Operationen= 7213; k*n=2940   
n=490; k=7; Gesamte Operationen= 8869; k*n=3430   
n=490; k=8; Gesamte Operationen= 9767; k*n=3920   
n=490; k=9; Gesamte Operationen= 11211; k*n=4410  
n=490; k=10; Gesamte Operationen= 12041; k*n=4900 
n=490; k=11; Gesamte Operationen= 13261; k*n=5390 
n=490; k=12; Gesamte Operationen= 14065; k*n=5880 
n=490; k=13; Gesamte Operationen= 15153; k*n=6370 
n=490; k=14; Gesamte Operationen= 15888; k*n=6860 
n=490; k=15; Gesamte Operationen= 16816; k*n=7350 
n=490; k=16; Gesamte Operationen= 17537; k*n=7840 
n=490; k=17; Gesamte Operationen= 18342; k*n=8330 
n=490; k=18; Gesamte Operationen= 19008; k*n=8820 
n=490; k=19; Gesamte Operationen= 19656; k*n=9310 
n=490; k=20; Gesamte Operationen= 20285; k*n=9800 
n=490; k=21; Gesamte Operationen= 20783; k*n=10290
n=490; k=22; Gesamte Operationen= 21368; k*n=10780
n=490; k=23; Gesamte Operationen= 21852; k*n=11270
n=490; k=24; Gesamte Operationen= 22417; k*n=11760
n=490; k=25; Gesamte Operationen= 22887; k*n=12250
n=490; k=26; Gesamte Operationen= 23417; k*n=12740
n=490; k=27; Gesamte Operationen= 23871; k*n=13230
n=490; k=28; Gesamte Operationen= 24390; k*n=13720
n=490; k=29; Gesamte Operationen= 24839; k*n=14210
n=490; k=30; Gesamte Operationen= 25337; k*n=14700
n=490; k=31; Gesamte Operationen= 25771; k*n=15190
n=490; k=41; Gesamte Operationen= 30164; k*n=20090
n=490; k=51; Gesamte Operationen= 34404; k*n=24990 
n=490; k=61; Gesamte Operationen= 38518; k*n=29890 
n=490; k=71; Gesamte Operationen= 42520; k*n=34790 
n=490; k=81; Gesamte Operationen= 46382; k*n=39690 
n=490; k=91; Gesamte Operationen= 50096; k*n=44590 
n=490; k=101; Gesamte Operationen= 53685; k*n=49490
n=490; k=111; Gesamte Operationen= 57154; k*n=54390
n=490; k=121; Gesamte Operationen= 60474; k*n=59290
n=490; k=131; Gesamte Operationen= 63656; k*n=64190
n=490; k=141; Gesamte Operationen= 66724; k*n=69090
n=490; k=151; Gesamte Operationen= 69664; k*n=73990
n=490; k=161; Gesamte Operationen= 72458; k*n=78890
n=490; k=171; Gesamte Operationen= 75112; k*n=83790
n=490; k=181; Gesamte Operationen= 77653; k*n=88690
n=490; k=191; Gesamte Operationen= 80056; k*n=93590
n=490; k=201; Gesamte Operationen= 82308; k*n=98490
n=490; k=211; Gesamte Operationen= 84440; k*n=103390
n=490; k=221; Gesamte Operationen= 86455; k*n=108290

Beispiel 2:Parameter 1101001.....1001 490 2 0 0 10
Also Version 2; nur 1 optimale Lösung wird im Speicher behalten; keine Ausgabe; Schrittweite 10
n=617; k=1; Gesamte Operationen= 617; k*n=617    
n=617; k=11; Gesamte Operationen= 17605; k*n=6787 
n=617; k=21; Gesamte Operationen= 28943; k*n=12957
n=617; k=31; Gesamte Operationen= 35799; k*n=19127
n=617; k=41; Gesamte Operationen= 41621; k*n=25297
n=617; k=51; Gesamte Operationen= 47131; k*n=31467 
n=617; k=61; Gesamte Operationen= 52515; k*n=37637 
n=617; k=71; Gesamte Operationen= 57787; k*n=43807 
n=617; k=81; Gesamte Operationen= 62919; k*n=49977 
n=617; k=91; Gesamte Operationen= 67903; k*n=56147 
n=617; k=101; Gesamte Operationen= 72762; k*n=62317
n=617; k=111; Gesamte Operationen= 77501; k*n=68487
n=617; k=121; Gesamte Operationen= 82091; k*n=74657
n=617; k=131; Gesamte Operationen= 86543; k*n=80827
n=617; k=141; Gesamte Operationen= 90881; k*n=86997
n=617; k=151; Gesamte Operationen= 95091; k*n=93167
n=617; k=161; Gesamte Operationen= 99155; k*n=99337
n=617; k=171; Gesamte Operationen= 103079; k*n=105507
n=617; k=181; Gesamte Operationen= 106890; k*n=111677
n=617; k=191; Gesamte Operationen= 110563; k*n=117847
n=617; k=201; Gesamte Operationen= 114085; k*n=124017
n=617; k=211; Gesamte Operationen= 117487; k*n=130187
n=617; k=221; Gesamte Operationen= 120772; k*n=136357
n=617; k=231; Gesamte Operationen= 123915; k*n=142527

Beispiel 3: wie oben nur längere Eingabe:
n=1070; k=1; Gesamte Operationen= 1070; k*n=1070   
n=1070; k=11; Gesamte Operationen= 32015; k*n=11770 
n=1070; k=21; Gesamte Operationen= 54638; k*n=22470 
n=1070; k=31; Gesamte Operationen= 71398; k*n=33170 
n=1070; k=41; Gesamte Operationen= 84682; k*n=43870  
n=1070; k=51; Gesamte Operationen= 96303; k*n=54570  
n=1070; k=61; Gesamte Operationen= 107280; k*n=65270 
n=1070; k=71; Gesamte Operationen= 117640; k*n=75970 
n=1070; k=81; Gesamte Operationen= 127377; k*n=86670 
n=1070; k=91; Gesamte Operationen= 136662; k*n=97370 
n=1070; k=101; Gesamte Operationen= 145821; k*n=108070
n=1070; k=111; Gesamte Operationen= 154833; k*n=118770
n=1070; k=121; Gesamte Operationen= 163730; k*n=129470
n=1070; k=131; Gesamte Operationen= 172511; k*n=140170
n=1070; k=141; Gesamte Operationen= 181160; k*n=150870
n=1070; k=151; Gesamte Operationen= 189681; k*n=161570
n=1070; k=161; Gesamte Operationen= 198068; k*n=172270
n=1070; k=171; Gesamte Operationen= 206321; k*n=182970
n=1070; k=181; Gesamte Operationen= 214469; k*n=193670
n=1070; k=191; Gesamte Operationen= 222498; k*n=204370
n=1070; k=201; Gesamte Operationen= 230339; k*n=215070
n=1070; k=211; Gesamte Operationen= 238035; k*n=225770
n=1070; k=221; Gesamte Operationen= 245620; k*n=236470
n=1070; k=231; Gesamte Operationen= 253066; k*n=247170
n=1070; k=241; Gesamte Operationen= 260349; k*n=257870
n=1070; k=251; Gesamte Operationen= 267513; k*n=268570
n=1070; k=261; Gesamte Operationen= 274534; k*n=279270
n=1070; k=271; Gesamte Operationen= 281395; k*n=289970
n=1070; k=281; Gesamte Operationen= 288139; k*n=300670
n=1070; k=291; Gesamte Operationen= 294780; k*n=311370
n=1070; k=301; Gesamte Operationen= 301269; k*n=322070
n=1070; k=351; Gesamte Operationen= 331499; k*n=375570
n=1070; k=401; Gesamte Operationen= 358343; k*n=429070
n=1070; k=451; Gesamte Operationen= 381646; k*n=482570
n=1070; k=501; Gesamte Operationen= 401551; k*n=536070
n=1070; k=551; Gesamte Operationen= 417953; k*n=589570
n=1070; k=601; Gesamte Operationen= 430910; k*n=643070
n=1070; k=651; Gesamte Operationen= 440418; k*n=696570
n=1070; k=701; Gesamte Operationen= 446429; k*n=750070
n=1070; k=751; Gesamte Operationen= 449066; k*n=803570
n=1070; k=801; Gesamte Operationen= 449383; k*n=857070  // Hier wurde bereits die Sättigung erreicht => d.h. es gibt nur noch substrings aus gleichen Zeichen
n=1070; k=851; Gesamte Operationen= 449383; k*n=910570

Gruß damh
PS: Der neue Code ist natürlich auch unter dem alten Link zu finden

[kane]

das problem ist generell, dass dein k natürlich im vergleich zu n nicht zuuu groß werden darf. wenn du k = 1/20n oder sowas immer hast dürfte dein algo sich auch etwas anders entwickeln, schätz ich mal.



ok, jetzt aber endlich mal zu meiner lösung, die hoffentlich korrekt ist:


idee: im laufe des algos wird eine tabelle der größe k*n aufgebaut, k zeilen, n spalten, wobei ein zelleintrag nur geschrieben und nie upgedated wird und das je zelle in konstanter zeit, womit eine laufzeit von O(kn) herauskommt.

input ist der string x1x2x3.......xn (und evtl k)

mit c(i,j) sei die zelle in zeile i und spalte j benannt, in ihr stecken (nach berechnung der zelle) folgende informationen:
OPT(i,j) = "optimale (minimal mögliche) anzahl exceptions im substring x1x2.....xj bei unterteilung in i segmente, d.h. mit (i-1) delimiter" (wichtig: das ist ein integerwert, es wird keine information über die zusammensetzung der information gespeichert)
o(i,j) = "die anzahl einsen (ones) im letzten segment der gegenwärtigen optimallösung"
z(i,j) = "die anzahl nullen (zeros) im letzten segment der gegenwärtigen optimallösung"

wenn ich von optimallösung spreche, dann meine ich nich den wert OPT allein, sondern in der regel die verteilung der delimiter, welche den wert OPT liefern.

wir definieren weiterhin global (wird nicht in der tabelle gespeichert):
z(j) = anzahl nullen im bit xj (d.h. 0 oder 1)
o(j) = anzahl einsen im bit xj (d.h. 0 oder 1)
1, wenn o(i, j) > z(i, j)
m(i, j) = { #, wenn o(i, j) = z(i, j)
0, wenn o(i, j) < z(i, j)



initialisierung:
=========

zu beginn konstruieren wir
a) die erste spalte, d.h. unterteilung des substrings "x1" in optimale segmente - offensichtlich ist OPT hier überall 0 und wenn x1 = "1" ist, wird überall o(i, 1) auf 1 gesetzt, ansonsten z(i, 1).
b) die erste zeile. die erste zeile behandelt den fall "ein segment", d.h. es werden keine delimiter eingefügt.
da lässt sich jeder zelleintrag ganz leicht berechnen, wir lesen einfach jedes zeichen bit für bit ein und erhöhen je nach eingelesenem bit z(1, j) oder o(1, j) um eins. die optimale lösung OPT(1, j) berechnet sich ganz einfach als minimum der beiden werte.



main part:
=======

jetzt kommen wir zum interessanten teil, dem auffüllen des rests der tabelle:
die tabelle wird jetzt reihe für reihe aufgefüllt und jede reihe selbst zelle für zelle.

c(i, j) sei gerade berechnet worden. ziel: berechne c(i, j+1).

lese bit x_{j+1} ein.

IF (x_{j+1} == m(i, j) OR m(i, j) = #) THEN
/* der "langweilige" fall: das beibehalten der derzeitigen lösung ist unbedenklich, da das eingelesene zeichen zur mehrheit des letzten segments gehört und daher keine exception ist, oder weil es das gleichgewicht zerstört, was aber auch die anzahl exceptions gleich lässt */
z(i, j+1) = z(i, j) + z(j+1)
o(i, j+1) = o(i, j) + o(j+1)
OPT(i, j+1) = OPT(i, j)
ELSE
/* der interessante fall: das eingelesene zeichen gehört zur minderheit und würde damit die anzahl exceptions erhöhen. jetzt wird das entweder (schweren herzens) akzeptiert und OPT um eins erhöht, oder nach einer anderen lösung gesucht; das geht in konstanter zeit, und warum das korrekt ist, folgt weiter unten */
IF (OPT(i, j) + 1 <= OPT(i - 1, j)) THEN
/* behalte gegenwärtige lösung bei und akzeptiere exception */
z(i, j+1) = z(i, j) + z(j+1)
o(i, j+1) = o(i, j) + o(j+1)
OPT(i, j+1) = OPT(i, j) + 1
ELSE
/* verwerfe gegenwärtige lösung, suche lösung für substring x1x2...xj, welche nur (i-1) segmente bzw. (i-2) delimiter hat und füge den letzten erlaubten, d.h. (i-1)ten delimiter direkt zwischen xj und x_{j+1} ein */
z(i, j+1) = z(j+1) //neues segment erzeugt, resette z und o
o(i, j+1) = o(j+1)
OPT(i, j+1) = OPT(i - 1, j) //das neue zeichen gehört zur mehrheit des neuen segments
END IF
END IF


das wird für jede zelle wiederholt und da eine abfrage eines werts in einem array auch nur konstante zeit kostet, kostet hier jeder zelleneintrag konstante zeit und damit der ganze algo nur O(kn)

die frage, die jetzt sicher jedem aufkommt (und auch aufkommen sollte!), ist, warum arbeitet der algorithmus korrekt?



proof of correctness:
=============

erstmal: wenn ich die anzahl erlaubter delimiter festhalte, aber meinen string vergrößere, dann wird die anzahl exceptions garantiert nicht weniger, das ist klar.
annahme: jede zelle c(f, g) mit f < i oder (f = i und g <= j) besitzt korrekte einträge für eine optimale lösung mit f segmenten auf dem substring x1x2...xg.
z.z.: c(i, j+1) besitzt nach obigem algo korrekte information. der rest folgt dann per induktion.
ok. angenommen, obiger algo produziert keine korrekte lösung. dann betrachten wir einfach mal die ECHTE korrekte lösung.
fall 1: der letzte delimiter der ECHTEN lösung ist zwischen xj und x_{j+1}. da unser algo keine korrekte lösung produziert, müssen die (i-2) anderen delimiter anders auf dem substring x1x2....xj aufgeteilt sein. das ist aber ein widerspruch zu der annahme, dass die zelle c(i-1, j) korrekte information enthält.
fall 2: der letzte delimiter der ECHTEN lösung ist VOR xj. in diesem fall wäre diese lösung auch für den substring x1x2.....xj optimal, womit dies ein widerspruch zu der tatsache ist, dass zelle c(i, j) korrekte informationen enthält, weil wir ja diese lösung in unserem algo übernehmen.
damit ist der induktionsschluss gezeigt und der algo arbeitet damit korrekt. jetzt müssen wir nur noch was mit den ganzen integern anfangen, die wir abgespeichert haben.



back-tracing
========

was jetzt noch fehlt, ist das backtracing, bisher haben wir ja überall nur integer gespeichert. wir wollen aber die positionen der delimiter so wie den optimalwert.
den optimalwert können wir ganz einfach ablesen, es ist OPT(k, n).
um die position der delimiter zu kriegen, definiere ich ne kurze hilfsfunktion, die mir beim niederschreiben der lösung hilft ^^
y_{i+1} := y_i + s(i, y_i)
wobei s(i, t) := z(k-i+1, t) + o(k-i+1, t), d.h. in dem segment, in dem x_t liegt, die anzahl bits vom anfang des segments bis zum zeichen x_t
damit kann ich direkt durch berechnung von s(1,n) sehen, wieviel zeichen im letzten segment der optimalen lösung sind. und damit auch die position des letzten delimters: er ist direkt hinter x_{n - s(1, n)}
der vorletzte delimiter ist jetzt eine zeile darüber angesiedelt (warum muss man sich kurz mal überlegen ^^), und um an diesen zu kommen, müssen wir s(2, n - s(1, n)) schritte zurückgehen, also zum zeichen x mit index (n - s(1,n) - s(2,n - s(1,n))) gehen und direkt hinter diesem ist der vorletzte delimiter. usf.
allgemein: berechne die y_i mit startwert y_0 = n, dann ist der (k-i)-te delimiter direkt hinter x_{n - y_i}



END OF FILE



oder doch nicht? ^^

ich werde auf jeden fall "trostpreise" für alle helfer verteilen.
wenn ihr also alle (prinegon, count, damh) mal welt + acc aufzählt, dann werd ich am wochenende mal kleine geschenke verteilen

wer einen fehler in meinem algo findet, darf ihn NICHT behalten!

greetz
kane

[Count Ypsilon]

ok, jetzt aber endlich mal zu meiner lösung, die hoffentlich korrekt ist

Klingt gut, dann war ich mit meiner Lösung einfach eine Dimension zu "flach". Mein allererster Lösungansatz war, einfach sämtliche Lösungen zu speichern, während ich durch den String durchlaufe (also mit einer Lösung starten, diese dann ein Zeichen weiter hinten aufsplitten in eine, die einen Delimiter setzt, und eine dies nicht tut) usw. - bei k gegen n hätte sich dabei die Laufzeit aber Richtung 2^n entwickelt ;-) ... dann dachte ich, der Ansatz mit dem Speichern und einmal durchlaufen ist nicht schlecht, aber man darf halt nicht *zu viel* speichern, also alles irrelevante wegwefen - aber ich habe dann zu viel weggeworfen und statt einer Matrix bloss einen Vektor übrig behalten...

Mein ursprüngliches 2^n-Programm war übrigens sehr kurz und übersichtlich ;-)

Achso - zu Deiner Loesung: Das mit dem Backtracking am Ende, macht das die Sache nicht unnoetig kompliziert? Sollte man nicht einfach die Delimiter-Positionen in den Feldern der Matrix mitspeichern, dann spart man sich das... und nach Speicherbedarf hat ja keiner gefragt...

Danke aber für die nette Unterhaltung.

Y@w7

[kane]

also wenn man alle delimiterpositionen in jedem feld abspeichert, dann würde das die laufzeit auf O(k^2*n) drehen. möglich ist es natürlich auch, die position des letzten delimiters einfach abzuspeichern. das geht natürlich auch, kommt halt aufs selbe hinaus, ist nur leichter durchschaubar - aber ich spiele eben gerne mit mathematischen ausdrücken rum ^^

ich wurde inzwischen übrigens aufgeklärt, dass es für dieses problem sogar NOCH schnellere verfahren gibt, die aber die spezielle 001011... struktur ausnutzen, um eine optimale lösung zu finden.
und NOCHMAL schnellere verfahren gibt es, wenn man nicht an der optimallösung interessiert ist, sondern an einer, die nahe dran ist, approximationsverfahren halt. aber gut, das ist ja oft so (siehe travelling salesman, geht auch polynomiell, wenn man ne fehlerquote von ein paar prozent in kauf nimmt)

die obige lösung glaub ich kann man speichermäßig durch einbindung einer divide&conquer-methode noch weiter reduzieren. da dürfte man dann am ende wohl bei O(n+k) oder so landen.


ich hoffe, es hat net nur dir spaß gemacht, zu tüfteln ^^