Busqueda De Soluciones

UNIVERSIDAD NACIONAL DE SAN AGUSTIN FACULTAD DE PRODUCCION Y SERVICIOS ESCUELA PROFESIONAL DE INGENIERIA INDUSTRIAL


CURSO: SISTEMAS INTELIGENTES
DOCENTE: ING. JULIO RAMOS QUISPE

INTEGRANTES:
* BARRIOS ZEBALLOS, JORGE LUIS F.
* CENTENOMEJIA, GILMAR MAURICIO
* LUNA MAYTA , JOSE
* NIFLA CORNEJO, RAMIRO
* NIFLA MORALES, MAXWELL
* SUASACA BELIZARIO, SILVANA
*SARDON MAMANI YENY

AREQUIPA 2012

INDICE

INDICE

1. INTRODUCCION
2. MARCO TEORICO
2.1.- BUSQUEDA EN PROFUNDIDAD
2.2.- BÚSQUEDA EN ANCHURA
2.3.- FUNCIÓN HEURÍSTICA
2.3.1.- ASCENSO DE COLINA
2.3.2.- PRIMERO EL MEJOR (BEST-FIRST)

2.4.- ALGORITMO PODA ALFA-BETA
3.
4. APLICACIONES

3.1.- EJEMPLO DE BUSQUEDA EN PROFUNDIDAD
3.2.- EJEMPLO DE BÚSQUEDA EN ANCHURA3.3.- EJEMPLO DE FUNCIÓN HEURÍSTICA
3.3.1.- EJEMPLO DE ASCENSO DE COLINA
3.3.2.- EJEMPLO DE PRIMERO EL MEJOR (BEST-FIRST)
3.4.- EJEMPLO DE ALGORITMO PODA ALFA-BETA

5. CONCLUSIONES
4.1.- BUSQUEDA EN PROFUNDIDAD
4.2.- BÚSQUEDA EN ANCHURA
4.3.- FUNCIÓN HEURÍSTICA
4.4.- ALGORITMO PODA ALFA-BETA

6. BIBLIOGRAFIA

1.- INTRODUCCION

El siguiente trabajo de investigación, tiene comopropósito mostrar la implementación de juegos basados en computadoras, aplicando el campo de la Inteligencia Artificial,

"Nuestro cerebro no posee un acceso directo al mundo exterior. Solamente
podemos operar sobre una representación interna suya la cual se corresponde
con una colección de estructuras de símbolos. Dichas estructuras pueden tomar
la forma de un patrón físico cualquiera, porejemplo un vector de interruptores
eléctricos dentro de un ordenador, o un conjunto de neuronas activadas en un
cerebro biológico. Un sistema inteligente (cerebro u ordenador) puede operar
sobre las estructuras con el objetivo de transformarlas en otra construcción. El
pensamiento consiste en la extensión, o desarrollo, de estas estructuras,
descomponiéndolas y reformándolas, destruyendo algunasy creando nuevas.
La inteligencia entonces no constituye nada más que la habilidad de procesar
estructuras de símbolos. Existe en un entorno diferente al hardware que le da
soporte, lo trasciende y puede tomar diferentes formas físicas."

2.-MARCO TEORICO
2.1.- BUSQUEDA EN PROFUNDIDAD

Una Búsqueda en profundidad (en inglés DFS o DepthFirstSearch) es un algoritmo que permite recorrertodos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.Análogamente existe el algoritmo de búsqueda en anchura (BFS o BreadthFirstSearch)

2.2.- BÚSQUEDA EN ANCHURA
Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todoslos vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.
Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística.
Si las aristas tienen pesosnegativos aplicaremos el algoritmo de Bellman-Ford en alguna de sus dos versiones.
Se comienza en el vértice inicial (vértice con índice 1) y se marca como vértice activo, a  diferencia con la BEP ahora se visitan en orden creciente de índice todos los vecinos del vértice activo antes de pasar al siguiente. Hasta que todos los vértices hayan sido visitados, en cada paso se van visitando en orden...