给定一个 MxN (4x4) 维度的矩阵 A,如何找到每个 2x2 子矩阵的次优最小值?
A = array([[ 32673. , 15108.2 , 26767.2 , 9420. ],
[ 32944.2 , 14604.01 , 26757.01 , 9127.2 ],
[ 26551.2 , 9257.01 , 26595.01 , 9309.2 ],
[ 26624. , 8935.2 , 26673.2 , 8982. ]])
一组子矩阵的次优最小值,是该子矩阵中与其他最小值的局部位置不冲突的最小值:
示例算法:
1. Find the minimum in A: 8935.2 global coords[3,1], local coords [1,1]
2. No other matrix has been evaluated so no conflict yet.
3. Find the next submatrix min: 8982. gc [3,3], lc [1,1]
4. Conflict exists, find next min in same submatrix: 9309.2 gc [2,3], lc [0,1]
5. Find next submatrix min: 9420 gc [0,3] lc[0,1]
6. Conflict exists, find next min: 26757.01 gc [1,2] lc [1,0]
7. Find next submatrix min: 14604 -- conflict with lc[1,1]
8. Find next submatrix min: 15108.2 -- conflict with lc [0,1]
9. Find next submatrix min: 32673. gc [0,0], lc [0,0]
我想尝试的一种方法是遵循上面的算法,但我没有再次详尽地搜索每个子矩阵,而是用“高”值 (>> max(A)) 全局更新每个子矩阵的局部位置,这是每次成功找到最小值时递增。
预期的输出将是一个列表:
[((0, 0), (0, 0), 32673), ((0, 1), (1, 0), 26757.01), ((1, 0), (1, 1), 8935.2), ((1, 1), (0, 1), 9309.2)]
形式为 [((t1), (t2), value) ... ],其中 t1 是 A 中子矩阵的坐标,t2 是子矩阵中所选最小值的坐标。
编辑:子矩阵定义为 ZxZ,其中 MxN 模 ZxZ == 0,并且从 (0,0) 开始不重叠,并平铺以匹配 MxN 的维度。
编辑:下面是我构建的解决方案,但速度很慢。我怀疑如果我在每次迭代中从矩阵中删除子矩阵,那么性能可能会提高,但我不确定该怎么做。
def get_mins(self, result):
# result is the 2d array
dim = 2 # 2x2 submatrix
mins = []
count = 0
while count < dim**2:
a, b = result.shape
M4D = result.reshape(a//dim, dim, b//dim, dim)
lidx = M4D.transpose(0, 2, 1, 3).reshape(-1, b//dim, dim**2).argmin(-1)
r, c = numpy.unravel_index(lidx, [dim, dim])
yy = M4D.min(axis=(1, 3))
ww = numpy.dstack((r, c))
super_min = numpy.unravel_index(numpy.argmin(yy), (dim, dim))
rows = super_min[0]
cols = super_min[1]
# ww[rows,cols] g_ves us 2x2 position
offset_r, offset_c = ww[rows, cols]
# super_min gives us submatrix position
mins.append((tuple(super_min), (offset_r, offset_c), yy.min()))
if dim > 1:
# update all other positions with inf >> max(result)
result[numpy.ix_([offset_r + (d * dim) for d in range(dim)], [offset_c + (d * dim) for d in range(dim)])] = numpy.inf
# update the submatrix to all == numpy.inf
result[rows*dim:((rows*dim)+dim), cols*dim:((cols*dim)+dim)] = numpy.inf
count += 1
return mins
最佳答案
考虑到在选择全局最小值时迭代之间的依赖性,这是一种单循环方法 -
def unq_localmin(A, dim):
m, n = A.shape
M4D = A.reshape(m//dim, dim, n//dim, dim)
M2Dr = M4D.swapaxes(1,2).reshape(-1,dim**2)
a = M2Dr.copy()
N = M2Dr.shape[0]
R = np.empty(N,dtype=int)
C = np.empty(N,dtype=int)
shp = M2Dr.shape
for i in range(N):
r,c = np.unravel_index(np.argmin(a),shp)
a[r] = np.inf
a[:,c] = np.inf
R[i], C[i] = r, c
out = M2Dr[R,C]
idr = np.column_stack(np.unravel_index(R,(dim,dim)))
idc = np.column_stack(np.unravel_index(C,(dim,dim)))
return zip(map(tuple,idr),map(tuple,idc),out)
让我们使用更大的随机 9x9
数组和 3x3
子矩阵/子数组来验证结果,以测试针对 OP 实现的多样性 get_mins
-
In [66]: A # Input data array
Out[66]:
array([[ 927., 852., 18., 949., 933., 558., 519., 118., 82.],
[ 939., 782., 178., 987., 534., 981., 879., 895., 407.],
[ 968., 187., 539., 986., 506., 499., 529., 978., 567.],
[ 767., 272., 881., 858., 621., 301., 675., 151., 670.],
[ 874., 221., 72., 210., 273., 823., 784., 289., 425.],
[ 621., 510., 303., 935., 88., 970., 278., 125., 669.],
[ 702., 722., 620., 51., 845., 414., 154., 154., 635.],
[ 600., 928., 540., 462., 772., 487., 196., 499., 208.],
[ 654., 335., 258., 297., 649., 712., 292., 767., 819.]])
In [67]: unq_localmin(A, dim = 3) # Using proposed approach
Out[67]:
[((0, 0), (0, 2), 18.0),
((2, 1), (0, 0), 51.0),
((1, 0), (1, 2), 72.0),
((1, 1), (2, 1), 88.0),
((0, 2), (0, 1), 118.0),
((2, 2), (1, 0), 196.0),
((2, 0), (2, 2), 258.0),
((1, 2), (2, 0), 278.0),
((0, 1), (1, 1), 534.0)]
In [68]: out = np.empty((9,9))
In [69]: get_mins(out,A) # Using OP's soln with dim = 3 edited
Out[69]:
[((0, 0), (0, 2), 18.0),
((2, 1), (0, 0), 51.0),
((1, 0), (1, 2), 72.0),
((1, 1), (2, 1), 88.0),
((0, 2), (0, 1), 118.0),
((2, 2), (1, 0), 196.0),
((2, 0), (2, 2), 258.0),
((1, 2), (2, 0), 278.0),
((0, 1), (1, 1), 534.0)]
简化
上面的解决方案为我们提供了可用于构造索引元组的行和列索引,如使用 get_mins
打印的那样。如果您不需要这些,我们可以稍微简化提议的方法,就像这样 -
def unq_localmin_v2(A, dim):
m, n = A.shape
M4D = A.reshape(m//dim, dim, n//dim, dim)
M2Dr = M4D.swapaxes(1,2).reshape(-1,dim**2)
N = M2Dr.shape[0]
out = np.empty(N)
shp = M2Dr.shape
for i in range(N):
r,c = np.unravel_index(np.argmin(M2Dr),shp)
out[i] = M2Dr[r,c]
M2Dr[r] = np.inf
M2Dr[:,c] = np.inf
return out
运行时测试 -
In [52]: A = np.random.randint(11,999,(9,9)).astype(float)
In [53]: %timeit unq_localmin_v2(A, dim=3)
10000 loops, best of 3: 93.1 µs per loop
In [54]: out = np.empty((9,9))
In [55]: %timeit get_mins(out,A)
1000 loops, best of 3: 907 µs per loop
关于python - Numpy:如何找到矩阵 A 中子矩阵的唯一局部最小值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40653937/