Búsqueda Ciega Inteligencia Artificial


¿cuanto tiempo puede tardar un computador en construir el grafo?

Los grafos pueden representarse estructuras de datos distintas. Los algoritmos que se aplican sobre ellos adoptan tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso (cuando tiene muchas aristas) o disperso (muy pocas aristas). 

formalizar un problema pasos: 

Estado inicial: es como se describe el problema.
Estado final: es la solución a la que se quiere llegar.
Estados posibles: son todos los posibles nodos que se pueden crear, o todos los posibles estados que puede tomar antes de encontrar las soluciones del problema.
Los operadores:Son los pasos que toma para cambiar de un estado a otro estado, las condiciones de cómo se debe ejecutar el algoritmo para poder encontrar la solución, su estructura es de tipo if- then.
formalizar los siguientes problemas como un problema de búsqueda

1) 3P Y 3CB 
1 balsa puede pasar a 2 personas
no pueden quedar en ninguna de las orillas mas políticos que ciudadanos porque los políticos lo roban.

 2) se tienen dos caballos blancos y dos caballos negros que lo solo se pueden mover en L acomodarlos de acuerdo al estado fanal.



1) Estado inicial:                                 Estado final:       
                     
      

   Estado de espacio:  

                                                                                                                                                                                                           Operador: subir político, bajar político, subir ciudadano de bien, bajar ciudadano de bien, orilla 1, orilla 2, capacidad balsa.

2) Estado inicial:                                 Estado final:   
                          
   Estado de espacio:













Operador: caballo negro derecha, caballo negro izquierda, caballo negro arriba, caballo negro abajo, caballo blanco derecha, caballo blanco izquierda, caballo blanco arriba, caballo blanco abajo.

Estados posibles: 9! = 362880.

Comentarios

Publicar un comentario

Entradas más populares de este blog

Proyecto Perceptron Simple (Código C++)

Imagen
INTRODUCCIÓN En 1936 Alan Turing estudio el cerebro como una forma de ver el mundo de la computación. Sin embargo, los primeros teóricos que concibieron los fundamentos de la computación neuronal fueron Warren McCulloch un neurofisiología y Walter Pitts un matemático quienes en 1943 lanzaron una teoría acerca de la forma de trabajar de las neuronas. Ellos modelaron una red neuronal simple mediante circuitos eléctricos. Años más tarde en 1949 Donald Hebb escribió un importante libro en el que explicaba los procesos del aprendizaje desde un punto de vista psicológico, desarrollando una regla de como el aprendizaje ocurría. Su idea fue que el aprendizaje ocurría cuando ciertos cambios en una neurona eran activados. Los trabajos de Hebb formaron las bases de la Teoría de las Redes Neuronales. Luego en 1957 Frank Rosenblatt desarrolla el Perceptrón, Esta es la red neuronal más antigua utilizándose hoy en día para aplicación como reconocedor de patrones. Este modelo era capaz de ge...
Leer más

IDA* Algoritmo Inteligencia Artificial

Imagen
El algoritmo de Búsqueda en Profundidad Iterativa, es un algoritmo ciego que aplica reiteradamente la búsqueda en profundidad. En cada aplicación incrementa en una unidad la profundidad de la búsqueda.  El algoritmo A*, se usa en problemas de optimización y es admisibilidad, esto es encuentra soluciones óptimas, si usa una heurística admisible.  El algoritmo IDA* Fase básica: Como el A* ordena los nodos según el valor de f(n) = g(n) + h(n), pero al expandir un nodo excluye como sucesores a aquellos nodos cuyo coste supere una cota prefijada. Si no alcanza solución. Fase de reiteración: Si todos los candidatos a sucesores han superado la cota, toma como nueva cota el coste del nodo menos transgresor y relanza de nuevo el algoritmo. IDA* es completo y optimo, pero al ser iterativo en profundidad, necesita menos memoria. complejidad espacial: O(b*d)=f*/minimo valor costes. d="profundidad" de lamejor solucion.
Leer más

Proyecto Minimax-Scout (Código C++)

Imagen
INTRODUCCIÓN La teoría de juegos plantea que debe haber una forma racional de jugar a cualquier «juego» (o de negociar en un conflicto), especialmente en el caso de haber muchas situaciones engañosas y segundas intenciones; así, por ejemplo, la anticipación mutua de las intenciones del contrario, que sucede en juegos como el ajedrez o el póquer, da lugar a cadenas de razonamiento teóricamente infinitas, las cuales pueden también trasladarse al ámbito de resolución de conflictos reales y complejos. En síntesis, y tal como se comentó, los individuos, al interactuar en un conflicto, obtendrán resultados que de algún modo son totalmente dependientes de tal interacción. Análisis Para el siguiente proyecto utilizaremos dos tipos de algoritmos por un lado Minimax y por el otro el algoritmo de Scout los cuales nos brindaran las mejores soluciones. El algoritmo de minimax consiste en la elección del mejor movimiento para el computador, suponiendo que el contrincante escogerá ...
Leer más