Efficient Algorithms for Generating Discrete Structures

给定一个属性，我们希望设计算法来生成具有该属性的所有离散对象。我们希望在没有重复的情况下有效地生成所有对象。这是计算机科学中的基本问题之一，在包括系统测试在内的许多应用中也经常出现。对于平面结构，我们已经设计了许多高效的生成算法。这些算法很简单，理论上比任何已知的算法都快。该算法只需要对每个对象进行固定次数的计算。在本研究中，我们对这些方法进行了扩展，并针对许多非平面结构设计了更通用的生成算法。例如，我们得到以下结果。给定一个偏置集P，提出了几种生成P的所有线性扩展的算法。我们设计了一个简单的算法，在最坏情况下，在常数时间内生成每个线性扩展。该算法比任何已知的算法都要快。已知的最佳算法对每个线性扩展精确生成两次并输出其中一个，而我们的算法基于图上的生成树结构，对每个线性扩展精确生成一次。

Given a property we wish to design algorithms to generate all discrete objects with the property. We wish to efficiently generate all objects without repetitions. This is one of basic problems in computer science, and also frequently arises in many applications, including system test.For planar structures we have already designed many efficient generating algorithms. Those algorithms are simple and theoretically faster than any known algorithms. The algorithms need only constant number of computations for each object.In this research we have extended the methods, and designed more general generation algorithms for many non-planar structures. For instance, we have the following result.Given a poset P, several algorithms have been proposed for generating all linear extensions of P.We have designed a simple algorithm which generates each linear extension in constant time in worst case. The algorithm is faster than any known algorithm. The known best algorithm generates each linear extension exactly twice and output one of them, while our algorithm, based on a spanning tree structure on a graph, generates each linear extension exactly once.