Algoritmo de búsqueda inversa

Los algoritmos de búsqueda inversa son una clase de algoritmos para generar todos los objetos de un tamaño dado, a partir de ciertas clases de objetos combinatorios . En muchos casos, estos métodos permiten generar los objetos en tiempo polinomial por objeto, utilizando solo la memoria suficiente para almacenar un número constante de objetos ( espacio polinomial ). (Generalmente, sin embargo, no se clasifican como algoritmos de tiempo polinomial, ya que el número de objetos que generan es exponencial). Funcionan organizando los objetos a generar en un árbol de expansión de su espacio de estados y, a continuación, realizando una búsqueda en profundidad en dicho árbol.

Los algoritmos de búsqueda inversa fueron introducidos por David Avis y Komei Fukuda en 1991 para problemas de generación de vértices de politopos convexos y celdas de arreglos de hiperplanos . ^{[ 1 ]} Avis y Fukuda los formalizaron de manera más amplia en 1996. ^{[ 2 ]}

Un algoritmo de búsqueda inversa genera los objetos combinatorios en un espacio de estados , un grafo implícito cuyos vértices son los objetos que se van a listar y cuyas aristas representan ciertos "movimientos locales" que conectan pares de objetos, normalmente mediante pequeños cambios en su estructura. Encuentra cada objeto utilizando una búsqueda en profundidad en un árbol de expansión con raíz de este espacio de estados, descrito por la siguiente información: ^{[ 2 ]}

• La raíz del árbol de expansión, uno de los objetos
• Una subrutina para generar el padre de cada objeto en el árbol, con la propiedad de que si se repite suficientes veces eventualmente llegará a la raíz.
• Una subrutina para listar todos los vecinos en el espacio de estados (no todos los cuales pueden ser vecinos en el árbol).

A partir de esta información, es posible encontrar los hijos de cualquier nodo dado en el árbol, invirtiendo los enlaces dados por la subrutina padre: son simplemente los vecinos cuyo padre es el nodo dado. Son estos enlaces invertidos a los nodos hijos los que busca el algoritmo. ^{[ 2 ]}

Una búsqueda clásica en profundidad de este árbol de expansión recorrería el árbol recursivamente, comenzando desde la raíz, en cada nodo listando todos los hijos y realizando una llamada recursiva para cada uno. A diferencia de una búsqueda en profundidad de un grafo con ciclos, no es necesario mantener el conjunto de nodos ya visitados para evitar visitas repetidas; tal repetición no es posible en un árbol. Sin embargo, este algoritmo recursivo aún puede requerir una gran cantidad de memoria para su pila de llamadas , en casos cuando el árbol es muy profundo. En cambio, la búsqueda inversa recorre el árbol de expansión en el mismo orden almacenando solo dos objetos: el objeto actual del recorrido y el objeto recorrido previamente. Inicialmente, el objeto actual se establece en la raíz del árbol y no hay ningún objeto anterior. A partir de esta información, es posible determinar el siguiente paso del recorrido mediante el siguiente análisis de casos: ^{[ 2 ]}

• Si no hay ningún objeto anterior, o si el objeto anterior es el padre del objeto actual, entonces esta es la primera vez que el recorrido llega al objeto actual, por lo que se muestra como resultado de la búsqueda. El siguiente objeto es su primer hijo o, si no tiene hijos, su padre.
• En todos los demás casos, el objeto anterior debe ser hijo del objeto actual. El algoritmo enumera los hijos (es decir, los vecinos en el espacio de estados del objeto actual que tienen al objeto actual como padre) uno a uno hasta llegar a este hijo anterior, y luego da un paso más en esta lista de hijos. Si se encuentra otro hijo de esta manera, este es el siguiente objeto. Si no hay un siguiente hijo y el objeto actual no es la raíz, el siguiente objeto es el padre del objeto actual. En el caso restante, cuando no hay un siguiente hijo y el objeto actual es la raíz, la búsqueda inversa finaliza.

Este algoritmo implica enumerar los vecinos de un objeto una vez por cada paso de la búsqueda. Sin embargo, si hay${\displaystyle N}$objetos a listar, luego se realiza la búsqueda${\displaystyle 2N-1}$pasos, por lo que el número de veces que genera vecinos de objetos está dentro de un factor de dos del número de veces que la búsqueda recursiva en profundidad haría lo mismo. ^{[ 2 ]}

Algunos ejemplos de problemas a los que se ha aplicado la búsqueda inversa incluyen los siguientes problemas de generación combinatoria:

