길이 10의 시퀀스가 0과 1로 구성되어 있습니다. 예 :시퀀스 세트 - 주어진 시퀀스 인 서브 세트 찾기
1010100000
1011000001
1011100010
1100000100
0011111011
요법
각 열에 집합 적으로 0이있는 시퀀스를 찾고 싶습니다.
1100000100
0011111011
이 세 : 예를 들어, 알고리즘은이 두 가지를 반환해야이하는 알고리즘이
1100110000
0011111111
1111001111
등
있습니까?
설명하는 문제는 모든 솔루션을 찾으려는 exact cover problem의 제한된 경우입니다. 이 문제의 일반 버전은 NP 하드이므로이 큰 문제에 대한 효율적인 일반 알고리즘은 알려져 있지 않습니다.
모든 가능한 해결책을 찾으려면 비트 벡터의 모든 하위 집합을 나열하고 각 비트 열에 정확히 하나씩 0이 있는지 테스트 해 볼 수 있습니다. 역 추적 검색 알고리즘을 구현하여 모든 하위 집합을 선택하는 것도 고려할 수 있지만 작동하지 않는 경로 (예 : 동일한 열에 0이 포함 된 두 비트 벡터가 포함 된 경로)를 찾는 경로는 중지됩니다. 원하는 경우이 일반적인 문제에 대한 모든 해결책을 나열하도록 특별히 고안된 dancing links algorithm을 구현할 수 있습니다.
희망이 도움이됩니다.
아이디어에 감사드립니다. 나는 뭔가를 알아 내려고 노력할 것이다. – user11775
"함께"는 무엇을 의미합니까? 그들을 추가하고, 그들? 또는 그들? 나에게 XOR처럼 보입니다. 또한, "드 Bruin 그래프"를 봐 – wildplasser
두 번째 예제는 단지 9 0을 가지고있다. – mavili
나는 그가 '0'의 '시퀀스'를 의미한다고 생각한다. 내가 맞습니까? – mavili