Thursday, May 24, 2007

Playlist Creation as a TSP

A playlist (or mixtape) can be considered an ordering over a set of songs. Defining this ordering can be a fairly difficult process, and if we frame it as TSP solving, it's clear why.

Every song has a number of features (tempo, key, genre, theme, etc.), and the difference between songs is some distance metric over these feature vectors. Each song is a node, and there is an edge between every node the length of the difference. As with a traditional TSP, the solution is the shortest path that visits every node.

This alone is a difficult problem, but it's compounded by the possibility of a context dependent metric, or even a total time constraint less than the sum of all the song lengths (with the ability to ignore expensive songs).

No comments: