完全な有向グラフがあります。各エッジには一連の数字があります。デフォルトでは、セットはソース ノードに保存されます。各番号は一度だけ保存されることに注意してください。たとえば、ノードにセット {1,2,3} と {2,3,4} を持つ 2 つのエッジがある場合、必要なスペースは 4 つだけです。これで、エッジを選択して、セットを移動元から移動先に 1 つのスペース ペナルティで移動できます。問題は、スペースの使用を最小限に抑えるために、どのセットを反対側に移動するかです。
たとえば、次のグラフがある場合
1->2: {123}
1->3: {456}
2->1: {}
2->3: {456}
3->1: {}
3->2: {123}
元のスペース使用量は 12 です。しかし、すべてのセットを移動先に移動すると、使用されるスペースは 3+3=6 になり、4 つのスペース ペナルティにより、結果は 10 になり、元の設定よりも良くなります。
誰にもこの問題のヒントはありますか? これは NP 完全問題に似ていますか?