注意:我计划使用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秒的速度运行将是完美的……但是由于各个专辑的长度可能不允许如此精确的划分，所以我的问题是最精确的划分。
注意:我实际上可以手动执行此操作，并且获得足够接近的近似值就足够了，但是我仍然对如何通过程序完成它很感兴趣。
谢谢!
最佳答案
我建议您使用模拟退火算法
这是此算法派生的一个不错的解决方案:
[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首曲目，以便所有专辑的时长大致相同。
首先让我们考虑-我们需要优化哪个属性？
从我的 Angular 来看，最合适的表述是:最小化所有专辑的standard deviation。 (但是，如果需要-您可以自由包含任何其他更复杂的属性)。
让我们将优化属性的值命名为 energy 。
算法的主要思想
我们系统的每个状态都具有一定的能量值。通过对系统执行一些操作，我们可以更改其状态(例如，在不同专辑之间交换曲目)。
另外，我们还有一些抽象属性 temperature 。
当系统处于高温下时，即使新状态具有更高的能量值，也可以自由地将其状态更改为另一状态。
但是，当温度较低时，系统倾向于将其状态大部分更改为具有较低能量值的新状态。
通过物理类比，可以按照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);
}
}
关于algorithm - 如何将24张音乐专辑分成6个播放列表，以使播放时间/长度尽可能均匀地分配？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23692081/