Vértices de politopos convexos simples

Si un${\displaystyle d}$Un politopo convexo de dimensión se define como la intersección de semiplanos , entonces sus vértices pueden describirse como los puntos de intersección de${\displaystyle d}$o más hiperplanos que delimitan los semiplanos; es un politopo simple si ningún vértice es la intersección de más de${\displaystyle d}$de estos hiperplanos. El problema de enumeración de vértices es el problema de enumerar todos estos vértices. Las aristas del politopo conectan pares de vértices que tienen${\displaystyle d-1}$ hyperplanes in common, so the vertices and edges form a state space in which each vertex has ${\displaystyle d}$ neighbors. The simplex algorithm from the theory of linear programming finds a vertex maximizing a given linear function of the coordinates, by walking from vertex to vertex, choosing at each step a vertex with a greater value of the function; there are several standard choices of "pivot rule" that specify more precisely which vertex to choose. Any such pivot rule can be interpreted as defining the parent function of a spanning tree of the polytope, whose root is the optimal vertex. Applying reverse search to this data generates all vertices of the polytope. A similar algorithm can also enumerate all bases of a linear program, without requiring that it defines a polytope that is simple.^[2][3]

Cells of hyperplane arrangements

A hyperplane arrangement decomposes Euclidean space into cells, each described by a "sign vector" that describes whether its points belong to one of the hyperplanes (sign 0), are on one side of the hyperplane (sign +1), or are on the other side (sign −1). The cells form a connected state space under local moves that change a single sign by one unit, and it is possible to check that this operation produces a valid cell by solving a linear programming feasibility problem. A spanning tree can be constructed for any choice of root cell by defining a parent operator that makes the first possible change that would bring the sign vector closer to that of the root. Using reverse search for this state space and parent operator produces an algorithm for listing all cells in polynomial time per cell.^[2][4]

Point-set triangulations

The triangulations of a planar point set are connected by "flip" moves that remove one diagonal from a triangulation and replace it by another. If the Delaunay triangulation is chosen as the root, then every triangulation can be flipped to the Delaunay triangulation by steps in which the triangulation of some subset of four points is replaced by its Delaunay triangulation.^[5][6] Choosing the first Delaunay flip as the parent of each triangulation, and applying local search, produces an algorithm for listing all triangulations in polynomial time per triangulation.^[2]

Connected subgraphs

Los subgrafos conexos y los subgrafos inducidos conexos de un grafo conexo dado forman un espacio de estados cuyos movimientos locales consisten en la adición o eliminación de una arista o un vértice del grafo, respectivamente. Un árbol generador de este espacio de estados se obtiene añadiendo la primera arista o vértice (en algún orden de las aristas o vértices) cuya adición produce otro subgrafo conexo; su raíz es el grafo completo. Al aplicar una búsqueda local a este espacio de estados y al operador padre, se obtiene un algoritmo para listar todos los subgrafos conexos en tiempo polinomial por subgrafo. ^{[ 2 ]}

Otras aplicaciones incluyen algoritmos para generar las siguientes estructuras:

• Poliominos , ^{[ 7 ]} prototiles de polidiamante , ^{[ 8 ]} y moléculas de hidrocarburos polihexagonales (matemáticas) . ^{[ 9 ]}
• Ordenaciones topológicas de grafos acíclicos dirigidos , utilizando un espacio de estados cuyos movimientos locales invierten el orden de dos elementos. ^{[ 2 ]}
• Árboles de expansión de grafos, árboles de expansión sin cruces de conjuntos de puntos planares y, más generalmente, bases de matroides , utilizando un espacio de estados que intercambia una arista por otra. ^{[ 2 ]}
• Recorridos de Euler en grafos. ^{[ 10 ]}
• Los conjuntos independientes máximos de grafos dispersos . ^{[ 11 ]}
• Grafos planares máximos ^{[ 12 ]} y grafos poliédricos . ^{[ 13 ]}
• Grafos mínimamente rígidos sin cruces en un conjunto de puntos dado. ^{[ 14 ]}
• Polígonos circundantes , polígonos que tienen algunos de un conjunto dado de puntos como vértices y rodean al resto, utilizando un espacio de estados que agrega o elimina un vértice del polígono. ^{[ 15 ]}
• Vértices o facetas de la suma de Minkowski de politopos convexos. ^{[ 16 ] [ 17 ]}
• Los vértices (multigrados) de ideales monomiales . ^{[ 18 ]}