algorithm - tablero - ¿Cómo puedo dividir 24 álbumes de música en 6 listas de reproducción para que el tiempo/duración de ejecución se distribuya de la manera más equitativa posible?

es members cd baby

Question

NOTA: Planeo implementar esto usando Java, pero cualquier explicación simple en inglés de los pasos necesarios en la lógica es bienvenida y apreciada.

Estoy tratando de encontrar una manera de dividir un grupo de 24 álbumes / discos de música en 6 listas de reproducción, de modo que la duración / el tiempo de ejecución de las 6 listas de reproducción sean lo más cercanos posible.

Inicialmente pensé que tal vez podría encontrar todas las posibles permutaciones del problema y luego elaborar una lógica que analice cuál es la mejor división. Incluso creé un hilo para pedir ayuda ayer ( tengo 24 elementos que necesito separar en 6 conjuntos de 4. ¿Qué algoritmo puedo usar para encontrar todas las combinaciones posibles? ). Sin embargo, cuando estuve cerca de encontrar una solución, me di cuenta de que solo encontrar todas las permutaciones del problema tomaría un tiempo increíblemente largo de ejecución, por lo que ese enfoque parece poco práctico.

Así que me preguntaba, ¿hay una manera más rápida de abordar un problema así?

Dado que estos son los tiempos de ejecución de los álbumes en cuestión (en formato MM: SS), ¿cuál es la forma más rápida en que puedo encontrar la división de álbumes en 6 listas de reproducción de 4, de modo que la longitud de cada una de las listas de reproducción sea tan cercana? entre sí como sea posible?

39:03 
41:08 
41:39 
42:54 
44:31 
44:34 
44:40 
45:55 
45:59 
47:06 
47:20 
47:53 
49:35 
49:57 
50:15 
51:35 
51:50 
55:45
58:10 
58:11 
59:48 
59:58   
60:00 
61:08 

Hice los cálculos y considerando el tiempo total para todos los álbumes, tener 6 listas de reproducción que duren 200 minutos y 49 segundos sería perfecto ... pero como la duración de cada álbum probablemente no permita esa división exacta, ¿qué Sería la división más exacta posible es mi pregunta.

NOTA: Realmente podría hacer esto manualmente y obtener una aproximación lo suficientemente cercana que sería suficiente, pero todavía estoy realmente interesado en cómo se puede hacer a través de un programa.

¡Gracias!

Answer 1

Te sugiero que uses un algoritmo de recocido simulado.

Y aquí hay una buena solución derivada de este algoritmo:

[17, 16, 15, 9] 199:39
[3, 14, 10, 24] 199:50
[6, 8, 13, 21]  199:52
[1, 5, 20, 19]  199:55
[4, 23, 2, 18]  199:47
[11, 7, 22, 12] 199:51

Como señaló Steven Skiena en su libro ("The Algorithm Design Manual"), es muy útil usar el método de metaheurística de recocido simulado para encontrar soluciones aceptables en problemas combinatorios de la vida real.

Entonces, como mencionaste, necesitas poner 4 pistas en cada uno de los 6 álbumes, de modo que todos los álbumes tengan aproximadamente la misma duración.

Primero consideremos: ¿qué propiedad necesitamos optimizar?

Desde mi punto de vista, la formulación más adecuada sería: minimizar la desviación estándar de la duración de todos los álbumes. (Pero, si es necesario, puede incluir cualquier otra propiedad más compleja).

Nombremos el valor de una propiedad optimizada como energía .

La idea principal del algoritmo.

Cada estado de nuestro sistema se caracteriza por algún valor de energía. Al realizar algunas acciones en el sistema, podemos cambiar su estado (por ejemplo, intercambiar pistas entre álbumes diferentes).

Además, tenemos alguna propiedad abstracta llamada temperatura .

Cuando el sistema está a alta temperatura, es libre de cambiar su estado a otro estado, incluso si el nuevo estado tiene un valor de energía más alto.

Pero cuando la temperatura es pequeña, el sistema tiende a cambiar su estado principalmente a nuevos estados con valores más bajos de energía.

Por analogía física, la probabilidad de cambiar el estado actual del sistema a un estado con un valor de energía más alto se puede limitar de la misma manera que define la distribución de Boltzmann .

Aquí hay una ilustración de cómo la desviación estándar de las duraciones cambió al derivar la solución desde arriba.

Aquí hay una implementación completa de Java del algoritmo, que proporciona la solución desde arriba.

import java.util.Arrays;
import java.util.Random;

public class SimulatedAnnealingTracksOrdering {

