Which algorithm would be suitable here? Traversing a series of interconnected nodes, covering them all with minimal repetition

I'm helping out a friend, writing him a program. He is re-recording the soundtrack to the old Lucasarts game Tie Fighter. The game used the iMuse system - each 'track' was made up of a number of small audio cues. The game combined these to make a dynamic soundtrack that changed as the situation did.

For each 'track' there is a set of rules that govern which cue to move onto next. There is a random element to this, eg:

SUCC CUES

SUCC-01 moves to SUCC-02

SUCC-02 moves to SUCC-03 or SUCC-04

SUCC-03 moves to SUCC-01 or SUCC-04

SUCC-04 moves to SUCC-05

SUCC-05 moves to SUCC-01 or SUCC-06 or开发者_如何学Python SUCC-08

SUCC-06 moves to SUCC-04 or SUCC-07

SUCC-07 moves to SUCC-01 or SUCC-02 or SUCC-04 or SUCC-08

SUCC-08 moves to SUCC-02 or SUCC-06

SUCC-IN moves to SUCC-01

There are many other tracks like this, with many more cues. Essentially each track is a mesh of interconnected nodes. He wants the program to parse the cues and create playlists for each track that satisfy 2 criteria:

• All the cues in a track are used
• There is minimal repetition of cues

I have minimal experience with algorithms, so I'm not sure which algorithm would be appropriate for this problem. From reading around my guess would be some sort of travelling-salesman type.

Additionally, if anyone could point me towards code samples that might help (bearing in mind my general ignorance of this kind of problem), it would be very much appreciated.

I'd suggest you try a simple brute-force heuristic-like solution based on a breath-first search:

On each level of the search "priorizie" cues which are not part of the current solution. Count the unique number of cues in your solution (this might be tricky, but it is not that hard: just remember the chain of cues you came from (from the beginning to the current cue) and you have all information you need) and terminate as soon as you find a solution that uses all cues (it should be quiet minimal then).

This "algorithm" is far from being perfect or performant, but unless you have a track built up from several thousands of cues, it should be no problem.

Note that this "algorithm" will be caught in an infinite loop if your track list contains cues which are not reachable from your start cue. Use a counter to terminate, e.g. if your search result has more than ten times the number of cues, or something like that.

I have no delphi code, but it should not be hard to find one for breath-first search.