P 문자가 많아야 단어 목록과 알파벳 목록이 주어지면 대부분의 단어를 포함하는 최적의 알파벳을 어떻게 선택할 수 있습니까?가장 많은 단어를 포함하는 알파벳 선택?
예 : P = 1 인 단어 "aaaaaa" "bb" "bb"가 주어지면 "b"는 두 단어를 포함하므로 최적의 알파벳은 "b"입니다.
다른 예 : P = 4 인 단어 "abmm" "abaa" "mnab" "bbcc" "mnnn"이 주어지면, 최적 단어는 "abmn"입니다.
알려진 알고리즘이 있습니까? 아니면 누군가이 문제를 해결하는 알고리즘을 제안 할 수 있습니까?
아직 정확한지는 확실하지 않지만, 적어도 가까운 것은 좋겠다. 우리는 동적 프로그래밍 솔루션을 고려합니다. 알파벳 1에서 P까지의 문자 인 1에서 N까지의 단어를 열거합니다. 모든 하위 솔루션 측면에서 (n, p)를 풀 수 있어야합니다. 몇 가지 경우를 고려합니다.
가장 단순한 경우는 n 번째 단어가 (n-1, p)의 해에 이미 사전에있는 경우입니다. 우리는 스스로 운이 좋다고 계산하고, 단어 하나를 덮고, 사전을 변경하지 않고 남겨 둡니다 (ddictionary는 여기에서 일부 문자 집합을 나타냅니다).
대신에 n 번째 단어가 (n-1, p)에 의해 주어진 사전에 없다고 가정하십시오. 그런 다음 사전 (n-1, p)을 해결하는 사전이 (n, p)에 대한 사전이거나 n 번째 단어가 솔루션에 있습니다. 그래서 우리는 n 번째 단어를 명시 적으로 포함하는 솔루션을 찾습니다. 그래서, 우리는 고려하고있는 사전에 n 번째 단어의 모든 문자를 추가합니다. 우리는 이제 모든 이전의 해답을 (n-1, i) 형식으로 검색합니다. 여기서 i는 p-1 이하입니다. 우리는 | d (n-1, i) U d (n) |가 0이되도록 i의 최대 값을 찾고있다. < = p. 여기서 d (n-1, i)는 해당 해와 연관된 사전을 의미하고, d (n)은 단순히 n 번째 단어의 모든 문자와 관련된 사전을 의미합니다. 평이한 영어로, 우리는 새로운 해결책을 사용하여 새로운 단어에 맞는 작은 값의 p로 최상의 솔루션을 찾습니다. 우리가 i의 가치를 발견하면 우리는 규모를 측정하고있는 사전들을 결합합니다. 이 집합의 크기가 여전히 p가 아니면 앞에서 설명한 과정을 반복합니다. 이 기법으로 n 번째 단어를 다루는 (또는 이전의 모든 솔루션을 통해 반복되는) 크기 p 인 사전을 만들었 으면, 우리는 그 범위를 계산하고 그것을 (n-1, p), 우리는 더 나은 것을 선택합니다. 넥타이가 있다면, 우리는 둘 다 골라냅니다.
Im이 솔루션의 정확성을 완전히 확신하지는 못했지만 올바른 것으로 생각됩니다. 생각?
3 단락의 일부를 완전히 따르지는 않지만 일부 난이도 (i <= n, j <= P)의 솔루션에 최적 인 여러 가지 사전이있을 수 있으며 모든 필요가 있다고 생각합니다. (n 번째 단어가 이미 (n-1, P)를 최적으로 해결하는 사전에있을 때) 첫 번째 경우에 대해 저장되도록해야합니다. –
동의하지만 여러 개의 사전을 저장하는 것은 그렇게 어렵지 않습니다. 더 큰 관심사는 어떤 경우에는 미묘하게 실패 할 수도 있다는 것입니다. 해답은 배낭 문제 이후에 모델링되지만 배낭의 용량은 서로 다르다. 반면 사전의 조합은 두 사전의 적용 범위의 합보다 크거나 같거나 작은 범위를 가질 수있다. 케이스가 가장 문제를 제기 함). 여전히 효과가있을 수 있습니다. 나는 그 괜찮은 출발로 그 가치가 게시 생각. 그것은 질문에 완전히 답할 수 없으므로 나는 선호 할 수있다. –
나는이 작업을 수행 할 것 :
이 문제는 CLIQUE (가장 밀도가 높은 k-sub (하이퍼) 그래프 문제)에서 축소하여 NP 하드입니다. 그래프가 주어지면 꼭지점에 별개의 문자로 레이블을 붙이고 각 가장자리에 대해 두 글자로 된 단어를 만듭니다.우리가 k를 커버 할 수있는 경우에만 k- 클릭이 존재하는데, k 문자로 2 단어를 선택하면된다.
CLIQUE의 경우에도 알고리즘 상황은 grim (실행 시간은 그럴듯한 가설 하에서 n^Theta (k) 여야 함)이므로 원시 코드 bit arrays을 사용하여 무차별 대항력 이외의 방법을 권하는 것은 확실하지 않습니다.
좋은 환원, CLIQUE를 시도한 적이 없을 것입니다! 나는 3SAT에서 진전을 이루면서 도망 가고 있었지만, 크고 추한 ... –
데이비드는 훌륭한 증거로 위의 그림과 같이 NP 하드이므로 모든 상황에서 완벽한 답변을 얻을 수 없습니다.
다른 답변에 추가하는 한 가지 방법은 최대 흐름 문제로 이것을 표현하는 것입니다.
소스 노드 S, 싱크 노드 D, 각 단어에 대한 노드 및 각 문자에 대한 노드를 정의하십시오.
1.
이 무한한 용량을 포함하는 문자로 각 단어로부터 에지를 추가 용량의 각각의 워드에 S로부터 에지를 추가한다.
각 문자의 가장자리를 용량 D의 D에 추가합니다. 여기서 x는 한 번에 x를 정의합니다.
다음으로 (S에서 D까지의 최대 흐름 알고리즘을 사용하여)이 그래프의 최소 자르기를 구하십시오. 글자를 자르면 해당 글자가 솔루션에 포함되지 않음을 나타냅니다.
이것은 각 단어에 대해 1의 보상을 얻는 문제를 해결하는 것으로 생각할 수 있지만, 우리가 사용하는 각각의 새로운 문자에 대해 x가 들지 요합니다.
그런 다음 아이디어는 정확한 k 문자 가장자리가 잘리는 x 값을 찾기 위해 x를 (예 : 이분법으로) 변경하는 것입니다. 당신이 이것을 관리한다면 당신은 당신의 문제에 대한 정확한 해결책을 발견하게 될 것입니다.
이 방법은 비교적 효율적이지만 답변을 찾을 수 있는지 여부에 따라 입력 데이터에 따라 다릅니다. 특정 사례 (예 : 파벌을 찾기위한 David의 구조)에서는 x가 다를 때 k 번째 문자 미만을 포함하는 것에서 k 번째 문자를 초과하는 것으로 갑자기 이동한다는 것을 알 수 있습니다. 그러나이 경우에도 정확한 해결책의 최대 단어 수에 대해 상한 및 하한이 제공된다는 점에서 도움이 될 수 있습니다.
P는 얼마나 커질 수 있습니까? 그리고 얼마나 많은 별개의 글자들이 (전체적으로 말하면) 있습니까? – kraskevich
정확히 어떻게 알아내는 데 열심히 노력하고 있지만 사소하지는 않습니다. 배낭 문제에 대한 동적 프로그래밍 의사 다항식 솔루션을 살펴보기는하지만이 정맥을 시도 할 것을 권합니다. –
어떻게 질문의 이전 버전은 9 downvotes를받을 수 있었고,이 노골적인 두 번째 시도는 10 upvotes를 받았습니다? – Marco13