将浮点数列表匹配到最接近的整数，而无需重复

debugcn 发表于 Dev

马克·斯帕克

我有一种算法正在尝试实现，而我正努力寻找一种实现它的好方法。目标是获取一个浮点数列表，并与整数列表进行一对一映射，这样就不会有两个浮点数被映射到同一整数，并且该映射具有最小的可能误差（无论是总误差还是误差或均方误差）。

例如，假设我有数字[2.1, 2.3, 2.4, 7, 7.5, 8.9, 9.3]。我希望它返回如下内容：

{
    2.1: 1,
    2.3: 2, 
    2.4: 3,
    7: 7,
    7.5: 8,
    8.9: 9,
    9.3: 10
}

请注意，聚集在2周围的数字必须分散为1、2和3。

可能要提一提，我的动机是在音乐上实用的：将一系列微音高的音调（注意“裂纹之间”）映射到钢琴的琴键。因此，实际上，我只需要一个“足够好”的解决方案，尽管真正的最佳解决方案会更令人兴奋！

另外，我正在使用Python工作，但是当然，这里的真正问题不是特定于语言的。

萨沙

也许不是最优雅，最有效的代码，但是：

这是多项式复杂性
它提供了全局最优

基本思路：

计算一些最坏情况的候选范围（我们一定不要忘记任何可能改进的候选范围）
- 我没有投入太多->一个“ hack”
计算距离矩阵
解决矩形线性分配问题

码：

import math
import numpy as np
from scipy.optimize import linear_sum_assignment
from scipy.spatial.distance import cdist

SQUARED_PENALTY = True

data = np.array([2.1, 2.3, 2.4, 7, 7.5, 8.9, 9.3])

# hacky safety-net -> which candidates to look at
min_ = math.floor(data.min())
max_ = math.ceil(data.max())
gap = max_ - min_

cands = np.arange(min_ - gap, max_ + gap)

cost_matrix = cdist(data[:, np.newaxis], cands[:, np.newaxis])

if SQUARED_PENALTY:
  cost_matrix = np.square(cost_matrix)

row_ind, col_ind = linear_sum_assignment(cost_matrix)

solution = cands[col_ind]

print(solution)
print('cost: ', np.round(cost_matrix[row_ind, col_ind].sum(), 3))

产出：l1-成本