2

我想创建一个程序,为我的乐队创建随机设置列表;但是,我不希望这些集合是完全随机的。有的歌曲最好作为开始,有的歌曲最好作为结尾。有些歌曲需要更换乐器,所以我想限制开关的数量。从一首快歌到一首慢歌通常不是一个好主意,但最好是从慢到快。我们不能连续玩 180 分钟,所以我想把演出分成三组,每组 50 分钟。

我可以将歌曲的关系想象为一个完全连接的有向图,每首歌曲作为一个节点,它们之间的连接是一个分数,表示一首歌曲在前一首歌曲之后的好坏程度,这适用于旅行推销员。但是,我不想要最短路径,我想要 50 分钟集合内的最佳歌曲过渡(每首歌曲都有一个时长,并且集合列表中所有歌曲的总时长不得超过 50 分钟),这听起来更像一个背包问题。

有人可以帮我吗?我应该研究什么算法?

编辑(更多信息):

我已经想到了一个函数来对两首歌曲 f(s,t) 之间的过渡进行评分,它产生一个介于 0 和 100 之间的整数值,其中 100 是更好的过渡。我还考虑为节目的开始(“START”)、节目的结束(“END”)和中间的中断(“BREAK 1”、“BREAK 2”等)创建节点。前面提到的函数可以对从“START”到另一首歌曲或歌曲到“BREAK 1”的过渡进行评分,以表示打开一组或​​关闭一组给定的歌曲。

4

1 回答 1

3

TSP 可能不是这个问题的一个很好的描述。原因是您实际上并没有在寻找最佳套装列表,因为您只是在寻找一些好的套装列表。

话虽如此,您的问题让我想起了很多使用粒子过滤器来尝试定位某物的位置。

稍微调整一下该方法会得到如下结果:

  1. 使用加权概率随机生成 100 个集合列表。手工挑选一些可能​​会很有用。
  2. 计算每个集合列表的分数,然后将其用作权重,随机选择 10 个集合列表。
  3. 对于这些集合列表中的每一个,使用加权概率随机生成 10 首歌曲。例如,您可以使用歌曲的分数作为权重来确定是否应该更改它(较低的相对分数意味着歌曲更有可能被更改)。
  4. 根据需要重复步骤二和三。
  5. 选择当前最好的,或随机选择当前 100 个中的一个。

我使用了 100 个示例,但您可以使用几乎任何可能低于一百万左右的样本量,除非您有很多时间让它运行。请注意您选择了多少 VS 从选定的那些中生成了多少。选择的数字乘以生成的数字应该等于您最初开始使用的数字。

编辑:

不确定您是否熟悉加权概率,所以我可能应该总结一下,因为它对算法相当重要。假设您有歌曲 AC,权重分别为 1-3。处理加权概率的一种方法不是从 [A,B,C](未加权)中随机选择 100 个元素,而是从 [A,B,B,C,C,C] 中随机选择 100 个元素。由于 C 的权重是 A 的 3 倍,因此它被选中的可能性是 3 倍。

理想情况下,如果您使用该方法,您应该将分数保持为整数,并且它们应该相对较低(以便从中选择元素的列表的最大长度不会太高)。如果您不介意精度损失(在这种情况下可能没问题),您还可以标准化概率并使用它创建一个列表,该列表在其大小方面将更加可预测。这可以通过将权重相加,然后将每个权重除以总和,然后将所有结果乘以一个数字来完成。因此,例如,如果您的权重为 [1000,10000,100000] 而不是 1-3,则将每个权重除以总和 (111000) 得出大约 [0.009,0.090,0.901],乘以 100(给出列表大小约 100) 并四舍五入到最接近的整数给出: [1,9, 90] 因此,您从中随机选择元素的列表应恰好包含 1 个 A、9 个 B 和 90 个 C。有可能只选择 A 进行重新采样(步骤 3),但这是不太可能的,尽管如果发生它会出现问题。在这种情况下,您可能必须重新运行该程序。有一些方法可以解决这个问题,但最终会失去算法的很多随机性。

哦,再加上 3) 更改歌曲时,计算可以替换该歌曲的每首歌曲的分数。删除所有权重较低的歌曲或可能略低于其权重的一部分*,然后使用分数作为权重并随机选择将替换它的新歌曲(如果分数相当高,这实际上可能是同一首歌曲) .

*这是可选的,但如果您认为它可能有用,那么实施它可能不是一个坏主意,因为您可以将其设置为低于 0.0 * 重量。

于 2013-01-04T05:09:54.580 回答