Nahezu präziese Schleife

[Hazzardous]

Moin Moin,

ich sitzt grade vor folgendem Problem. Ich habe eine gefüllte Datenbank mit Liedern. Titel, Länge etc...

Aus diesen Titeln wird eine Playliste generiert. Für jede Stunde gibt es unterschiedliche Kriterien. Darum wird erst eine Stunde der Playliste zusammengebaut, dann werden die Stunden zusammengesetzt und wir erhalten eine 24 Stunden Playliste.

Hier der Code der eine Stunde zusammenbaut:

$hour_index = 0;            
while($second_puffer <= $hour_index){

                $flag = false;
                $show = rand_array($temparray);


                if(! in_array($show, $playlist)){
                    array_push($playlist, $show);
                    $flag = true;

                    //echo $overall_time."-".date("H:i",$overall_time)."r>";
                    if($overall_time == ""){ $overall_time = "1";}
                    $content .= '<Song id="'.$temparray[$show]["id"].'" begin="'.date("H:i",$overall_time).'" />';
                    $ki = 0;

                }else{
                    $ki++;
                    $flag = false;
                }
                if($ki == 5){
                    $flag = true;
                    array_push($playlist, $show);
                    $content .= '<Song id="'.$temparray[$show]["id"].'" begin="'.date("H:i",$overall_time).'" />';
                    $ki = 0;
                }
                $overall_time = $overall_time+$temparray[$show]["laenge"];

            

                //Schleife solange durchlaufen bis eine Stunde ($hour_index) voll ist.

                $second_puffer = $second_puffer+$temparray[$show]["laenge"];

            } 

Nun habe ich das Problem das die Stunden zwischen 3600 und 4000 Sekunden lang sind. Und es sollten nicht mehr als 3600 sein. Nur leider habe ich keinen Ansatz wie ich dies verhindern könnte.

[onemorenerd]

http://de.wikipedia.org/wiki/RUCKSACK - ist es das?

[Hazzardous]

Ja, scheint mir so.

[onemorenerd]

Man kann es also nur bei hinreichend wenig Songs wirklich berechnen, wenn es größere Dimensionen annimmt, lediglich approximieren.

Aber eine ungefähre Lösung würde dir ja schon reichen, also versuchen wir es mal.

Zum Beispiel so (Greedy): Zuerst den längsten Song in die Playlist packen, dann den zweitlängsten usw., bis der nächstlängste nicht mehr reinpaßt. Dann wird aus der (sortierten) Liste der noch unbenutzten Songs einer gesucht, der noch reinpaßt. Das kann bei Bedarf wiederholt werden.

Nachteil: Es landen vor allem die langen Songs auf der Playlist, d. h. hier wird implizit gewichtet. Na ja und man will nicht immer das gleiche hören, oder?

Also mit etwas Zufall nachwürzen (Random):

while (nicht alle Songs verbraucht und Playlist nicht voll) {
    wähle zufällig einen Song;
    if (Song paßt noch in Playlist) {
        setze Song auf Playlist;
        if (Wiederholungen nicht erwünscht) {
            entferne Song aus Liste der verfügbaren Songs;
        }
    } else {
        entferne Song aus Liste der verfügbaren Songs;
    }
}

Nachteil: Sowohl Greedy als auch Random liefern (zumindest theoretisch) beliebig schlechte Ergebnisse. Man kann nicht sagen, die Lösung ist nur soundsoweit vom Optimum entfernt. Blöd, denn genau das willst du ja.

Aber beide Ansätze kann man verstricken.

Erstmal einschränken: Die vorgegebene Länge der Playlist (l = 3600) darf nur in gewissen Grenzen überschritten werden (max_l = l + 180). Wir wollen eine Mindestlänge (min_l = l - 180), damit wir zufrieden sind. Außer der Menge aller Songs (s) und der Playlist (p) benötigen wir noch eine Hilfsliste (h).

while (length(p) < min_l && count(s) > 0) {
    song = random(s);    // zufälligen Song auswählen
    if (length(p) + length(song) <= max_l) {
        if (Wiederholungen nicht erwünscht) {
            if (song noch nicht in p) {
                p = p + song;
            }
        } else {
            p = p + song;
        }
    } else {
        h = h + song;
    }
    s = s - song;
}

if (length(p) >= min_l)
    exit(p);    // fertig.

Halt! Schauen wir doch mal was wir jetzt haben:
p enthält eine zufällige Auswahl aus s, die Gesamtlänge von p ist kleiner als das geforderte Minimum.
s ist leer, sonst wären wir nicht im else-Zweig gelandet.
h enthält alle Songs, die nicht in p sind und keiner davon kann mehr zu p hinzugefügt werden, ohne die zulässige Gesamtlänge zu überschreiten.

p = sort(p);    // von lang nach kurz
h = sort(h);    // von lang nach kurz
for (i = count(p); i > 0; i--) {
    if (length(p[i]) > h[count(h)]) {    // gibt es kürzere Songs in h
        for (j = 0; j < count(h); j++) {
            if ((length(p) - length(p[i]) + length(h[j])) < max_l) {
                p = p - p[i] + h[j];
                h = h - h[j];
                if (length(p) > min_l) {
                    exit(p);
                } else {
                    break 1;  // innere Schleife verlassen
                }
            }
        }
    }
}

Jetzt haben wir für jeden Song in der Playlist versucht, ob man ihn entfernen und den so noch größeren Freiraum durch einen Song von der Hilfsliste auffüllen kann.
Soweit ist der Algorithmus noch unfertig, denn wenn wir jetzt die geforderte Playlist-Länge noch nicht erreicht haben, müßte versucht werden, zwei Songs durch einen oder mehrere zu ersetzen. Dann drei Songs, vier, ... bis man letztlich doch alle Permutationen durchprobiert hat.

Wir wissen aber, dass uns das Testen aller Permutationen wieder in NP führt. Also muß man eh irgendwann abbrechen.
Wenn du viele Songs hast und deren Längen gut verteilt sind, dann solltest du mit geeigneten Schwellwerten schon zu guten Ergebnissen kommen.

Lang lebe NP!

[Hazzardous]

Ich danke dir für die ausführliche Dokumentation. Werde mich mal näher mit der Thematik befassen. Der Ansatz nach Greedy ist auf dem ersten Blick zu unflexibel. Also wird es wohl auf eine Annäherung mit Schwellwerten hinauslaufen.

Sobald ich einen Ansatz umgesetzt habe werde ich ihn mal posten.

[quarks]

Eine effiziente Lösung kannst du wohl nur erreichen, wenn es dir möglich ist z.B den letzten Song abzubrechen bzw wenn du selbst seine Dauer bestimmen kannst.