根据具有多个结果的矩阵构建地图 [英] build a map out of a matrix with multiple outcomes
问题描述
我有一个未知的n x m尺寸的输入矩阵，其中填充了1s和0s
I have an input matrix that is of unknown n x m dimensions that is populated by 1s and 0s
例如5x4矩阵:
A = array(
[[1, 0, 0, 0],
[1, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 1, 1]])
目标
我需要在尽可能多的列和行之间创建一个1:1的映射，其中该位置的元素为1.
Goal
I need to create a 1 : 1 map between as many columns and rows as possible, where the element at that location is 1.
1:1映射的意思是每一列和每一行最多只能使用一次.
What I mean by a 1 : 1 map is that each column and row can be used once at most.
理想的解决方案具有尽可能多的映射，即.使用最多的行和列.它还应避免详尽的组合或在较大的矩阵上无法很好地缩放的操作(实际上，最大尺寸应为100x100，但没有声明的限制，因此它们可能会更高)
the ideal solution has the most mappings possible ie. the most rows and columns used. It should also avoid exhaustive combinations or operations that do not scale well with larger matrices (practically, maximum dimensions should be 100x100, but there is no declared limit so they could go higher)
以下是上述可能的结果
array([[ 1., 0., 0., 0.],
[ 0., 0., 0., 0.],
[ 0., 0., 1., 0.],
[ 0., 1., 0., 0.],
[ 0., 0., 0., 1.]])
更多示例:
input:
0 1 1
0 1 0
0 1 1
output (one of several possible ones):
0 0 1
0 1 0
0 0 0
另一个(这表明可能会出现一个问题)
another (this shows one problem that can arise)
input:
0 1 1 1
0 1 0 0
1 1 0 0
a good output (again, one of several):
0 0 1 0
0 1 0 0
1 0 0 0
a bad output (still valid, but has fewer mappings)
0 1 0 0
0 0 0 0
1 0 0 0
更好地展示它们如何成为多个输出
to better show how their can be multiple outputs
input:
0 1 1
1 1 0
one possible output:
0 1 0
1 0 0
a second possible output:
0 0 1
0 1 0
a third possible output
0 0 1
1 0 0
我做了什么?
我现在有一种非常愚蠢的方式来处理它，这完全不能保证正常工作.基本上，我只是从一个单位矩阵中构建一个过滤器矩阵(因为它是理想的映射，每一行和每一列都使用一次)，然后我随机交换其列(n次)并用它过滤原始矩阵，记录过滤器效果最佳的矩阵.
What have I done?
I have a really dumb way of handling it right now which is not at all guaranteed to work. Basically I just build a filter matrix out of an identity matrix (because its the perfect map, every row and every column are used once) and then I randomly swap its columns (n times) and filter the original matrix with it, recording the filter matrix with the best results.
My [non] solution:
import random
import numpy as np
# this is a starting matrix with random values
A = np.array(
[[1, 0, 0, 0],
[1, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 1, 1]])
# add dummy row to make it square
new_col = np.zeros([5,1]) + 1
A = np.append(A, new_col, axis=1)
# make an identity matrix (the perfect map)
imatrix = np.diag([1]*5)
# randomly swap columns on the identity matrix until they match.
n = 1000
# this will hold the map that works the best
best_map_so_far = np.zeros([1,1])
for i in range(n):
a, b = random.sample(range(5), 2)
t = imatrix[:,a].copy()
imatrix[:,a] = imatrix[:,b]
imatrix[:,b] = t
# is this map better than the previous best?
if sum(sum(imatrix * A)) > sum(sum(best_map_so_far)):
best_map_so_far = imatrix
# could it be? a perfect map??
if sum(sum(imatrix * A)) == A.shape[0]:
break
# jk.
# did we still fail
if sum(sum(imatrix * A)) != 5:
print('haha')
# drop the dummy row
output = imatrix * A
output[:,:-1]
#... wow. it actually kind of works.
推荐答案
让我尝试一下.我建议的算法并不总是能提供最佳解决方案，但也许有人可以对其进行改进.
Let me give it a go. The algorithm I suggest will not always give the optimal solution, but maybe somebody can improve it.
-
您始终可以互换两列或两行而不更改问题.此外，通过跟踪更改，您可以始终返回到原始问题.
You can always interchange two columns or two rows without changing the problem. Further, by keeping track of the changes you can always go back to the original problem.
我们将尽可能用1s填充主对角线.通过互换列或行或同时获得两者，获得左上角的第一个1.现在第一行和第一列已固定，我们不再赘述.现在，我们尝试用1填充对角线上的第二个元素，然后修复第二行和第二列.依此类推.
We are going to fill the main diagonal with 1s as far as it will go. Get the first 1 in the upper left corner by interchanging columns, or rows, or both. Now the first row and column are fixed and we don't touch them anymore. We now try to fill in the second element on the diagonal with 1, and then fix the second row and column. And so on.
如果右下子矩阵为零，则应尝试通过使用整个矩阵互换两列或两行，但在对角线上保留现有的1来使那里为1. (这就是问题所在.很容易有效地检查一次交换是否可以提供帮助.但是可能至少需要两次交换，或者可能需要更多.)
If the bottom right submatrix is zero, we should try to bring a 1 there by interchanging two columns or two rows using the whole matrix but preserving the existing 1s in the diagonal. (Here lies the problem. It is easy to check efficiently if one interchange can help. But it could be that at least two interchanges are required, or maybe more.)
当对角线上没有其他1时，我们停止.
We stop when no more 1s can be obtained on the diagonal.
因此，虽然该算法并非总是最佳算法，但也许可以提出一些额外的规则，以实现如何互换列和行，从而尽可能多地将对角线填充为1s.
So, while the algorithm is not always optimal, maybe it is possible to come up with extra rules how to interchange columns and rows so as to populate the diagonal with 1s as far as possible.
这篇关于根据具有多个结果的矩阵构建地图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
