论文标题
列举等效类别的解决方案类别的一般框架
A general framework for enumerating equivalence classes of solutions
论文作者
论文摘要
当问题具有多个解决方案时，通常取决于基本环境，枚举（即列出）所有问题。即使可以以多项式延迟进行枚举，也就是说，花费的时间不超过多项式时间从一个解决方案到下一种解决方案，这可能会很昂贵，因为解决方案的数量本身可能很大，包括有时指数。此外，根据应用的不同，这些解决方案中的许多可以视为等效。在很少的特定情况下仅解决了对等价类别或每个类别的一个代表性列举或每个级别的代表性枚举的问题（没有生成所有解决方案）的问题。在本文中，我们提供了一个通用框架，该框架在多种情况下在多项式延迟中解决此问题，包括可以通过动态编程算法来解决的优化，以及解决方案之间的某些类型的等效关系。
When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of contexts, including optimization ones that can be addressed by dynamic programming algorithms, and for certain types of equivalence relations between solutions.
