したがって、基本的に次のような問題があります。文字列がたくさんあり、すべてのパスが文字列に対応するように、またはその逆になるようにDAGを構築したいと思います。ただし、文字列を任意に並べ替える自由があります。文字の順序は関係ありません。私が生成するDAGには、それに関連するコストがあります。基本的に、DAGのブランチのコストは、その子パスの長さに比例します。
たとえば、文字列BAAA、CAAA、DAAAがあり、それらを並べ替えることなくそれらを表すDAGを作成するとします。私は得る：
（）->（B、C、D）-> A-> A-> A
ここで、タプルは分岐を表します。
私の目的のためのより安価な表現は次のようになります：
（）-> A-> A-> A->（B、C、D）
問題は次のとおりです。n個の文字列が与えられた場合、対応するDAGのコストが最も低くなるように文字列を並べ替えます。ここで、コスト関数は次のとおりです。多様性を持って訪問してください。
したがって、最初の例のコストは12です。これは、トラバーサルでAを複数回訪問する必要があるためです。2番目の例のコストは6です。これは、ブランチを処理する前にAを1回だけ訪問するためです。
この問題はNP困難だと感じています。形式言語についての質問のようで、私はそのような種類のアルゴリズムに精通していないため、削減をどのように行うべきかを理解できません。完全な答え自体は必要ありませんが、誰かが関連していると思われるよく知られた問題のクラスを指摘できれば、それをいただければ幸いです。