Ответ 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
Как Стивен Скиена указал в своей книге ( "Руководство по разработке алгоритмов" ), что очень полезно использовать Имитированный отжиг метаэвристический для нахождения приемлемых решений в комбинаторных задачах реальной жизни.
Итак, как вы уже упоминали, вам нужно поставить 4 трека в каждом из 6 альбомов, чтобы все альбомы имели примерно такую же продолжительность.
Во-первых, рассмотрим - какое свойство нам нужно оптимизировать?
С моей точки зрения, наиболее подходящей формулировкой было бы: минимизировать стандартное отклонение продолжительности всех альбомов. (Но при необходимости - вы можете включать любые другие, более сложные свойства).
Назовите значение оптимизированного свойства как Энергия.
Основная идея алгоритма
Каждое состояние нашей системы характеризуется некоторой величиной энергии. Выполняя некоторые действия над системой, мы можем изменить ее состояние (например, свопинг дорожек между разными альбомами).
Кроме того, у нас есть некоторое абстрактное свойство, называемое температура.
Когда система находится под высокой температурой, она может изменять свое состояние в другое состояние, даже если новое состояние имеет более высокое значение энергии.
Но когда температура мала, система имеет тенденцию менять свое состояние в основном на новые состояния с более низкими значениями энергии.
По физической аналогии вероятность изменения текущего состояния системы в состоянии с более высоким значением энергии может быть ограничена так же, как Boltzmann распространение.
Вот иллюстрация того, как стандартное отклонение длительностей изменилось при выводе решения сверху
Вот полная реализация алгоритма 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);
}
}