    public static void main(String[] args) {
        int albumsCount = 6;
        int tracksInAlbum = 4;

        Album[] result = generateOptimalTracksOrdering(
                tracksInAlbum,
                albumsCount,
                new Track[] {
                        new Track(1, "39:03"), new Track(2, "41:08"),
                        new Track(3, "41:39"), new Track(4, "42:54"),
                        new Track(5, "44:31"), new Track(6, "44:34"),
                        new Track(7, "44:40"), new Track(8, "45:55"),
                        new Track(9, "45:59"), new Track(10, "47:06"),
                        new Track(11, "47:20"), new Track(12, "47:53"),
                        new Track(13, "49:35"), new Track(14, "49:57"),
                        new Track(15, "50:15"), new Track(16, "51:35"),
                        new Track(17, "51:50"), new Track(18, "55:45"),
                        new Track(19, "58:10"), new Track(20, "58:11"),
                        new Track(21, "59:48"), new Track(22, "59:58"),
                        new Track(23, "60:00"), new Track(24, "61:08"),
                });

        for (Album album : result) {
            System.out.println(album);
        }
    }

    private static Album[] generateOptimalTracksOrdering(
            int tracksInAlbum, int albumsCount, Track[] tracks) {

        // Initialize current solution
        Albums currentSolution =
                new Albums(tracksInAlbum, albumsCount, tracks);
        // Initialize energy of a current solution
        double currentEnergy =
                currentSolution.albumsDurationStandartDeviation();

        System.out.println("Current energy is: " + currentEnergy);

        // Also, we will memorize the solution with smallest value of energy
        Albums bestSolution = currentSolution.clone();
        double bestEnergy = currentEnergy;

        // Constant, which defines the minimal value of energy
        double minEnergy = 0.1;
        // Initial temperature
        double temperature = 150;
        // We will decrease value of temperature, by multiplying on this
        // coefficient
        double alpha = 0.999;
        // Constant, which defines minimal value of temperature
        double minTemperature = 0.1;
        // For each value of temperature - we will perform few probes, before
        // decreasing temperature
        int numberOfProbes = 100;

        Random random = new Random(1);

        while ((temperature > minTemperature)
                && (currentEnergy > minEnergy)) {

            for (int i = 0; i < numberOfProbes; i++) {
                // Generating new state
                currentSolution.randomTracksPermutation();
                double newEnergy =
                        currentSolution.albumsDurationStandartDeviation();

                // As defined by Boltzmann distribution
                double acceptanceProbability = 
                        Math.exp(-(newEnergy - currentEnergy) / temperature);

                // States with smaller energy - will be accepted always
                if ((newEnergy < currentEnergy)
                        || (random.nextDouble() < acceptanceProbability)) {

                    currentEnergy = newEnergy;
                    System.out.println("Current energy is: " + currentEnergy);

                    if (newEnergy < bestEnergy) {
                        bestSolution = currentSolution.clone();
                        bestEnergy = newEnergy;
                    }
                } else {
                    // If state can''t be accepted - rollback to previous state
                    currentSolution.undoLastPermutation();
                }
            }
            // Decreasing temperature
            temperature *= alpha;
        }
        // Return best solution
        return bestSolution.getAlbums();
    }
}

/**
 * Container for bunch of albums
 */
class Albums {
    private Random random = new Random(1);
    private Album[] albums;
    // These fields, are used for memorizing last permutation
    // (needed for rollbacking)
    private Album sourceAlbum;
    private int sourceIndex;
    private Album targetAlbum;
    private int targetIndex;

    public Albums(int tracksInAlbum, int albumsCount, Track[] tracks) {
        // Put all tracks to albums
        this.albums = new Album[albumsCount];
        int t = 0;
        for (int i = 0; i < albumsCount; i++) {
            this.albums[i] = new Album(tracksInAlbum);
            for (int j = 0; j < tracksInAlbum; j++) {
                this.albums[i].set(j, tracks[t]);
                t++;
            }
        }
    }

    /**
     * Calculating standard deviations of albums durations
     */
    public double albumsDurationStandartDeviation() {
        double sumDuration = 0;
        for (Album album : this.albums) {
            sumDuration += album.getDuraion();
        }
        double meanDuration =
                sumDuration / this.albums.length;

        double sumSquareDeviation = 0;
        for (Album album : this.albums) {
            sumSquareDeviation +=
                    Math.pow(album.getDuraion() - meanDuration, 2);
        }
        return Math.sqrt(sumSquareDeviation / this.albums.length);
    }

