哪种算法适合这里？遍历一系列互连的节点，以最少的重复覆盖所有节点
我正在帮助一个朋友，给他写一个程序。他正在重新录制旧 Lucasarts 游戏《Tie Fighter》的配乐。该游戏使用了 iMuse 系统 - 每个“轨道”都由许多小的音频提示组成。游戏将这些结合起来，制作出随着情况的变化而变化的动态配乐。
对于每个“轨道”，都有一组规则来控制移动到下一个提示。这有一个随机元素，例如：
SUCC CUES
SUCC-01 移至 SUCC-02
SUCC-02 移至 SUCC-03 或 SUCC-04
SUCC-03 移至 SUCC-01 或 SUCC-04
SUCC-04 移至 SUCC-05
SUCC-05 移至 SUCC-01 或 SUCC-06 或 SUCC-08
SUCC-06 移至 SUCC-04 或 SUCC-07
SUCC-07 移至 SUCC-01 或 SUCC-02 或 SUCC-04 或 SUCC-08
SUCC-08 移至 SUCC-02 或 SUCC-06
SUCC-IN 移至 SUCC-01
还有许多其他类似的曲目，有更多的提示。本质上，每个轨道都是互连节点的网格。他希望程序解析提示并为每个轨道创建满足 2 个条件的播放列表：
- 使用轨道中的所有提示 提示
- 的重复最少
我对算法的经验很少，所以我不确定会使用哪种算法适合这个问题。通过阅读周围的内容，我猜测这可能是某种旅行推销员类型。
此外，如果有人可以向我指出可能有帮助的代码示例（考虑到我对此类问题的普遍无知），我将非常感激。
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 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我建议您尝试一个基于呼吸优先搜索的简单的类似暴力启发式的解决方案：
在搜索的每个级别上“优先”提示不属于当前解决方案的一部分。计算解决方案中线索的唯一数量（这可能很棘手，但并不难：只需记住您来自的线索链（从开始到当前线索），并且您拥有所需的所有信息）并终止一旦您找到使用所有提示的解决方案（那么它应该是安静的最小）。
这个“算法”远非完美或高性能，但除非你有一个由数千个线索组成的曲目，否则应该没有问题。
请注意，如果您的曲目列表包含无法从开始提示访问的提示，则此“算法”将陷入无限循环。使用计数器终止，例如，如果您的搜索结果的提示数量超过十倍，或类似的情况。
我没有delphi代码，但是找到一个用于快速搜索的代码应该不难。
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.