如何将24个音乐专辑分成6个播放列表,以使运行时间/长度尽可能均匀分布？
hei*_*man 20 language-agnostic algorithm
注意:我计划使用Java实现这一点,但欢迎并赞赏逻辑中所需步骤的任何简单英语解释.
我试图想出一种方法将一组24个音乐专辑/记录分成6个播放列表,这样所有6个播放列表的长度/运行时间尽可能彼此接近.
我最初认为也许我可以找到问题的所有可能的排列,然后找出一个逻辑来分析哪个是最好的除法.我昨天创建了一个线程来寻求帮助(我有24个项目需要分成6组4.我可以使用什么算法来查找所有可能的组合？).然而,当我接近寻找解决方案时,我意识到只是找到问题的所有排列将花费极长的时间来运行,因此这种方法似乎不切实际.
所以我想知道,有没有更快的方法来解决这个问题？
鉴于这些是相关专辑的运行时间(以MM:SS格式),我找到将专辑分成4个播放列表的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秒运行将是完美的...但由于个别专辑长度可能不允许精确的分区,什么将是最准确的分工是我的问题.
注意:我实际上可以手动执行此操作并获得足够接近的足够近似值,但我仍然对如何通过程序完成它感兴趣.
谢谢!
ste*_*emm 22
我建议你使用模拟退火算法
以下是此算法派生的一个很好的解决方案:
[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在他的书("算法设计手册")中指出的那样,使用模拟退火元启发式在现实生活中的组合问题中寻找可接受的解决方案是非常有帮助的.
因此,正如您所提到的,您需要在6张专辑中分别放置4首曲目,以便所有专辑的持续时间大致相同.
首先让我们考虑一下 - 我们需要优化哪个属性？
从我的观点来看 - 最合适的配方是:尽量减少所有专辑持续时间的标准偏差.(但是,如果需要 - 您可以自由地包含任何其他更复杂的属性).
让我们将优化属性的值命名为energy.
算法的主要思想
我们系统的每个状态都具有一定的能量值.通过在系统上执行某些操作,我们可以更改其状态(例如,在不同的专辑之间交换曲目).
此外,我们有一些称为温度的抽象属性.
当系统处于高温时,即使新状态具有较高的能量值,也可以自由地将其状态改变为另一状态.
但是当温度很小时,系统倾向于将其状态主要改变为具有较低能量值的新状态.
通过物理类比,可以以与玻尔兹曼分布定义的相同方式限制将系统的当前状态改变为具有较高能量值的状态的概率.
以下是从上方推导出解决方案时,持续时间标准偏差如何变化的说明
这是一个完整的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);
}
}
ham*_*mar 13
如果您将每个专辑视为作业并将每个播放列表视为处理器,并且找到最佳解决方案是NP难度,则这与多处理器调度等效*.
然而,有一些有效的算法可以提供合适的但不一定是最佳的结果.例如,按长度排序相册并重复将最长的相册添加到最短的播放列表中.
如果我们将相册从1到24从最短到最长编号,则此算法给出以下划分.
{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)
*如果我们认为"均匀分布"意味着最长播放列表的长度最小化.
使用比蛮力更智能的搜索算法,我们不必经历所有1e12的可能性.首先,我们转换输入,枚举所有四个集合,并根据它们与目标时间的接近程度对它们进行排序.
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))
现在来搜索.我们使用部分解决方案保留优先级队列,按目标时间的最小可能最大偏差排序.优先级队列让我们首先探索最有前途的部分解决方案.
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
在几秒钟内,此代码会吐出以下最佳答案.(我们很幸运,因为这段代码正在进行略微修改的目标,即尽量减少与目标时间的最大偏差;对于下面更复杂的程序,我们可以最小化最小值和最大值之间的差异,结果是相同的分组.)
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
优化最大减去最小目标的程序如下.与上述程序相比,它不会在第一个解决方案之后停止,而是等到我们开始考虑与目标的偏差大于我们迄今为止找到的解决方案的最小最大减去min的集合.然后它输出最好的.
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))