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 回答