2進数のセットを区別するための最小ビット数を見つけるアルゴリズム

Question

K個のバイナリ番号（それぞれ同じ長さ）があるとします。これらのK個の2進数を一意に識別するために必要なビット数を最小限にする（連続である必要はありません）必要があります。例えば100,110は1ビット（第2の位置）で区別することができる。 111,110,101は2ビットを区別する必要がある。

Answer 1

Minimum Set CoverがセットU、及びUのサブセットの集合S に関して定義されます。 Uの各要素は、Sのセットのうち少なくとも1つでカバーする必要があります。

Set Coverを解決できる場合は、この問題も解決できます。あなたがセットを構築するとしその各エントリU、U _私は、J（私< J）、（i、j）はペア（i、j）のとにあなたのに対応します（したがって、| U | = k（k-1）/ 2）。今Nセット、Sを構築、...、nは S _{、のn可能なビット位置に対応します。セットS jは、ペアの位置jの区別に対応するすべての要素のサブセットです。数字K、L位置Jが異なる場合には、であり、次いで、U K、L ∈ S Jを設定します。}

しかし、これは削減によるNP困難な問題です。欲張りのアプローチでは、必要最小限のビット数の近似を得ることができますが、厳密には最小ではありません。

Answer 2

これらのバイナリを一連の線形方程式として見ることができます。私たちはこれらのバイナリ持っているのであれば、たとえば ため、：1111、1100、1001、我々は次のようにそれらを表現することができます

x1 + x2 + x3 + x4 = y1 
x1 + x2 + 0 + 0 = y2 
x1 + 0 + 0 + x4 = y3 

ここから、我々は余分排除するために、これらの方程式を減らすためにGaussian eliminationを使用することができることを実感変数（上記の例ではx1）です。削減の結果はK個の異なる変数に設定され、元の質問の結果を得るために1つの余分な変数が削除されます。