本当に巨大なa1単語 ( dog、fish、runなど)の配列 ( と呼びましょう) を取得しました。programming
単語のうちのa1どれでも他の単語と組み合わせることができ (たとえば、 and と組み合わせることができますdog) programming、dog-programming文字列が非常に大きくなるまで、何度も何度も組み合わせることができます。
a2また、文字列の配列 ( と呼びましょう) も取得しました ( de、s、x?、などumh、ほとんど何でもかまいません)。a2a1 のどの文字列にも見つからない文字列は存在しないことが保証されています。
私が探しているのは、 内のすべての文字列を含む最短の文字列 (文字列に含まれる文字数ではなく、その文字列を作成するのに必要な組み合わせの数に関して最も短い) ですa2。最小の長さを特徴とする文字列が複数ある場合は、任意の文字列を選択して、プログラムから抜け出すことができます。
配列が比較的小さい場合でも、単語を組み合わせるオプションは事実上無限にあるため、これをブルートフォースすることはできないと思いますが、間違っていることを証明したいと思います!
確実に最短の結果が得られる最短の文字列を取得する良い方法はありますか、それともヒューリスティックアルゴリズムを使用してかなり短い文字列を検索する必要がありますか?
a2 のほとんどの文字列をカバーする文字列を a1 から選択し、a2 からそれらの項目を削除して、最初からやり直そうとしましたが、うまくいきません! かなり良い結果が得られますが、最高ではありません。