比较布尔矩阵
我有一个小问题。我需要将一个填充有 1 和 0 的二维数组（我们称之为矩阵 A - 零实际上代表空白点，1 是足球运动员在场上的位置）与许多其他以不同方式填充的矩阵（但同样，只是 1）进行比较和零），结果应该表明哪个矩阵与矩阵 A 最相似。通过相似性，我的意思是场上球员分布（或位置）的相似性 - 因此球员位置最相似的矩阵矩阵 A 将被选择为进一步的东西。
有人可以帮忙解决这个算法问题吗？
我用 C++ 编写它，但伪代码就足够了。问题只是一个比较算法。最好的情况是比较函数的输出类似于相似系数，我可以将其存储在数组中，然后使用它选择最相似的矩阵。但我就是想不出一些算法来进行相似性比较。
编辑：关于相似性和算法的一些澄清是从我下面的评论中复制的 -
矩阵 A - 矩阵 A , 矩阵 1 - 矩阵1，矩阵2 - Matrix2，与矩阵 A 相比，两者都有 1 个变化，但对我来说 - 矩阵 2 必须“更相似” - 因为玩家站得更接近其在矩阵 A 中的位置
考虑矩阵要达到 8x6 左右或类似的大小，它需要相当快 - 每个游戏周期都会计算一次（因此每 20 毫秒左右..），并且每方都有 5 个玩家。
I have a little problem. I need to compare one two-dimensional array filled with ones and zeros (lets call it Matrix A - zeros actually represent blank spots and ones are positions of football players on the field) against lots of other matrices filled differently (but again, just ones and zeros) and the result should be some indication which of the matrices is most similar with the Matrix A. By similarity I mean similarity in distribution (or positioning) of the players on the field - so the matrix with players postition the most similar to the matrix A will be chosen for further stuff.
Could somebody help with this algorithmic problem ?
I'm writing it in c++ but pseudo-code would suffice. The problem is just a comparison algorithm. The best would be if the output of the comparison function would be something like similarity coefficient which I can store in an array and later choose the most similar matrix using it. But I just cant come up with some algorithm for that similarity comparison.
EDIT: some clarifications about similarity and algorithm copied from my comments below -
Matrix A - Matrix A , Matrix 1 - Matrix1 , Matrix 2 - Matrix2, Both have 1 change in comparison with Matrix A, but for me - matrix 2 must be "more similar" - because player is standing closer to its position in matrix A
Matrices are considered to be around 8x6 or something like that, it needs to be reasonably fast - it will be computed every game cycle (so every 20ms or so..), and there will be 5 players on each side.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
零/一矩阵不能很好地满足您的需求。
您关心玩家总数位移。由于玩家数量是恒定的，因此可以将游戏状态表示为矩阵，该矩阵的行对应于玩家，列对应于场坐标。例如，对于两个玩家 {{1,0,0},{0,0,0},{0,0,1}} 将是 {{1,1},{3,3}}。给定两个游戏状态矩阵 A、B，您可以将它们视为向量并使用任何距离度量计算向量相似度 (喜欢这些，另请参阅 C++库）。一个简单的选项是余弦相似度：
dot(A,B)(在你的情况下，规范是不变的。）A zero/one matrix is not a good representation for your needs.
You care about the total player displacement. Since the number of players is constant it is possible to represent a game state as a matrix whose rows correspond to players and columns corresponds to field coordinates. So, for example, for two players {{1,0,0},{0,0,0},{0,0,1}} will be {{1,1},{3,3}}. Given two games state matrices A, B, you can treat them as vectors and compute vector similarity with any distance measure (like these, also see C++ library). One simple option is cosine similarity:
dot(A,B)(in your case the norms are constant.)一种可能的简单算法的想法，虽然不是很强大，但在您的情况下就足够了：
1 表示两个原始矩阵之间存在差异，0表示两个矩阵中的单元格相同。这将为您提供每两个矩阵更改的单元格数量。
在您在评论中提供的示例中，根据此算法，Matrix 1 将获得
2分数，Matrix 2 将获得8分数，这意味着 Matrix与 Matrix 2 相比，1 与A更相似。An idea for a possible simple algorithm, though not very robust, but which could be enough in your case:
1means there was a difference between the two original matrices, and0means that cell was identical in both matrices.This would provide you, for every two matrices, the number of cells that are changed.
In the example you provided in the comment, according to this algorithm, Matrix 1 would get a score of
2and Matrix 2 would get a score of8, which means that Matrix 1 is a lot more similar toAthan Matrix 2.如果你想检查 1 秒之间的距离，那就有点麻烦了。
AND 两个数组，然后求和 - 这给出了两个 1 的距离=0 的位置数。
现在通过在所有 4 个方向上移动原始图像来生成一个掩模，或者将它们组合在一起得到 MASK1。
AND MASK1 然后求和得出距离=1 的位置数。
您可以再生成 4 个用于对角线移位的蒙版。
您可以对不同距离的总和进行加权。
例如，如果您的原始数组是
<代码>
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
那么 MASK1 将是
<代码>
0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0
If you want to check for distance between 1s it will be a little work.
AND the two arrays, then sum - this gives the number of positions where two 1s have distance=0.
Now generate a mask by shifting the original in all 4 directions, OR them together to give MASK1.
AND MASK1 then sum to give the number of positions where distance=1.
You can generate 4 more masks for diagonal shifts.
You can weight the sums for different distances.
For example, if your original array is
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
Then MASK1 would be
0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0