5
Ich denke, das könnte NP-komplett sein, aber ich werde trotzdem fragen. Gierige Algorithmen scheinen nicht in meinem Kopf zu funktionieren.Algorithmus, um die geringste Anzahl von Tags zu finden, die alle Elemente umfassen?
Angesichts einer Reihe von Elementen, jede mit 1 oder mehr Tags, möchte ich den kleinsten Satz von Tags, die alle Elemente abdecken.
Bearbeiten: Siehe my "solution" here.
nur als Referenz, der naive Algorithmus ist n * 2^k. Iterieren Sie einfach die Leistungseinstellungen der Tags und prüfen Sie, ob alle markierten Elemente von der aktuellen Gruppe abgedeckt sind. n ist die Anzahl der markierten Objekte, k ist die Anzahl der Tags. – aaronasterling
so ... gegeben 1000 Artikel und 3000 Tags ... Ich sehe 1.2e906 Operationen ... d. H. Unlösbar ... so viel für diesen Plan. – mpen
@Mark, für den naivsten Weg, optimale Lösung zu bekommen, ist es n * 2^k. Ich bin mir nicht sicher über bessere Möglichkeiten. Wenn Sie nur eine Annäherung wünschen, kann es wahrscheinlich weit darüber hinaus verbessert werden. – aaronasterling