ELECTIVA TÉCNICA
JONNATHAN FERNEY PEDROZA
CORPORACION TECNOLOGICA INDUSTRIAL COLOMBIANA
INGENIERIA DE SISTEMAS
III SEMESTRE
JORNADA NOCHE
2021
ELECTIVA TÉCNICA
JONNATHAN FERNEY PEDROZA
Búsquedas Informadas
LIC STEPHANI MUÑOZ AVILA
CORPORACION TECNOLOGICA INDUSTRIAL COLOMBIANA
INGENIERIA DE SISTEMAS
III SEMESTRE
JORNADA NOCHE
2021
Agente Viajero
Es un método que es utilizado cuando existe un problema donde se debe realizar varios viajes a
diferentes lugares una sola vez y se debe llegar al mismo lugar de donde se originó dicho viaje. Es
por ello por lo que los principales objetivos son minimizar distancias, tiempos y costos, es decir,
que al realizar una secuencia entre varios nodos estos pueden ser estaciones, ciudades, puntos de
referencia entre otros.
Una de las áreas en las que se puede observar el problema del agente viajero es en la teoría de
gráficas. En la siguiente grafica se puede observar las tres grandes áreas o enfoques que ha
tomado el problema del Agente Viajero para su estudio, véase el siguiente gráfico
Ejemplo de utilidad en un problema de un viajero
Un viajero tiene que visitar cada una de las cuatro ciudades y lo quiere hacer de tal manera que
visite una sola vez partiendo de la ciudad A y regresando al final del recorrido, viajando el menor
tiempo posible, la siguiente tabla muestra los tiempos entre ciudades (horas):
Formulación
Variables Xij: Horas de viaje desde la ciudad i hasta la ciudad j. Siendo i=A,B,C,D{1,2,3,4} y
j=A,B,C,D{1,2,3,4}
Solución
Para poder darle solución a este problema se realizan cambios en el nombre de las variables se
acomodan de acuerdo a su posición del 1 al 12.
Para la interpretación de resultados regresamos al nombre original de las variables obteniendo lo
siguiente:
X1=X12
X6=X24
X7=X31
X12=X43
Por lo tanto, se dice que el recorrido será de siguiente manera:
Pasa de la ciudad A a la B
Pasa de la ciudad B a la D
Pasa de la ciudad D a la 4
Pasa de la ciudad C a la A terminando donde se inició el recorrido.
El tiempo mínimo usado haciendo este recorrido será de 9 horas.
Alfa-Beta
alfa-beta es un algoritmo de búsqueda que busca reducir el número de nodos que se evalúan
por el algoritmo minimax en su árbol de búsqueda. Se trata de un algoritmo de búsqueda de
confrontación de uso común para la máquina de juego de juegos de dos jugadores (Tic-tac-toe,
Ajedrez, Go, etc.).
Ejemplo de utilidad en un problema de Alfa-Beta
La primera hoja B tiene valor 3. En consecuencia, B, que es un nodo Min tiene un valor máximo de
3. La segunda hoja 12 en B tiene un valor, MIN evitar que este movimiento, por lo que B se
encuentra todavía en la mayoría de 3. La tercera hoja en B tiene un valor 8, por lo que el valor de B
es exactamente 3. Ahora, podemos deducir que el valor de la raíz es por lo menos 3, ya que MAX
tiene una opción de valor 3 en la raíz,
CONCLUSIÓN
Poda alfa-beta es un algoritmo que limita la profundidad de búsqueda en juego no estocástico
donde se conocen las reglas y se dominan las acciones. La compresión de este algoritmo de
búsqueda avanzada lleva a un nivel de compresión alto en cuanto a las matemáticas respectas si
deseas aplicarlo debes saberles.
A*
Es un método de búsqueda heurística desarrollado por Spendley, Hext y Himsworth. Está basado
en la evaluación de la función en los vértices de un simplex regular. En n dimensiones, un
simplex regular es un poliedro compuesto por (n + 1) puntos equidistantes, estos puntos son los
vértices del simplex.
El algoritmo A* es usado para encontrar la ruta más cercana para ir de un lugar a otro (llamados
nodos), es el más usado debido a que es sencillo y rápido.
Ejemplo de utilidad en un problema de A*
El nodo inicial es el nodo (2,4) o el que está de color azul, el nodo final es el nodo (3,2) o nodo rojo,
los nodos de color verde son nodos sólidos y no pueden ser traspasados.
Al empezar el algoritmo tendremos el nodo azul como opción y lo agregamos a la lista abierta,
luego como no es el nodo final, obtenemos sus nodos adyacentes y luego lo dejaremos en la lista
cerrada, calculamos los valores de los nodos de la lista abierta (a menos que ya los hayamos
calculado) y tomamos el de menor valor:
La heurística que se ha usado es la distancia de Manhattan:
H = [Link](nodoActual.X – nodoFinal.X) + [Link](nodoActual.Y – nodoFinal.Y)
Como ejemplo tomamos el cuadrado B (1,4) hasta el nodo final (3,2)
H = (1 – 3) + (4 – 2)
H= 2+2
H=4
Lo que hicimos fue contar los cuadrados que hay para llegar del nodo actual al nodo final.
Ahora, el nodo que tiene el menor valor es C, por lo tanto buscamos sus nodos adyacentes, dando
como resultado el nodo E y F porque los demás son sólidos y el nodo (4,5) aunque es alcanzable
diagonalmente, es inalcanzable porque uno de los nodos cerca es sólido.
Se añade el nodo C a la lista cerrada y los demás nodos a la lista abierta, pero como ya se
encuentran, se verifica que el valor calculado no sea menor, los costos nuevos son de los nodos
son:
Como el costo no es menor que el que tienen en la lista abierta, se descartan y se vuelve a tomar
el menor valor de la lista abierta, lo que da un empate entre B y E, pero si tomamos el nodo E,
volveríamos a descartar los demás nodos, volviendo a tomar el valor B porque el E es enviado a la
lista cerrada.
Si se sigue con el algoritmo va a dar lo siguiente:
HILL CLIMBING
También es conocido como el método de ascenso de colinas. Usa una técnica de mejoramiento
iterativo. Comienza a partir de un punto (punto actual) en el espacio de búsqueda. Si el nuevo
punto es mejor, se transforma en el punto actual, si no, otro punto vecino es seleccionado y
evaluado. El método termina cuando no hay mejorías, o cuando se alcanza un número predefinido
de iteraciones
Ejemplo de utilidad en un problema de HILL CLIMBING
f(nodo)= # de casillas bien colocadas (maximización)
