2

我有一个问题：

我有一个 A 类和一个 B 类，可以通过编程检查它们的实例对象是否在不同数量上彼此相似或不同。例如，它们可能完全匹配，或者完全不同（即使类别不同，它们仍然可以表示相同的信息并且得分相同。）

现在，给定两个集合，一个是 A，一个是 B，将 As 和 B 配对的最佳方式是什么，以使它们最匹配，如果任一集合大于另一个集合或如果某些 As 或 B 完全不同而无法匹配？

我的第一次尝试是创建一个二维数组，其中每个单元格都是匹配的“分数”（0 = 完美，数字越大越差），并在每条路径中递归查找最低累积分数。这行得通，结果很完美，但速度非常慢。

关于更有效算法的任何想法？

如果您想知道，我的 A 类代表一个混音器输入通道，我的 B 代表相同的持久状态（称为场景）。我要解决的问题是如何将场景导入现有混音器，其中场景 (B) 可能与任何现有通道 (A) 略有不同甚至高度不同。如果我可以稍微修改任何一个以匹配，我不想只添加频道 (A)。例如，我可以在 A 中添加一个效果插入，以便与 B 完美匹配，避免添加另一个 A。

麦克风

4

3 回答 3

2

这听起来像是一个二分匹配问题，并且可能可以通过使用相似性度量来加权边缘，使用标准的最大流/最小切割解决方案来解决。

这可能有帮助

于 2009-03-04T04:28:29.827 回答
0

我会启发式地这样做。

首先收集一组完全匹配。

然后有一个阈值，并收集比该阈值更好的匹配项。

扩大阈值并重复，直到用尽一组或两组。

现在你有一场试赛，这可能不是最好的。

运行大量模拟退火循环，在其中随机排列匹配链接，并根据取决于它们各自成本的概率保留或不保留它们。

这使您可以探索匹配空间，如果附近有更好的匹配，它应该会找到它们。

于 2009-03-10T12:04:36.047 回答
0

我没有算法，只有一般建议。您可以尝试随机抽样的可能性，直到您花费了您愿意花费的时间并采取了一路上找到的最佳选择。这种方法通常不会找到最佳解决方案，但通常很容易编程。并且根据问题，它可能足够接近最佳值。您可以进行实验，看看随着随机样本数量的增加，质量如何提高。如果幸运的话，少量样本可能就足够了。

于 2009-03-04T11:18:04.117 回答