将测量值与已知项匹配的算法

Question

我有一组测量项目 (m1, m2 m3...) 和一组真实项目 (r1, r2, r3...)。真实项目集大于测量值(并非所有项目都被测量)，我正在寻找一种算法来将测量项目与最接近的真实项目配对。我有一个函数 error(meas, real) 可以计算测量项目与真实项目的接近程度(返回单个 float ，越小越接近)。

我已经实现了一个贪婪算法，它会得到误差最小的对，也就是说，我计算每个可能对的误差并得到误差最小的对，将它们从它们的集合中移除并重复直到我匹配每一个测量项目。

这个方法有效，但我正在寻找一种算法，它可以最小化每对的所有 error() 的总和。

我想这是一个常见问题，可能有多种选择可以解决这个问题。如果是这样的话，如果您能提供链接或名称在互联网上查找，那就太好了。

Answer 1

在我看来这个问题类似于空间划分问题，给定平面上的一组点(通常你可以解决 k 维空间的问题)你必须找到一个闭合点到查询点。 wiki

编辑

我可以将此问题与 minflow 联系起来问题:

The minimum-cost flow problem is to find the cheapest possible way of sending a certain amount of flow through a flow network

因此构造一个具有两组不同节点的图(删除了一些不必要的部分)。 M 中的每个节点都连接到 R 中的每个节点。顶点的权重由 error 函数计算。

任务是将 d 值从 s 传输到 t 并保持传输值尽可能低。您必须修改原始问题以满足您的需要。例如，从 s 到 M 的每个顶点都应该在传输 d 时使用，e.t.c

我不确定这是否是正确的方法，但值得考虑