Algoritmos - Búsqueda Completa

Búsqueda Completa

Andrés Ricardo Pérez Rojas

Algoritmos

Noviembre 13, 2019

Definición

Es un método general que puede ser utilizado para resolver casi cualquier problema, al estar basado en generar todas las posibilidades utilizando fuerza bruta, y a partir de estas calcular la respuesta.

Generar Subconjuntos

Para generar todos los posibles subconjuntos existen dos formas generales:

• Recursión

• Representación Binaria (Bitmask)

Ambas parten del hecho de que cada objeto en el conjunto original puede estar o no estar en cada subconjunto.

Generar Subconjuntos: Recursión

Para cada elemento k explora sus dos opciones. Cada vez que llega al estado con k igual a n, se obtiene un subconjunto nuevo en el vector subset.

Generar Subconjuntos: Bitmask

Dado que cada elemento tiene dos posibilidades, su presencia o no en un subconjunto puede ser representada por un bit. Usando un entero como máscara podemos recorrer todos los posibles subconjuntos de manera más sencilla.

Generar Permutaciones

Para probar todos los posibles órdenes o permutaciones de un conjunto de datos, también existen dos formas generales:

• Recursión

• Iterar por cada permutación

Generar Permutaciones: Recursión

En cada paso se pasa por cada elemento y se revisa si ya está insertado en la permutación actual. Se exploran todas las posibles opciones de colocar los que estén disponibles como siguiente elemento.

Generar Permutaciones: Next Permutation

Partiendo de la permutación lexicográficamente menor, se puede usar la función next_permutation para iterar una por una orden.

Backtracking

Un algoritmo con backtracking empieza a construir la solución según las restricciones del problema para explorar las diferentes posibilidades. Cuando llega al final de un posible caso, evalúa si es una solución válida (si solo se requiere saber si existe puede parar la ejecución al encontrar una), y vuelve al estado inmediatamente anterior para probar otra alternativa.

Podando la Búsqueda

Al hacer una “poda” sobre el árbol de búsqueda se puede optimizar el proceso significativamente. Esto se hace al darle “inteligencia” a la búsqueda para que no siga bajando cuando ya es imposible encontrar una respuesta correcta, o cuando ciertos casos no son necesarios para calcular la respuesta al ser equivalentes a otros.

Meet in the Middle

Esta técnica se basa en separar el espacio de búsqueda en dos partes de aproximadamente el mismo tamaño,  para luego realizar la búsqueda en en cada mitad y unir las respuestas para obtener la respuesta completa. Se utiliza la técnica repetidamente hasta llegar a un caso suficientemente pequeño para calcular la respuesta de manera eficiente. Se puede llegar a reducir la complejidad de un factor de 2n a uno de 2n/2.

Bibliografía

• [1]A. Laaksonen, Competitive Programmer’s Handbook. 2018, pp. 47 - 56.

• [2]"Power Set", Mathsisfun.com. [Online]. Available: https://www.mathsisfun.com/sets/power-set.html. [Accessed: 11- Nov- 2019].

• [3]"C# Sharp Exercises: Generate all possible permutations of an array - w3resource", w3resource. [Online]. Available: https://www.w3resource.com/csharp-exercises/recursion/csharp-recursion-exercise-11.php. [Accessed: 11- Nov- 2019].

• [4]"Backtracking Introduction - javatpoint", www.javatpoint.com. [Online]. Available: https://www.javatpoint.com/backtracking-introduction. [Accessed: 11- Nov- 2019].

• [5]"File:Tic-tac-toe-full-game-tree-x-rational.jpg - Wikimedia Commons", Commons.wikimedia.org. [Online]. Available: https://commons.wikimedia.org/wiki/File:Tic-tac-toe-full-game-tree-x-rational.jpg. [Accessed: 11- Nov- 2019].

• [6]"Divide-and-conquer approach for finding the closest pair of points", Code Review Stack Exchange. [Online]. Available: https://codereview.stackexchange.com/questions/141976/divide-and-conquer-approach-for-finding-the-closest-pair-of-points. [Accessed: 11- Nov- 2019].

...