さて、今手元にある小さな作品で問題に直面しています...
主な目標は、与えられたグラフ (重みなしで有向) を持ち、すべてのエッジをカバーする最小の合計長でパスのグループ (可能であれば 1 つのパスのみですが、それ以上でもかまいません) を発見することです。その他の「制約」は、グラフが DFA であるため、パスは初期状態で開始し、受け入れ状態で終了する必要がある (マークされている) ことです。
最初は、これが中国の郵便配達員問題に似ていることに気づきました。実際、そうです。しかし、私の場合、グラフは方向付けられており (これは少し変わっていると思います)、結果のパスが最短のままであるため、エッジを複数回処理しても問題はありません。
オイラー パスと T-Joins についていくつか読んだことがありますが、これがおそらく私の問題の解決策です。私がそれを正しく理解していれば、私がすべきことは、グラフでオイラー パスを見つけて、存在しない場合は存在させたり、T-Joins を複製したり、そのようなことをすることです...私は多くの問題を抱えていましたこれを理解しても、これが私の問題に対する答えであるかどうかさえわかりません... (ここで見つけた最も短くてわかりやすいテキスト: http://en.wikipedia.org/wiki/Route_inspection_problem )
このグラフを考えると、短い例を残すだけです (1 は初期で、5 は承認です)。
1 -> 2;
2 -> 3;
2 -> 4;
4 -> 5;
私の問題に対する答えは、1 -> 2 -> 4 -> 5 および 1 -> 2 -> 3 となるはずです (この場合、3 は受け入れ状態ではないという事実も処理する必要がありますが、しかし、エッジのないすべての状態を他のノードに受け入れ状態としてフラグを立てることで、簡単にそれを乗り越えることができます)。
すべてを十分に説明したことを願っています。
前もって感謝します！