Trova il numero binario con una distanza massima di martello WRT dato un set di numeri binari
-
05-11-2019 - |
Domanda
Supponiamo di avere un set $ A $ di numeri binari con la stessa lunghezza $ n $. Per esempio (con $ n = 8 $):
$ A = {10010011, 01011011, 00010010, 11110001 } $
Ora, voglio trovare il numero binario $ z $ (anche con $ n $ bit) in modo tale che la distanza minima di keting tra $ z $ e uno di questi numeri è massimizzato.
cioè $ z = arg max {d (x, a) mid x in x } $
insieme a
$ d (x, a): = min {d (x, a) mid a in a } $
dove $ X $ è l'insieme di tutti $ n $-bit numeri binari e $ d (x, a) $ la distanza di Hamming tra $ x $ e $ a $.
Esiste un algoritmo efficiente per questo?
Ovviamente, se $ n $ è abbastanza piccolo che possiamo forzare questo, ma sto cercando qualcosa di più efficiente quando $ n $ è grande. La dimensione di $ A $, d'altra parte, può essere assunto relativamente piccolo, quindi qualsiasi polinomio algoritmo in $ | A | $ è ok. Inoltre, non deve essere un algoritmo esatto. Anche qualsiasi algoritmo che si avvicina alla risposta corretta è il benvenuto.
Nessuna soluzione corretta