0

類似性マトリックスから2つのシーケンスの最適なアラインメントを見つけようとしています。値が高いほど、アライメントが良好であることを示します。

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を除いて、正確に1つの列/行に配置する必要があります。

つまり、これらのシーケンスの最適なアラインメントは次のとおりです。

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

(1,5)は整列されたペアではありません。これ(1,1)は、より適切な整列であり、行と列が0より大きい場合は1つの整列にしか参加できないためです。

任意の提案をいただければ幸いです。

4

1 に答える 1

0

問題を少し変えています。ここで、各列を正確に1つの行に揃える必要があり、各行を正確に1つの列に揃える必要があります。マトリックスを正方形にするために、以前は複数のアラインメントに参加できた行/列0と同等の行/列を追加しています。正方行列と、各行/列が1つの線形にのみ関与するという要件がある場合、問題は安定結婚問題のインスタンスとして扱うことができます。

于 2012-12-02T22:12:55.523 に答える