Cuadro comparativo de IA

Cuadro Comparativo de los tipos de busquedas y sus algoritmos

1. Busqueda Primero es 
el mejor 
La cual trata de expandir el nodo más cercano al objetivo para poder encontrar 
una solución que lo conduzca hacia un estado objetivo, esta búsqueda evalúa 
los nodos mediante una función heurística f(n)=h(n) la cual es un componente 
clave de este tipo de algoritmos. La función
 de evaluación es la encargada de 
devolver los valores de la expansión de los nodos en donde se escoge el nodo 
que posea una mejor evaluación. Un defecto de este tipo de búsqueda es que 
no tiene en cuenta el costo que tendrá n hasta llegar a su objetivo
Algoritmo Asociado
Tipo de Busqueda Definicion Caracteristicas Aplicación Ventajas Desventajas
1.Tratar de expandir el nodo más cercano para conseguir más rápidamente la 
solución.
2.Evalúa los nodos utilizando solo la función heurística.
3.Encuentra la solución sin expandir un nodo que este el camino de solución.
1.Admite costes variables de acciones.
2.Reduce complejidad con buena heurística.
3.Evita visitar demasiados 
caminos inútiles
1.Puede hacernos difundir nodos que no son necesarios
2.Se puede llegar a callejones sin salida,si no se tiene cuidado con los nodos repetidos
3.No es optima y es incompleta
1.Despues de expandir el nodo voy a elegir el mejor nodo hijo es decir el que tenga mejor heuristica
2.Luego va
 empezar su recorrido por el nodo hijo viendo que nodo tiene su mejor heuristica
3. Si al finalizar la ramificacion no encuentra en Nodo (hoja) o Destino aplicara el Backtraking para recorrer otro 
camino.
4.La busqueda Terminara cuando se encuentre el nodo de Inicio y Destino
Es usado en problemas en donde 
las acciones se comportan como si fuesen un 
único camino hacia la solución
Busqueda General en 
Grafos
Se trata de un algoritmo de búsqueda sobre grafos que soluciona el problema 
del camino mínimo (de ahí que también sea conocido como algoritmo de 
caminos mínimos) en grafos de aristas con pesos no negativos
1.Es un algoritmo greddy.
2.Trabaja por etapas, y toma en cada etapa la mejor solución sin considerar 
consecuencias futuras.
3.El óptimo encontrado en una etapa puede modificarse posteriormente si surge una 
solución mejor.
1.Sea V un conjunto de vértices de un grafo.
2.Sea C una matriz de costos de las aristas 
del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v.
3.Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.
4.Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al
 vértice v.
5.Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene 
construido.
6.Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen 
partiendo de un vértice origen al resto de los vértices.
BUSQUEDAS INFORMADAS (HEURISTICAS)
1.Ocupa muy poco espacio.
2.Si hay una solución, la encuentra siendo esta la más óptima.
3.Evita la generación de nodos repetidos.
1.Expande muchos nodos inútiles.
2.Coste constante y no negativo. Usado para la resolución de problemas en general.
Busqueda Sin Informacion Del Dominio
Algoritmo Asociado
     Sea G = (V, A) un grafo conexo, V’ = V un conjunto de vértices, A’ un vector de arcos inicialmente vacío y P un 
vector auxiliar inicialmente vacío:
1.Se introduce el vértice inicial en P y se elimina del conjunto.
2.Mientras V’ no sea vacío repetir los puntos 3
 y 4. En otro caso parar.
3.Se toma el primer elemento de P como vértice activo.
4.Si el vértice activo tiene algún vértice adyacente que se encuentre en V’:
Se toma el de menor índice.
Se inserta en P como último elemento.
Se elimina de V’.
Se inserta en A’ el arco que 
le une con el vértice activo.
Si el vértice activo no tiene adyacentes se elimina de P.
1.La principal ventaja de esta algoritmo radica en el reducido valor de su 
complejidad espacial. 
2.Cuando existen múltiples soluciones posibles la eficiencia del algoritmo 
aumenta.
1.La dificultad estriba en el tiempo requerido. El algoritmo
 puede dedicarse a recorrer un camino 
