algorithm - 如何将 24 张音乐专辑分成 6 个播放列表，使播放时间/长度尽可能均匀分布？

Question

注意:我计划使用 Java 来实现它，但欢迎和赞赏任何对逻辑中所需步骤的简单英语解释。

我正在尝试想出一种方法，将一组 24 张音乐专辑/唱片分成 6 个播放列表，以便所有 6 个播放列表的长度/运行时间尽可能接近。

我最初想也许我可以找到问题的所有可能排列，然后制定出一个逻辑来分析哪个是最好的划分。昨天我什至创建了一个线程来寻求帮助(I have 24 items that I need to separate into 6 sets of 4. What algorithm can I use to find all possible combinations?)。然而，当我接近找到解决方案时，我意识到仅仅找到问题的所有排列将需要非常长的运行时间，因此这种方法似乎不切实际。

所以我想知道，有没有更快的方法来解决这样的问题？

鉴于这些是相关专辑的运行时间(MM:SS 格式)，我找到将专辑分成 6 个播放列表的最快方法是 4，这样每个播放列表的长度是尽可能靠近彼此？

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 

我算了算，考虑到所有专辑的总时间，如果有 6 个播放列表，播放时间为 200 分 49 秒，那将是完美的……但由于单个专辑的长度可能不允许那么精确除法，我的问题是什么是最准确的除法。

注意:我实际上可以手动执行此操作并获得足够接近的近似值，但我仍然对如何通过程序完成它非常感兴趣。

谢谢!

Answer 1

我建议你使用模拟退火算法

这是由该算法得出的一个很好的解决方案:

[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

作为Steven Skiena在他的书(“算法设计手册”)中指出，使用 Simulated annealing 非常有帮助用于在现实生活中的组合问题中寻找可接受的解决方案的元启发式方法。

因此，正如您提到的，您需要在 6 张专辑中的每张专辑中放置 4 首轨道，这样所有专辑的时长都大致相同。

首先让我们考虑一下 - 我们需要优化哪个属性？

从我的角度来看 - 最合适的公式是:最小化 standard deviation所有专辑的持续时间。(但是，如果需要 - 您可以自由地包含任何其他更复杂的属性)。

让我们将优化属性的值命名为能量。

算法主要思想

我们系统的每个状态都以某种能量值为特征。通过对系统执行一些操作，我们可以更改其状态(例如，在不同专辑之间交换轨道)。

此外，我们还有一些称为温度的抽象属性。

当系统处于高温状态时，它可以自由地将其状态更改为另一种状态，即使新状态具有更高的能量值。

但是当温度很低时，系统往往会将其状态主要更改为具有较低能量值的新状态。

通过物理类比，将系统的当前状态改变为具有更高能量值的状态的概率可以用与Boltzmann distribution相同的方式来限制。定义。

这是从上面推导出解决方案时持续时间的标准差如何变化的图示

这是算法的完整 Java 实现，它给出了上面的解决方案

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);
    }
}