Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects ( polynomial space). (Generally, however, they are not classed as polynomial-time algorithms, because the number of objects they generate is exponential.) They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.
Reverse-search algorithms were introduced by David Avis and Komei Fukuda in 1991, for problems of generating the vertices of convex polytopes and the cells of arrangements of hyperplanes. [1] They were formalized more broadly by Avis and Fukuda in 1996. [2]
A reverse-search algorithm generates the combinatorial objects in a state space, an implicit graph whose vertices are the objects to be listed and whose edges represent certain "local moves" connecting pairs of objects, typically by making small changes to their structure. It finds each objects using a depth-first search in a rooted spanning tree of this state space, described by the following information: [2]
From this information it is possible to find the children of any given node in the tree, reversing the links given by the parent subroutine: they are simply the neighbors whose parent is the given node. It is these reversed links to child nodes that the algorithm searches. [2]
A classical depth-first search of this spanning tree would traverse the tree recursively, starting from the root, at each node listing all of the children and making a recursive call for each one. Unlike a depth-first search of a graph with cycles, it is not necessary to maintain the set of already-visited nodes to avoid repeated visits; such repetition is not possible in a tree. However, this recursive algorithm may still require a large amount of memory for its call stack, in cases when the tree is very deep. Instead, reverse search traverses the spanning tree in the same order while only storing two objects: the current object of the traversal, and the previously traversed object. Initially, the current object is set to the root of the tree, and there is no previous object. From this information, it is possible to determine the next step of the traversal by the following case analysis: [2]
This algorithm involves listing the neighbors of an object once for each step in the search. However, if there are objects to be listed, then the search performs steps, so the number of times it generates neighbors of objects is within a factor of two of the number of times the recursive depth-first search would do the same thing. [2]
Examples of the problems to which reverse search has been applied include the following combinatorial generation problems:
Other applications include algorithms for generating the following structures:
Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects ( polynomial space). (Generally, however, they are not classed as polynomial-time algorithms, because the number of objects they generate is exponential.) They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.
Reverse-search algorithms were introduced by David Avis and Komei Fukuda in 1991, for problems of generating the vertices of convex polytopes and the cells of arrangements of hyperplanes. [1] They were formalized more broadly by Avis and Fukuda in 1996. [2]
A reverse-search algorithm generates the combinatorial objects in a state space, an implicit graph whose vertices are the objects to be listed and whose edges represent certain "local moves" connecting pairs of objects, typically by making small changes to their structure. It finds each objects using a depth-first search in a rooted spanning tree of this state space, described by the following information: [2]
From this information it is possible to find the children of any given node in the tree, reversing the links given by the parent subroutine: they are simply the neighbors whose parent is the given node. It is these reversed links to child nodes that the algorithm searches. [2]
A classical depth-first search of this spanning tree would traverse the tree recursively, starting from the root, at each node listing all of the children and making a recursive call for each one. Unlike a depth-first search of a graph with cycles, it is not necessary to maintain the set of already-visited nodes to avoid repeated visits; such repetition is not possible in a tree. However, this recursive algorithm may still require a large amount of memory for its call stack, in cases when the tree is very deep. Instead, reverse search traverses the spanning tree in the same order while only storing two objects: the current object of the traversal, and the previously traversed object. Initially, the current object is set to the root of the tree, and there is no previous object. From this information, it is possible to determine the next step of the traversal by the following case analysis: [2]
This algorithm involves listing the neighbors of an object once for each step in the search. However, if there are objects to be listed, then the search performs steps, so the number of times it generates neighbors of objects is within a factor of two of the number of times the recursive depth-first search would do the same thing. [2]
Examples of the problems to which reverse search has been applied include the following combinatorial generation problems:
Other applications include algorithms for generating the following structures: