Bir ikili sayı grubunu ayırt etmek için minimum sayıda bit bulmak üzere algoritma

Question

K binary sayılarımız olduğunu varsayalım (her biri aynı uzunlukta). Bu K ikili sayılarını benzersiz bir şekilde tanımlamak için gereken minimum sayıda bit bulmamız gerekir (sürekli olmamak gerekir). Örneğin 100, 110, 1 bit (ikinci pozisyonda) ile ayırt edilebilir. 111, 110, 101, ayırt edilmesi için 2 bit gerekir.

Answer 1

Minimum Set Cover kümesi U ve bir dizi alt kümeleri U arasında S açısından tanımlanmaktadır. U numaralı her öğenin, S'daki kümelerden birinin (en az) tarafından karşılanması gerekir.

Set Cover'u çözebilirseniz, bu sorunu da çözebilirsiniz. Bir dizi U her girişin, u _{i, j} (i < j olduğu), çiftler tekabül (i, j) ve (j, i) arasında inşa varsayalım senin k numaraları (dolayısıyla | U | = k (k - 1)/2). Şimdi n setleri, S inşa , ..., n S _{, n olası bit pozisyonlarına karşılık gelen. S} j farklı çiftler grubuna karşılık gelen tüm elemanların alt kümesidir. sayılar k, l pozisyon j farklıdır Yani, eğer, o zaman u _{k, l} ∈ S _j ayarlayın. Bununla birlikte, bu azalma ile NP-zor bir sorundur. Açgözlü yaklaşımla, minimum sayıda bit için sınırlı bir yaklaşım elde edebilirsiniz, ancak tam olarak minimum değil.

Answer 2

Bu ikilileri bir dizi doğrusal denklem olarak görebiliriz. bu ikili varsa Yani, örneğin için,:

Buradan

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

, biz ekstra ortadan kaldırmak için o denklemleri azaltmak için Gaussian elimination kullanabilirsiniz fark: 1111, 1100, 1001, biz takip kendilerini temsil edebilir değişkenler (yukarıdaki örnekte, x1). İndirgemenin sonucu K değişken değişkenleri olacak ve orijinal sorunun sonucunu elde etmek için bir ek değişken çıkarıyoruz.