在Python中，从带有一些褶皱的相似矩阵中寻找最佳的成对对齐集

Question

我试图从相似矩阵中找出两个序列的最佳对齐方式。值越高表示对齐效果越好。你知道吗

import numpy as np
a = np.array([
[0,5,5,5,5,5,5,5],
[3,10,0,0,0,9,0,0],
[3,0,10,0,0,0,1,0],
[3,0,0,9,0,0,0,0],
[3,0,0,0,0,0,0,10],
])

除行0和列0外，每一行/列必须正好与一列/行对齐，行0和列0可用于0或多个对齐。你知道吗

也就是说，这些序列的最佳对齐方式是：

(0,0)
(1,1)
(2,2)
(3,3)
(0,4)
(0,5)
(0,6)
(4,7)

(1,5)不是对齐对，因为(1,1)是更好的对齐方式，并且行和列>；0只能参与一次对齐。你知道吗

如有任何建议，我们将不胜感激。你知道吗

Answer 1

我正在稍微改变这个问题。现在，每列必须正好对齐到一行，每行必须正好对齐到一列。为了使矩阵成为正方形，我添加了相当于行/列0的行/列，它以前可以参与多个对齐。对于一个方阵和要求每一行/列只参与一次对齐的问题，可以将其视为稳定婚姻问题的一个实例。你知道吗