Scegliere un alfabeto che copre più parole?

Question

Dato un elenco di parole e un alfabeto che ha al massimo P lettere, come possiamo scegliere l'alfabeto ottimale che copre più parole?

Ad esempio: le parole date "aaaaaa" "bb" "bb" con P = 1, l'alfabeto ottimale è "b" poiché "b" copre due parole.

Un altro esempio: le parole date "abmm" "abaa" "mnab" "bbcc" "mnnn" con P = 4, l'alfabeto ottimale è "abmn", poiché copre 4 delle 5 parole.

Esistono algoritmi noti oppure qualcuno può suggerire un algoritmo che risolva questo problema?

Answer 1

Non sono ancora sicuro che sia corretto, ma si spera che sia almeno vicino. Consideriamo una soluzione di programmazione dinamica. Enumerare le parole da 1 a N, le lettere nel nostro alfabeto da 1 a P. Vogliamo essere in grado di risolvere (n, p) in termini di tutte le soluzioni secondarie. Consideriamo diversi casi.

Il caso più semplice è dove l'ennesima parola è già nel dizionario indicato nella soluzione a (n-1, p). Ci consideriamo poi fortunati, le parole coperte da una e lasciamo il dizionario invariato (il ddictionary si riferisce a qualche sottoinsieme di lettere qui).

Supponiamo invece che l'ennesima parola non sia nel dizionario dato da (n-1, p). Quindi il dizionario che risolve (n-1, p) è il dizionario per (n, p), O l'ennesima parola è nella soluzione. Quindi cerchiamo soluzioni che coinvolgono esplicitamente l'ennesima parola. Quindi, aggiungiamo tutte le lettere dell'ennesima parola al dizionario che stiamo considerando. Ora cerchiamo attraverso tutte le precedenti sottoluzioni del modulo (n-1, i), dove i è p-1 o meno. Stiamo cercando il valore più grande di i tale che | d (n-1, i) U d (n) | < = p. Dove d (n-1, i) indica il dizionario associato a quella soluzione, e d (n) significa semplicemente il dizionario associato a tutte le lettere dell'ennesimo. In inglese semplice, utilizziamo le nostre soluzioni per trovare la soluzione migliore con un valore inferiore di p che ci consente di adattare la nuova parola. Una volta trovato il valore di i, combiniamo i dizionari di cui misuriamo la grandezza. Se la grandezza di questo set non è ancora p, ripetiamo la procedura descritta in precedenza. Quando abbiamo creato un dizionario con magnitudine p che copre l'ennesima parola con questa tecnica (o ripetuto attraverso tutte le soluzioni precedenti), calcoliamo la sua copertura e la confrontiamo con la copertura che otterremmo semplicemente usando il dizionario da (n-1, p), e prendiamo il meglio. Se c'è un pareggio, li selezioniamo entrambi.

Non sono completamente convinto della correttezza di questa soluzione, ma penso che potrebbe essere giusto. Pensieri?

Answer 2

farei questo:

1. usare le parole di ingresso per creare una struttura di dati che mappa gli elenchi delle lettere (stringhe) per il numero di parole che essi coprono. Puoi farlo estraendo lettere univoche che formano una parola, ordinandole e usando il risultato come una chiave di mappa hash.
2. Ignorare le voci le cui chiavi sono più lunghe di P (non possono coprire quelle parole con il nostro alfabeto limitato).
3. Per tutte le entrate rimanenti, calcolare un elenco di voci che sono contenute da loro (un alfabeto 'ab' contiene l'alfabeto 'b' e 'a'). Sommare il numero di parole coperte da tali voci.
4. Trova la voce con il numero più alto di chiavi.

Answer 3

Questo problema è NP-hard riduzione da CLIQUE (è una sorta di densa k-sub (iper) problema grafico). Dato un grafico, etichetta i suoi vertici con lettere distinte e, per ciascun bordo, crea una parola di due lettere.Esiste una k-cricca se e solo se possiamo coprire k scegliere 2 parole con k lettere.

La situazione algoritmo anche per CLIQUE è grim (tempi di esecuzione devono essere n^Theta (k) sotto un'ipotesi plausibile), quindi non sono sicuro di cosa raccomandare altro che la forza bruta con primitiva bit arrays.

Answer 4

Come David ha mostrato sopra (con una prova eccellente!), Questo è NP-difficile in modo da non ottenere una risposta perfetta in ogni situazione.

Un approccio da aggiungere alle altre risposte è esprimere questo come un problema di flusso massimo.

Definire un nodo di origine S, un nodo di sink D, un nodo per ogni parola e un nodo per ogni lettera.

Aggiungi bordi da S ad ogni parola della capacità 1.

Aggiungi bordi da ogni parola alle lettere in esso contenute di capacità infinita.

Aggiungere bordi da ogni lettera a D di capacità x (dove definiremo x in un momento).

Quindi risolvere per il taglio minimo di questo grafico (utilizzando un algoritmo di flusso massimo da S a D). Un taglio a una lettera indica che quella lettera non viene inclusa nella soluzione.

Questo può essere pensato come risolvere il problema in cui otteniamo una ricompensa di 1 per ogni parola, ma ci costa x per ogni nuova lettera che usiamo.

Quindi l'idea è di variare x (ad esempio per bisezione) per cercare e trovare un valore per x dove vengono tagliati esattamente i bordi di lettera k. Se gestisci questo, avrai identificato la soluzione esatta al tuo problema.

Questo approccio è ragionevolmente efficiente, ma dipende dai dati di input indipendentemente dal fatto che troverà o meno la risposta. Per alcuni esempi (ad esempio la costruzione di David per trovare clique) scoprirai che variando x improvvisamente salterai dall'includere meno di k lettere ad includere più di k lettere. Tuttavia, anche in questo caso potreste scoprire che aiuta a fornire limiti inferiori e superiori per il numero massimo di parole nella soluzione esatta.