    /**
     * Performing swapping of random tracks between random albums
     */
    public void randomTracksPermutation() {
        this.sourceAlbum = this.pickRandomAlbum();
        this.sourceIndex =
                this.random.nextInt(this.sourceAlbum.getTracksCount());

        this.targetAlbum = this.pickRandomAlbum();
        this.targetIndex =
                this.random.nextInt(this.targetAlbum.getTracksCount());

        this.swapTracks();
    }

    public void undoLastPermutation() {
        this.swapTracks();
    }

    private void swapTracks() {
        Track sourceTrack = this.sourceAlbum.get(this.sourceIndex);
        Track targetTrack = this.targetAlbum.get(this.targetIndex);

        this.sourceAlbum.set(this.sourceIndex, targetTrack);
        this.targetAlbum.set(this.targetIndex, sourceTrack);
    }

    private Album pickRandomAlbum() {
        int index = this.random.nextInt(this.albums.length);
        return this.albums[index];
    }

    public Album[] getAlbums() {
        return this.albums;
    }

    private Albums() {
        // Needed for clonning
    }

    @Override
    protected Albums clone() {
        Albums cloned = new Albums();
        cloned.albums = new Album[this.albums.length];
        for (int i = 0; i < this.albums.length; i++) {
            cloned.albums[i] = this.albums[i].clone();
        }
        return cloned;
    }
}

/**
 * Container for tracks
 */
class Album {
    private Track[] tracks;

    public Album(int size) {
        this.tracks = new Track[size];
    }

    /**
     * Duration of album == sum of durations of tracks
     */
    public int getDuraion() {
        int acc = 0;
        for (Track track : this.tracks) {
            acc += track.getDuration();
        }
        return acc;
    }

    public Track get(int trackNum) {
        return this.tracks[trackNum];
    }

    public void set(int trackNum, Track track) {
        this.tracks[trackNum] = track;
    }

    public int getTracksCount() {
        return this.tracks.length;
    }

    public Track[] getTracks() {
        return this.tracks;
    }

    @Override
    protected Album clone() {
        Album cloned = new Album(this.tracks.length);
        for (int i = 0; i < this.tracks.length; i++) {
            cloned.tracks[i] = this.tracks[i];
        }
        return cloned;
    }

    /**
     * Displaying duration in MM:SS format
     */
    @Override
    public String toString() {
        int duraion = this.getDuraion();
        String duration_MM_SS = (duraion / 60) + ":" + (duraion % 60);
        return Arrays.toString(this.tracks) + "/t" + duration_MM_SS;
    }

}

class Track {
    private final int id;
    private final int durationInSeconds;

    public Track(int id, String duration_MM_SS) {
        this.id = id;
        this.durationInSeconds =
                this.parseDuration(duration_MM_SS);
    }

    /**
     * Converting MM:SS duration to seconds
     */
    private int parseDuration(String duration_MM_SS) {
        String[] parts = duration_MM_SS.split(":");
        return (Integer.parseInt(parts[0]) * 60)
                + Integer.parseInt(parts[1]);
    }

    public int getDuration() {
        return this.durationInSeconds;
    }

    public int getId() {
        return this.id;
    }

    @Override
    public String toString() {
        return Integer.toString(this.id);
    }
}

Answer 2

Con un algoritmo de búsqueda más inteligente que la fuerza bruta, no tenemos que pasar por todas las posibilidades 1e12. Primero convertimos la entrada, enumeramos todos los conjuntos de cuatro y los ordenamos por su proximidad al tiempo objetivo.

import heapq
import itertools
import re

def secondsfromstring(s):
    minutes, seconds = s.split('':'')
    return int(minutes) * 60 + int(seconds)

def stringfromseconds(seconds):
    minutes, seconds = divmod(seconds, 60)
    return ''{}:{:02}''.format(minutes, seconds)

# for simplicity, these have to be pairwise distinct
stringtimes = ''''''39:03 41:08 41:39 42:54 44:31 44:34
                 44:40 45:55 45:59 47:06 47:20 47:53
                 49:35 49:57 50:15 51:35 51:50 55:45
                 58:10 58:11 59:48 59:58 60:00 61:08''''''
times = [secondsfromstring(s) for s in stringtimes.split()]
quads = [frozenset(quad) for quad in itertools.combinations(times, 4)]
targettime = sum(times) / 6
quads.sort(key=lambda quad: abs(sum(quad) - targettime))

Ahora viene una búsqueda. Mantenemos una cola de prioridad con soluciones parciales, ordenadas por la mínima desviación máxima posible del tiempo objetivo. La cola de prioridad nos permite explorar primero las soluciones parciales más prometedoras.

