Algoritmos para juegos | Tema 4: Divide y vencerás Por Alejandro Vargas Lugo Obra de creación propia bajo licencia Creative Commons BY-NC-SA 4.0 Internacional https://creativecommons.org/licenses/by-nc-sa/4.0/deed.es
IntroducciónMáxima eficienciaBúsqueda binariaBúsqueda de la cifra exactaBúsqueda de la cifra inmediatamente por debajo de la cifra objetivoBúsqueda de la cifra inmediatamente por encima de la cifra objetivo
En el mundo de las ciencias de la computación, hay ciertos problemas que, si bien pueden resolverse en tiempo polinómico (forman parte del conjunto de problemas P), en ocasiones pueden llegar a ser tan grandes que requieran sin embargo una cantidad considerable de tiempo para resolverlos. Aunque a primera vista pudiese parecer que existe poco margen de mejora para algoritmos con una complejidad O(N²), o incluso O(N), te sorprenderás viendo lo sencilo que puede ser hacerlos aún más eficientes.
Para ilustrarlo vamos a poner de ejemplo un juego bien conocido: el de adivinar un número en un intervalo. Una persona piensa un número (normalmente del 1 al 100) y tú debes averiguar cuál es. Por cada respuesta incorrecta que das, la otra persona te indica si te has quedado por debajo ("¡más!") o si te has pasado ("¡menos!"), para ayudarte.
Por supuesto, la forma conceptualmente más sencilla de llegar al número correcto es simplemente irlos nombrando uno a uno (1, 2, 3, 4, 5, ...). En algún momento alcanzarás la cifra correcta, y la complejidad sigue siendo relativamente buena: O(N) (es decir, en el peor caso, dado un intervalo de 1 a N, tendrías que hacer N intentos). Pero como tú no eres una máquina, te habrás dado cuenta de que hay una estrategia mucho más sensata: mencionar el número en el centro del intervalo, y de esta manera, te descartas la mitad entera de los números sólo en la primera iteración. Repites el proceso con la mitad restante y te quitas otra mitad de golpe. Y cuando menos te lo esperas, has llegado a la cifra correcta en apenas una fracción de intentos. Estas estrategias se conocen con el nombre de Divide y vencerás, y de hecho, este algoritmo que acabo de describir es uno de los más representativos:
La búsqueda binaria consiste en un algoritmo de búsqueda que permite encontrar un valor en una lista ordenada, comparándolo en cada iteración con el valor situado exactamente en la mitad de la lista (la mediana), descartando la mitad en la cual es imposible que se encuentre el objetivo.
La mejora de eficiencia con respecto a una búsqueda estándar iterativa (ir leyendo los elementos uno a uno por orden) es considerable. En este último caso la complejidad es de O(N), pero aplicando la búsqueda binaria, esta se reduce a O(logN).
Según cómo queramos buscar el elemento existen diferentes variantes de la búsqueda binaria. El caso de querer encontrar el valor exacto, o más comunmente, el caso de querer hallar el valor inmediatamente por encima o por debajo de un valor objetivo.
x
def binsearch(values, target, left, right): if left > right: return -1 mid = (left + right) // 2 if values[mid] == target: return mid elif values[mid] < target: return binsearch(values, target, mid + 1, right) else: return binsearch(values, target, left, mid - 1)Applet interactivo: ¿Aún tienes dudas? ¿Quieres buscar un elemento exacto en tu propia lista? ¡Prueba el applet interactivo de la búsqueda binaria!
x
def binsearch(values, target, left, right): if left > right: return right
mid = (left + right) // 2
if values[mid] <= target: return binsearch_high_rec(values, target, mid + 1, right) else: return binsearch_high_rec(values, target, left, mid - 1)xxxxxxxxxxdef binsearch(values, target, left, right):
if left > right: return left
mid = (left + right) // 2
if values[mid] >= target: return binsearch_low_rec(values, target, left, mid - 1) else: return binsearch_low_rec(values, target, mid + 1, right)