Dfsdfasd

Búsqueda exhaustiva

En esta nueva parte del curso se estudiarán técnicas para la solución de
problemas de búsqueda. Aunque el nombre sugiere una clase de problemas
limitada, conforme se profundice en el tema se verá que esta clase de problemas incluye muchos que inicialmente no parecen ser de búsqueda; he aquí el
primero. Suponga que se quiere a combatir a un adversario a lo largo de mfases (p. ej., asaltos, si fuera boxeo) utilizando en cada una de ellas una de n
posibles armas, tal que está permitido repetir armas. ¿Qué combinación(es)
de armas conduce(n) a la victoria? Con tan poca información no queda otra
que simular combates utilizando todas las combinaciones posibles de armas,
es decir, realizar una búsqueda exhaustiva en el espacio de soluciones, y anotar cuál(es)lleva(n) a una victoria (una solución). En este caso el espacio de
soluciones E es el producto cartesiano Nm , en donde Nn = {1, 2, . . . , n}.
n
Su cardinalidad es |E | = nm (en cada fase se escoge una de entre n posibles armas, y existen m fases), número que crece bastante rápido conforme
aumenta el número de fases.

1.

Búsqueda exhaustiva con retroceso

Una técnica computacionalmenteeficiente para realizar búsquedas y evitar rehacer trabajo es el retroceso . La técnica consiste en resolver el problema en fases , haciendo llamados a una subrutina en cada fase (usualmente
a la misma rutina, es decir, usando recursión). Cuando la subrutina devuelve
1

el control, se dice que retrocedió, y dependiendo del resultado (puede ser
que se haya encontrado una solución satisfactoria) seprocede a explorar
otras alternativas o no, conservando el trabajo realizado en fases previas. A
continuación se muestra el uso de esta técnica para la solución del problema
del combate.
Problema del combate
La aplicación de la técnica de retroceso en este caso consiste en registrar
el estado del combatiente al finalizar cada fase. De esta forma, si se pierde
la batalla en la fase i, sepuede recuperar el estado en el que estaba el
combatiente al finalizar la fase i − 1, y volver a pelear la fase i pero con un
arma distinta, sin empezar de nuevo el combate desde la fase 1.
Algoritmo

El algoritmo siguiente muestra cómo utilizar la técnica de retroceso para
resolver el problema del combate. El algoritmo toma como entrada el número
de fase i y devuelve un booleano que indica sise ganó el combate o no.
La colección de armas α y el número de fases m se asumen conocidos (son
variables globales). La solución (el vector de índices que contiene la secuencia
de armas a utilizar) se guarda en el arreglo (global) σ .1
Sí/No←Fase(i)
1
si i > m
2
devuelva No
3
para j = 1 . . . n
4
σ [i] = j
5
pelear con arma α[j ]
6
si ganó
7
devuelva Sí
1

Si el lenguaje deprogramación utilizado o las buenas costumbres de programación no permiten el
uso de variables globales, y pueden ser pasados como parámetro y devuelto como argumento de salida.

2

8
9
10
11
12

si perdió
siguiente j
si Fase(i + 1)
devuelva Sí
devuelva No

Duración

Para analizar la duración de este algoritmo es conveniente ver la fase i
como un problema de tamaño m − i + 1,pues queda esa cantidad de fases
por resolver, y para resolverlo se deben resolver en el peor caso n problemas
una unidad más pequeños, es decir, de tamaño m − i. Además, en cada
llamado se realiza trabajo proporcional a n debido al ciclo para y trabajo
constante debido a lo que está fuera del ciclo (líneas 1, 2 y 12). Por lo tanto,
se puede formular el tiempo de ejecución de este algoritmorecursivamente
de la siguiente manera:
T (m) =
=
=
=
=
.
.
.

nT (m − 1) + nc1 + c0
n [nT (m − 2) + nc1 + c0 ] + c0
n2 T (m − 2) + n2 c1 + (n + 1)c0
n2 [nT (m − 3) + nc1 + c0 ] + (n + 1)c0
n3 T (m − 3) + n3 c1 + (n2 + n + 1)c0

= nk T (m − k ) + nk c1 + (nk−1 + nk−2 + · · · + 1)c0
y cuando k = m:
T (m) = nm c + nm c1 + (nm−1 + nm−2 + · · · + 1)c
nm − 1
m
m
= n c + n c1 +
c...