queue = [(0, frozenset(times), [])]
while True:
    i, remaining, sofar = heapq.heappop(queue)
    if not remaining:
        for quad in sofar:
            print(stringfromseconds(sum(quad)), '':'',
                  *(stringfromseconds(time) for time in quad))
        break
    while i < len(quads):
        quad = quads[i]
        if quad.issubset(remaining):
            heapq.heappush(queue, (i + 1, remaining, sofar))
            heapq.heappush(queue, (i + 1, remaining - quad, sofar + [quad]))
            break
        i += 1

En unos pocos segundos, este código escupe la siguiente respuesta óptima. (Tuvimos suerte, ya que este código está trabajando en el objetivo ligeramente modificado de minimizar la desviación máxima del tiempo objetivo; con el programa más complicado a continuación, podemos minimizar la diferencia entre mínimo y máximo, que resulta ser la misma agrupación .)

199:50 : 47:06 41:39 61:08 49:57
199:52 : 44:34 45:55 59:48 49:35
199:45 : 55:45 41:08 59:58 42:54
199:53 : 44:40 47:20 60:00 47:53
199:55 : 58:10 44:31 58:11 39:03
199:39 : 51:35 50:15 51:50 45:59

El programa que optimiza el objetivo max minus min está abajo. En comparación con el programa anterior, no se detiene después de la primera solución, sino que espera hasta que comencemos a considerar los conjuntos cuya desviación del objetivo es mayor que el máximo máximo mínimo mínimo de soluciones que hemos encontrado hasta ahora. Luego sale lo mejor.

import heapq
import itertools
import re

def secondsfromstring(s):
    minutes, seconds = s.split('':'')
    return int(minutes) * 60 + int(seconds)

def stringfromseconds(seconds):
    minutes, seconds = divmod(seconds, 60)
    return ''{}:{:02}''.format(minutes, seconds)

# for simplicity, these have to be pairwise distinct
stringtimes = ''''''39:03 41:08 41:39 42:54 44:31 44:34
                 44:40 45:55 45:59 47:06 47:20 47:53
                 49:35 49:57 50:15 51:35 51:50 55:45
                 58:10 58:11 59:48 59:58 60:00 61:08''''''
times = [secondsfromstring(s) for s in stringtimes.split()]
quads = [frozenset(quad) for quad in itertools.combinations(times, 4)]
targettime = sum(times) / 6
quads.sort(key=lambda quad: abs(sum(quad) - targettime))

def span(solution):
    quadtimes = [sum(quad) for quad in solution]
    return max(quadtimes) - min(quadtimes)

candidates = []
bound = None
queue = [(0, frozenset(times), [])]
while True:
    i, remaining, sofar = heapq.heappop(queue)
    if not remaining:
        candidates.append(sofar)
        newbound = span(sofar)
        if bound is None or newbound < bound: bound = newbound
    if bound is not None and abs(sum(quads[i]) - targettime) >= bound: break
    while i < len(quads):
        quad = quads[i]
        i += 1
        if quad.issubset(remaining):
            heapq.heappush(queue, (i, remaining, sofar))
            heapq.heappush(queue, (i, remaining - quad, sofar + [quad]))
            break
best = min(candidates, key=span)
for quad in best:
    print(stringfromseconds(sum(quad)), '':'',
          *(stringfromseconds(time) for time in quad))

Answer 3

Esto es equivalente * a la programación de multiprocesador si considera cada álbum como un trabajo y cada lista de reproducción como un procesador, y encontrar una solución óptima es NP-difícil.

Sin embargo, hay algoritmos eficientes que dan resultados decentes pero no necesariamente óptimos. Por ejemplo, ordenar los álbumes por longitud y agregar repetidamente el álbum más largo a la lista de reproducción más corta.

Si numeramos los álbumes del 1 al 24 del más corto al más largo, este algoritmo proporciona la siguiente división.

{24, 13,  9,  6}  (201:16)
{23, 14, 12,  2}  (198:58)
{22, 15, 10,  4}  (200:13)
{21, 16,  8,  5}  (201:49)
{20, 17, 11,  3}  (199:00)
{19, 18,  7,  1}  (197:38)

* Si consideramos que "distribuido uniformemente" significa que se minimiza la longitud de la lista de reproducción más larga.

Answer 4

Esto también puede ser un comentario, pero es demasiado largo, así que lo publico como respuesta. Esta es una pequeña mejora fácil de codificar para la solución de Hammar. Este algoritmo no le ofrece una solución óptima, pero encuentra una mejor.

