Método de análisis de medios y metas de reducción de problemas

Solo disponible en BuenasTareas
  • Páginas : 7 (1623 palabras )
  • Descarga(s) : 0
  • Publicado : 28 de abril de 2011
Leer documento completo
Vista previa del texto
Tema:

METODOS DE:

• ANALISIS DE MEDIOS Y METAS

• REDUCCIÓN DE PROBLEMAS

Materia:

Introducción a la IA.

EL MÉTODO DE ANÁLISIS DE MEDIOS Y METAS

El estado de un sistema es una descripción que basta para determinar el futuro. En un espacio de
estados, cada nodo representa un estado, y cada enlace una posible transición de un paso de un
estado a otro:

Unespacio de estados es una representación, o sea una red semántica en la que los nodos representan estados; los enlaces representan transiciones entre estados.

En consecuencia un espacio de estados es miembro de la familia de redes semánticas de representaciones que se introdujo.

En el contexto de la resolución de problemas, los estados corresponden al lugar en que usted está o debería estar en elproceso de resolver un problema. De ahí que el estado actual sea el lugar en donde usted se encuentra; el estado meta, el lugar al que desea llegar; y el problema consiste en hallar una sucesión de transiciones que conduzca del estado inicial al estado meta.
En lo que resta de esta sección, usted aprenderá acerca del análisis de medios y metas, un método estándar para seleccionar transiciones.También podrá conocer una forma popular de instrumentar el análisis de medios y metas mediante una tabla sencilla.

A. Sin información

• búsqueda en profundidad y a lo ancho

Algoritmo Primero en Profundidad (DEPTH-FIRST)
1. Si el estado inicial es el objetivo, salir y retornar éxito.
2. Si no, haga lo siguiente hasta que se obtenga señal de éxito o fracaso:
a. Genere unsucesor E del estado inicial. Si no hay más sucesores, retorne con
señal de fracaso.
b. Llame recursivamente al algoritmo, esta vez con E como el estado inicial.
c. Si la señal es éxito, retorne, de otra manera, continúe en este lazo

Algoritmo Primero a lo Ancho (BREATH-FIRST)
1. Crear una variable NODE_LIST y ponerla al estado inicial.
2. Hasta que se encuentre el objetivo ohasta que NODE_LIST esté vacía haga lo siguiente:
a. Remover el primer elemento de NODE_LIST, y llamarlo E. Si NODE_LIST estuvo
vacía, salir.
b. Para cada forma en que cada regla puede ajustarse al estado descrito en E, haga
lo siguiente:
i. Aplicar la regla para generar un nuevo estado.
ii. Si el nuevo estado es un estado objetivo, salir yretornar este estado.
iii. Si no, añada el nuevo estado al final de NODE_LIST.

B. Con información

• Hill climbing, best-first,beam search y A*
Ascenso a Colina (Hill Climbing)

Es una variante del algoritmo de búsqueda de generación y prueba. Del procedimiento de prueba existe una realimentación que ayuda al generador a decidirse por cual dirección debe moverse enel espacio de búsqueda. En estos procesos se abandona la búsqueda si no existe un estado alternativo razonable al que se pueda mover.

Los algoritmos de ascenso a colina son típicamente locales, ya que deciden qué hacer, mirando únicamente a las consecuencias inmediatas de sus opciones. Puede que nunca lleguen a encontrar una solución, si son atrapados en estados que no son el objetivo, desdedonde no se puede hallar mejores estados, por ejemplo:

1. Un máximo local, que es un estado mejor que sus vecinos
pero no es mejor que otros que están algo más alejados.

2. Una meseta, es un espacio de búsqueda en el que todo un
conjunto de estados vecinos tienen igual valor.

3. Un risco, que es un tipo especial de máximo local, imposible de
atravesarcon movimientos simples.

Hay algunas formas que pueden ayudar a solventar estos problemas, aunque no existe garantía:

1. Para evitar máximos locales, regresar a un estado anterior y
explorar en una dirección diferente.

2. Para casos de mesetas, dar un salto grande en alguna
dirección y tratar de encontrar una nueva sección del espacio de
estado....
tracking img