-1

テストカバーの問題は、次のように定義できます。

一連のn病気と、m症状をチェックするために実行できる一連のテストがあるとします。また、次のものが与えられます。

  • nxn行列A。ここで、は、th病の患者に対してthテストA[i][j]を実行した結果を表す2進値です（1は陽性の結果を示し、0は陰性を示します）。ji
  • テストの実行コストj、c_j; そしてそれ
  • すべての患者はちょうど1つの病気になります

nタスクは、最小限のコストで各疾患を一意に識別できる一連のテストを見つけることです。

この問題は、目的関数を最小化する整数線形計画として定式化できます。\sum_{j=1}^{m} c_j x_jここで、セットにx_jテストを含めることを選択した場合は= 1、それ以外の場合は0です。j

私の質問は：

この問題の線形制約のセットは何ですか？

ちなみに、この問題はNP困難であると思います（一般的な整数線形計画法と同様）。

4

2 に答える 2

0

私が正しければ、あなたはただ確認する必要があります 

\sum_j x_j.A_ij >= 1 forall i
于 2012-04-11T10:40:52.003 に答える
-1

=0のようなすべてのののth列をT削除した結果の行列とします。jAjx_j

次に、任意の2つの病気を一意に区別できる一連のテストを選択することは、すべての行Tが一意であることを確認することと同じです。

k2つの行を観察し、すべてのl場合に限り同一です。(T[k][j] XOR T[l][j]) = 0j

したがって、必要な制約は次のとおりです。

\sum_{j=1}^{m} x_j(A[k][j] XOR A[l][j]) >= 1

すべてのために1 <= k <= mそして1 <= l <= 1そのようなk != l。

係数を事前に計算できるため、上記の制約は線形であることに注意してください(A[k][j] XOR A[l][j])。

于 2012-04-13T20:50:44.193 に答える