2
$\begingroup$

I'm tempted to phrase this question notationally, but I may be jumping the gun on the exact problem definition as well. So let me start with the real-world scenario and work forward from there.

You're given a list of media items--songs, let's say--to play. You must play every song once, with no repetitions, but you get to pick the play sequence. The goal of sequencing is to maximize variety. For example, it would be undesirable to play two songs by the same artist back-to-back.

My initial thought was to treat items analogously to magnets that repel each other according to their degree of similarity. (Details below.) A simple brute-force implementation shows that this approach works well. However, it's of course computationally intractable. Not only are there $n!$ permutations to evaluate, but calculating the cost of a given permutation is $O(n^2)$, because every song exerts force on every other song.

Formally: Given a set of $n$ items $\{T_1, T_2, ... T_n\}$, find the permutation $P$ $\{T_{p1}, T_{p2}, ... T_{pn} \}$ that minimizes cost function $C(P)$:

$$ C(P) = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac{S(T_{pi}, T_{pj})D(T_{pi})D(T_{pj})}{R(T_{pi}, T_{pj})^2} $$

where $S()$ is a measure of similarity between two items (take this as given), $D()$ is the duration (think "mass") of a given item, and $R()$ is the time-distance between item centerpoints.

Scheduling problems of this type often seem to have dynamic programming solutions, but those solutions usually rely on the incremental cost of the sequence-ending item being dependent only on the item's completion time. Here, the cost of the final item depends on the positioning of all other items in the sequence, which would seem to rule out that approach.

Possible ameliorating factors: A) Total cost is a monotonically increasing value as items are added to a sequence, so some unpromising starts can be pruned from the search if they already exceed the best-so-far result. B) For a given sequence prefix, interactions internal to the prefix need be calculated only once. C) True optimality is not necessary, although it would be helpful to have some guarantee of reasonability.

Questions: The usual. :-) Is this a known problem that has a literature behind it? What would the standard name be? Does any particular search method stick out as being especially appropriate? In particular, would simulated annealing be a good approach? Is there a better formulation of the problem that would have better tractability?

Thanks for your comments!

$\endgroup$
  • $\begingroup$ At a cursory whiff, this smells like TSP... $\endgroup$ – Nicholas Mancuso Jan 12 '15 at 3:07
  • $\begingroup$ Thanks. I can see the analogy/mapping, but it would have to be some sort of dynamic TSP variant, wouldn't it? The cost of a particular edge isn't constant; it depends on the prefix path. Is this a standard kind of TSP-ish problem? $\endgroup$ – GSnyder Jan 12 '15 at 3:12
  • $\begingroup$ A very interesting approach would be to run a physical simulation, with the songs exerting force on each other as you describe. Such a simulation would eventually settle in to a (local) minimum. You could apply some variant of simulated annealing, where the temperature is something that perturbs the movement of the songs (the songs get random impulses that scale with temperature). Another (more traditional) approach would be to only store the last few songs played, and ignore any songs played earlier since they would have limited effect. $\endgroup$ – Tom van der Zanden Jan 12 '15 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.