Puedes comenzar con el codicioso algoritmo de Hammar para llenar las listas de reproducción con álbumes. A continuación, todo lo que tienes que hacer es recorrerlos varias veces. Sea D la diferencia entre la longitud total de la lista de reproducción A y la lista de reproducción B, donde length(A)>length(B) . Recorra las listas de reproducción A y B y si encuentra los álbumes x /in A y y /in B que muestran que x>y && xy<D , intercambie x e y.
Esto me dio los siguientes resultados:

{7,8,22,13}   200:8
{2,11,24,15}  199:51
{4,10,23,14}  199:57
{3,17,12,19}  199:32
{5,16,21,6}   200:28
{1,18,9,20}   198:58

Answer 5

Para que valga la pena, antes de que stemm publicara su algoritmo de recocido simulado, ya tenía una solución que llegó a una aproximación bastante cercana de lo que estaba buscando. Entonces, solo para compartir otro enfoque (aunque relativamente crudo), aquí está:

(1) Ordené todos los tiempos de las pistas individuales de más corto a más largo.

#01 - 39:03 
#02 - 41:08 
#03 - 41:39 
#04 - 42:54 
#05 - 44:31 
#06 - 44:34 
#07 - 44:40 
#08 - 45:55 
#09 - 45:59 
#10 - 47:06 
#11 - 47:20 
#12 - 47:53 
#13 - 49:35 
#14 - 49:57 
#15 - 50:15 
#16 - 51:35 
#17 - 51:50 
#18 - 55:45
#19 - 58:10 
#20 - 58:11 
#21 - 59:48 
#22 - 59:58   
#23 - 60:00 
#24 - 61:08 

(2) Me agrupé en grupos de 4 de tal manera que las listas de reproducción resultantes tuvieran una distancia corta entre sí en función de sus posiciones en la lista ordenada, y esa agrupación sería: el elemento más corto + el elemento más largo + el centro dos elementos ... luego de la lista restante (aún ordenada), nuevamente el más corto + el más largo + los dos elementos intermedios ... y así sucesivamente hasta que se agrupen todos los elementos.

(3) Usando los conjuntos resultantes de 4 ahora, recorro en iteración todos los álbumes individuales en cada uno de los conjuntos, cambiando cada elemento por cada otro elemento de los otros conjuntos. Si, cuando se intercambian, la distancia de sus conjuntos de fuente se reduce, entonces realice el intercambio. Si no, omita el intercambio. Luego lo hice repetidamente hasta que ya no se puedan intercambiar dos álbumes para reducir la distancia entre sus conjuntos principales.

Para ilustrar el paso # 3 en el código:

Partitioner(){
    for(int i=0;i<total.length;i++)
        total[i] = 0;

    // get the total time for all sets of four albums
    for(int i=0;i<sets.length;i++){
        for(int j=0;j<sets[i].length;j++){
            total[i] = total[i] + sets[i][j];
        }
    }

    // this method will be called recursively until no more swaps can be done
    swapper();

    for(int i=0;i<sets.length;i++){
        for(int j=0;j<sets[i].length;j++){
            System.out.println(sets[i][j]);
        }
    }
}

void swapper(){
    int count = 0;  

    for(int i=0;i<sets.length;i++){ // loop through all the sets
        for(int j=0;j<sets[i].length;j++){ // loop through all the album in a set
            for(int k=0;k<sets.length;k++){ // for every album, loop through all the other sets for comparison
                if(k!=i){ // but of course, don''t compare it to its own set
                    for(int l=0;l<sets[k].length;l++){ // pair the album (sets[i][j]) with every album from the other sets
                        int parentA = total[i]; // store the total length from the parent set of album sets[i][j] 
                        int parentB = total[k]; // store the total length from the parent set of the album being compared
                        int origDist = Math.abs(parentA - parentB); // measure the original distance between those two sets
                        int newA = total[i] - sets[i][j] + sets[k][l]; //compute new length of "parentA" if the two albums were swapped
                        int newB = total[k] - sets[k][l] + sets[i][j]; //compute new length of "parentB" if the two albums were swapped
                        int newdist = Math.abs(newA - newB); //compute new distance if the two albums were swapped
                        if(newdist<origDist){ // if the new resulting distance is less than the original distance, commit the swap
                            int temp = sets[i][j];
                            sets[i][j] = sets[k][l];
                            sets[k][l] = temp;
                            total[i] = newA;
                            total[k] = newB;
                            count++;

                        }
                    }
                }
            }
        }
    }
    System.out.println(count);
    if (count > 0 ){
        swapper();
    }
}