python - 等价类优化解

Question

假设有多个大写字母指定的测试用例，一个括号中的字母表示这些是相等的测试用例。我想要最小的 X 字母组。 但相等的测试用例不存在传递关系。 即(A,B)(A,D)无法得到(B，D)。

所以，当输入是: (A,B) (A,C) (A,D) (E) 显然输出应该是 (A,E) 而不是 (B,C,D,E)

当输入是: (A,B) (A,C) (A,D) (B,E) (C,F) (D,G) 在这种情况下，输出应该是 (B,C,D) 而不是 (A,E,F.G)。

当输入为 (A,B,C) (B,D) (C,D) 输出是 (B,C) 或 (A,D)。

非常感谢。

Answer 1

这是一个优化问题，可以为分支定界解决方案制定。看到这个: http://www.sce.carleton.ca/faculty/chinneck/po/Chapter12.pdf