demasiado largo que no conduzca a ninguna solución. 
2.Si no se guarda constancia de los nodos que forman el camino recorrido se podría caer en ciclos 
y el proceso no acabaría.  
 3.El problema por tanto es determinar cuál debe ser lp.  Si éste
 es inferior a la longitud real del 
camino de la solución, ésta nunca se encontraría, y si es mucho mayor sería ineficiente. Esta es la 
razón por la que  lp  debería llamarse límite de exploración.
Sea G = (V, A) un grafo conexo, V’ = V  un conjunto de vértice, A’un
 vector de arcos inicialmente vacío y P un vector 
auxiliar inicialmente vacío:
1.Se introduce el vértice inicial en P y se elimina del conjunto V’.
2.Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.
3.Se toma el último elemento de P como vértice activo.
4.Si el 
vértice activo tiene algún vértice adyacente que se encuentre en V’:
Se toma el de menor índice.
Se inserta en P como último elemento.
Se elimina de V’.
Se inserta en A’ el arco que le une con el vértice activo.
Si el vértice activo no tiene adyacentes se elimina de P.
Desventajas
Se 
refiere en buscar esta vez no por niveles sino según sea el camino que se aya 
elegido recorrerlo hasta que ya no existan mas nodos al final, es decir en 
expandir un único camino desde la raíz hasta el ultimo en esa rama si ya no 
existen mas nodos retrocede y
 selecciona otro camino a los siguientes nodos 
por descubrir.
1.La búsqueda en profundidad no garantiza que se encuentre la solución si el árbol 
tiene ramas infinitas 
2.La complejidad en espacio es lineal en el tamaño del camino que e se está 
explorando.
Es usado en espacios de estados en donde 
las acciones están limitadas.
Esta técnica su fin es recorrer todos los nodos del mismo nivel que de donde se 
encuentra como todo siempre la posición sera el inicio y como final el 
objetivo buscado
1.Si el problema tiene una solución este procedimiento garantiza el 
encontrarla. 
2.Si hubiera varias soluciones se
 obtiene la de menor coste (la óptima), 
es decir, la que requiere un menor número de pasos (si consideramos un 
coste uniforme de aplicación de los operadores).
1.Si el nivel de profundidad asociado a la solución es significativamente menor que el factor 
de ramificación se expandirían demasiados nodos inútilmente. 
2.Por
 otro lado la principal desventaja de este método es el espacio de almacenamiento 
requerido. Esto lo hace prácticamente inviable para problemas complejos, como suelen ser los del 
mundo real.
Busqueda en 
Profundidad
Tipo de Busqueda Definicion Caracteristicas Aplicación Ventajas
Busqueda En Anchura
1.Si el factor de ramificación de todos los nodos es finito, la
búsqueda 
en anchura encuentra una solución (si existe).
2.Además encuentra el camino con menos arcos.
3.La complejidad en tiempo es exponencial en la longitud del camino: bn, con b el 
factor de ramificación y n la longitud del camino.
4.La complejidad en espacio es también exponencial en la longitud del camino: bn.
Es usado en problemas realmente pequeños, en donde el coste de las acciones es 
el mismo para todas
1.No es óptimo porque no consigue la solución más óptima.
1.Necesitamo una variable denominada K ‐> es el factor  maximo  de ramificacion en ese arbol = la cantidad  mayor 
de hijos  que tenga
 un modo
2. A partir  del origen o estado  incial se escoge para el siguiente nivel los k mejores nodos, que cumplan con la 
condicion de tener un padre que haya sido escogido en el nivel anterior
Algoritmo A*
En esta búsqueda se evalúa el nodo sumando al costo de alcanzar el
 nodo, el 
