5
Sto pensando che questo potrebbe essere NP-completo, ma lo chiederò comunque. Gli algoritmi greedy non sembrano funzionare nella mia testa.Algoritmo per trovare il minor numero di tag che comprende tutti gli elementi?
Dato un set di elementi, ciascuno con 1 o più tag, voglio trovare il set di tag più piccolo che copra tutti gli articoli.
Modifica: Vedere my "solution" here.
solo per riferimento, l'algoritmo ingenuo è n * 2^k. basta scorrere il power set dei tag e verificare che ogni elemento taggato sia coperto dal set corrente. n è il numero di elementi taggati, k è il numero di tag. – aaronasterling
così ... dati 1000 articoli e 3000 tag ... Sto osservando le operazioni 1.2e906 ... cioè irrisolvibili ... così tanto per quel piano. – mpen
@ Mark, per il modo più ingenuo per ottenere una soluzione ottimale è n * 2^k. Non sono sicuro dei modi migliori però. Se vuoi solo un'approssimazione, probabilmente può essere migliorata ben oltre. – aaronasterling