5
이것이 NP 완성일지도 모르겠지만 어쨌든 물어볼 것입니다. 욕심 많은 알고리즘이 내 머리 속에서 작동하지 않는 것 같습니다.모든 항목을 포함하는 태그 중 가장 적은 수의 태그를 찾는 알고리즘?
각 태그가 1 개 이상인 항목 집합이 있으면 모든 항목을 포함하는 가장 작은 태그 집합을 찾고 싶습니다.
편집 :my "solution" here을 참조하십시오.
A
답변
6
관련 문제
- 1. 배열의 모든 요소를 포함하는 항목을 찾는 중
- 2. 가장 좋은 조합을 찾는 알고리즘
- 3. 문자열의 모든 img 태그를 찾는 방법은 무엇입니까?
- 4. 가장 가까운 벡터를 찾는 알고리즘
- 5. C에서 가장 낮은 레벨의 항목을 재귀 적으로 찾는 중
- 6. 하나 이상의 태그를 포함하는 리소스를 찾는 SQL 쿼리
- 7. 최소 태그를 사용하여 채우기를 처리하는 알고리즘
- 8. 하위 문자열의 모든 항목을 찾는 가장 빠른 방법은 무엇입니까?
- 9. 숫자로 시작하는 모든 항목을 찾는 가장 효율적인 MySQL 쿼리는 무엇입니까?
- 10. 패턴과 일치하는 가장 짧은 문장을 찾는 알고리즘
- 11. db.Model ListProperty에서 특정 수의 항목을 일치시키는 가장 효율적인 방법
- 12. 가장 일치하는 속성을 가진 레코드를 찾는 알고리즘
- 13. 텍스트의 모든 키워드를 찾는 효율적인 알고리즘
- 14. 첫 번째 유효한 이름을 찾는 효율적인 알고리즘
- 15. 관련 제출물을 찾는 효율적인 알고리즘
- 16. 적은 수의 항목에 알맞은 전자 상거래 솔루션입니까?
- 17. C# : 적은 수의 문자로 복어가 작동하지 않습니다.
- 18. 태그를 기반으로 사용자에게 콘텐츠를 추천하기위한 알고리즘
- 19. 정규식, 태그 안에 IMG가없는 태그를 찾는 방법은 무엇입니까?
- 20. 항목을 찾는 가장 효율적인 방법은 무엇입니까?
- 21. 목록에서 항목을 찾는 가장 빠른 방법은 무엇입니까?
- 22. 상위 태그 (및 모든 하위 태그) 내의 모든 1 세대 UL 태그를 찾는 데 사용할 jQuery 구문
- 23. 는 닫는 태그를 포함하는
- 24. 제목과 태그를 사용하여 가장 친숙한 항목을 검색하는 방법
- 25. 리소스가없는 슬롯을 찾는 알고리즘
- 26. filterby 후 모든 항목에 대한 모든 관련 태그를 얻기 (태그)
- 27. 가장 많은 수의 배열 찾으십시오.
- 28. 파생 알고리즘을 찾는 알고리즘
- 29. 임의의 수의 이질적인 항목을 렌더링하는 가장 좋은 방법은 무엇입니까?
- 30. 큰 수의 집합에 대한 가장 효율적인 정렬 알고리즘
단순한 알고리즘은 n * 2^k입니다. 태그의 파워 세트를 반복하고 각 태그가 달린 항목이 현재 세트로 덮여 있는지 확인하십시오. n은 태그가 지정된 항목의 수이고, k는 태그의 수입니다. – aaronasterling
그래서 ... 1000 개의 항목과 3000 개의 태그가 있습니다 ... 1.2e906 작업을보고 있습니다 ... 즉, 해결할 수없는 ... 그 계획에 너무 많은 부분. – mpen
@ 마크, 최적의 솔루션을 얻는 가장 순진한 방법은 n * 2^k입니다. 나는 더 나은 방법에 대해 확신하지 못합니다. 근사치를 원한다면 그 이상으로 향상시킬 수 있습니다. – aaronasterling