지정된 세트의 모든 문자를 포함하는 단어의 최단 조합 찾기

Question

"개", "물고기", "실행", "프로그래밍"과 같은 단어를 배열로 가져옵니다. .

a1의 단어 중 하나를 다른 단어와 결합 할 수 있습니다 (예 : "개"및 "프로그래밍"을 "개 프로그래밍"에 결합 할 수 있음). 그리고 나서 문자열이 나타날 때까지 매우 큰.

나는 또한 "de", "s", "x?", "umh"와 같은 문자열 (a2라고 부름)을 얻었습니다. a2의 어떤 문자열에서도 찾을 수없는 문자열이 없음을 보장합니다.

내가 찾고있는 것은 a2 안에있는 모든 문자열을 포함하는 가장 짧은 문자열 (해당 문자열을 만드는 데 얼마나 많은 조합이 필요한지, 문자열이 얼마나 많은 문자가 아닌가에 따라 가장 짧음)입니다. 최소 길이를 특징으로하는 하나 이상의 문자열이 있다면, 나는 무엇이든 선택할 수 있으며 프로그램에서 탈락 할 수 있습니다.

배열이 상대적으로 작더라도 사실상 단어를 결합 할 수있는 옵션이 존재하기 때문에 이것이 잘못 될 수는 없다고 생각합니다. 그러나 잘못된 것으로 입증되기를 바랍니다!

가장 짧은 문자열을 얻는 좋은 방법이 있습니까? 아니면 가장 짧은 결과를 얻을 수있는 방법이 있습니까? 아니면 짧은 문자열을 찾기 위해 발견 알고리즘을 사용해야합니까?

편집 : a2에서 대부분의 문자열을 덮은 a1에서 문자열을 선택한 다음 a2에서 해당 항목을 제거하고 다시 시작했지만 작동하지 않습니다! 그것은 꽤 좋은 결과를 산출하지만, 최고는 아닙니다.

Answer 1

예와 같이 대시로 단어를 결합하면

dog + programming + sky = dog-programming-sky 

및 A2에있는 단어

다음은 위장에 불과 SET-COVER, NP에 완전 최적화 문제의 대시를 포함하지 않습니다. 그런 다음 SET-COVER에서 사용할 수있는 솔루션 전략을 사용하여 문제를 해결할 수 있습니다. SET-COVER에 대한 빠른 근사 알고리즘이 있지만 가장 작은 솔루션을 원한다면 최악의 지수 알고리즘을 사용해야합니다.

대시가없는 단어를 결합하면 (예 :

dog + programming + sky = dogprogrammingsky 

이 문제는 더 어렵습니다. "ogpro"는 구성 문자열 중 하나의 하위 문자열이 아니더라도 결합 된 단어에서 발견됩니다.