costo estimado de ir al nodo objetivo, esta estrategia deberá cumplir con el 
requisito de nunca sobreestimar el costo de alcanzar el objetivo.
1.Conseguir buenas soluciones (óptimas).
2.Ganar en eficiencia (reduciendo el árbol de búsqueda).1.Soluciones más cercanas a la raíz.1.La función de evaluación se complica
Es usado
 en donde la heurística es admisible, donde el coste de ir al nodo objetivo 
no sobreestime el coste de alcanzar el nodo objetivo.
1.‐ Establecer el nodo s como origen. Hacer f(s)=0, y f(i)=∞ para todos los nodos i diferentes del nodo s. Iniciar el 
conjunto Q vacío.
2.‐ Calcular el 
valor de f(s) y mover el nodo s al conjunto Q .
3.‐ Seleccionar el nodo i del conjunto Q que presente menor valor de la función f(i) y eliminarlo del conjunto Q.
4.‐ Analizar los nodos vecinos j de i. Para cada enlace (i, j) con coste cij hacer:
4.1.‐Calcular:  f(j)’=g(i)+cij  +h(j)
4.2.‐Si f(j)’<f(j),
4.2.1.‐Actualizar la etiqueta de j y su nuevo valor será: f(j)= g(i)+cij +h(i)
4.2.2.‐Insertar el nodo j en Q
4.3.‐Si f(j)’≥f(j)
4.3.1.‐Dejar la etiqueta de j como está, con su valor f(j)
5.‐ Si Q está vacío el algoritmo se termina. Si no está
 vacío, volver al paso 3.
Busqueda en Haz
Pretende acelerar el proceso de búsqueda reduciendo en cada paso del 
algoritmo el número de nodos generados que van a poder ser expandidos.
1.Parte de K estados generados aleatoriamente
2.Genera los hijos de todos los estados
3.Conserva los K estados con mejor valor 
de la función de evaluación heurística
Es aplicado en algoritmos genéticos en donde cada estado sucesor combina dos 
estados padres.
1.Disminuye la cantidad de nodos a generar.
BUSQUEDA CON ADVERSARIOS
Metodo Minimax
Minimax es un método de decisión para minimizar la pérdida máxima esperada 
en juegos con adversario y con información perfecta.
1.Minimax es un algoritmo recursivo.
2.El funcionamiento de Minimax puede resumirse como elegir mejor movimiento 
para ti mismo suponiendo que tu contrincante escogerá el peor para ti. 
Usado ampliamente 
en juegos en donde se necesita saber cuáles son las posibles 
opciones a elegir en una partida.
El algoritmo tiene la capacidad de aprender de su oponente.
1.Cada estado debe ser visitado dos veces: una vez para encontrar sus hijos, y otra para evaluar el 
valor heurístico.
2.Tiende a ser demasiado 
lento.
3.El factor de ramificación es cada vez más profundo.
Para aplicar el algoritmo se requiere:
1.Generar el árbol entero hasta nodos terminales
2.Aplicar función de utilidad a nodos terminales
3.Propagar hacia arriba para generar nuevos valores de utilidad para todos los nodos
4.Elegir jugada con máximo valor de utilidad
1.La eficacia es 
debido a la forma en como examina los sucesores.
2.La poda no afecta el resultado final.
3.Es más eficiente debido a que usa menos variables.
1.Es posible que no consiga una solución aunque exista. Metodo Poda
Es una técnica de búsqueda que reduce el número de nodos evaluados en un 
árbol de
 juego por el algoritmo Minimax. Se trata de una técnica muy utilizada 
en programas de juegos entre adversarios.
1.Se centrán en los nodos en donde se consiga posiblemente la solución.
2.Se abandonara una solución cuando se compruebe que esta es peor que otras ya 
conocidas.
Esta técnica es usada por un
 gran número de problemas NP‐hard, tales como:
Problema de la mochila.
Programación lineal.
Programación no lineal.
Problema del viajante.
Problema de la asignación cuadrática.
Problema de máxima satisfacibilidad (Versión Inglesa).
Búsqueda del vecino más cercano (Versión Inglesa).
Análisis del ruido falso.