将一个列表与另一个列表匹配，误差最小
我有两个列表，A 和 B。A 最多有约 1000 个元素，B 最多有约 100 个元素。我想将 B 的每个元素与 A 的一个元素相匹配，以使两对的绝对差之和最小化。
即我想选择|B|与 A 不同的索引，并将它们分配给 B 的索引，从而最小化以下总和： sum(abs(A[j] - B[i]) for i in |B|, j = index_mapping(i))
我的第一个方法是：
- 对于 B 的每个元素，计算 |B| A 的最接近的元素。
- 以贪婪的方式选择对（即最小误差优先）
通过一些简单的示例，很明显我的方法不是最好的。它应该可以很好地满足我的目的，但我想知道是否有人可以提出更好的方法？
I have two lists, A and B. A will be at most ~1000 elements, and B will be at most ~100 elements. I want to match every element of B to an element of A, such that the sum of the absolute differences of the pairs is minimized.
i.e. I want to choose |B| distinct indexes from A, and assign them to the indexes of B, such that the following sum is minimized: sum(abs(A[j] - B[i]) for i in |B|, j = index_mapping(i))
My first approach is:
- For each element of B, to compute the |B| closest elements of A.
- Choose the pairs in a greedy fashion (i.e. minimum error first)
Playing with some simple examples, it's clear that my approach is not the best. It should work fine for my purpose, but I was wondering if anyone could suggest a better approach?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我最终对两个列表进行了排序，并迭代它们以进行匹配。这对于我正在做的事情来说已经足够好了。
I ended up sorting both lists, and iterating through them to match. This worked well enough for what I was doing.
嗯...临时想到的是，如果你可以对 A 和 B 进行排序，那么一旦你找到 A[j] 到 B[i] 的第一个映射，那么对于 B[i+1]，您可以使用 A[j] 而不是 A[0] 开始测试。
例如：
您从 B[0] = 31 开始，逐步执行 A，直到找到最接近的匹配项 A[1]。由于列表是有序的，您知道 B[1] 不会匹配小于 A[1] 的任何内容，因此您可以从那里开始比较。事实证明，A[1] 仍然是最接近的匹配。在 B[2] 处，最接近的匹配是 A[4]，因此您知道 B[3] 不会匹配低于 A[4] 的任何内容，无需通过 A[3] 搜索 A[0]。
Hmm... Offhand, the first thought that comes to mind is that if you can sort A and B, then once you find the first mapping of A[j] to B[i], then for B[i+1], you could start your testing with A[j] instead of A[0].
For example:
You start with B[0] = 31 and step through A until you find the closest match, A[1]. Since the lists are ordered, you know that B[1] won't match anything less than A[1], so you can start comparing from there. Turns out, A[1] is still the closest match. At B[2], the closest match is A[4], so you know that B[3] won't match anything lower than A[4], there's no need to search A[0] through A[3].