ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Heurística admisible : que es, definición y significado, descargar videos y fotos.

videos internet

salud  ıllı Heurística admisible : que es, definición y significado, descargar videos y fotos.  


Una heurística aceptable es utilizada para apreciar el costo de lograr el estado objetivo en un algoritmo de busca informada. Una heurística va a ser aceptable para determinado inconveniente de busca cuando el costo estimado sea siempre y en toda circunstancia menor o bien igual que el costo mínimo de lograr el estado objetivo. El algoritmo de busca emplea la heurística para localizar una estimación del camino inmejorable hasta el propósito desde el nodo actual. Por poner un ejemplo, uno de los algoritmos de busca más populares es el A* (en inglés A-Star Search). En este la función de evaluación para nundefined, donde nundefined es el nodo actual, es así:


f(n)=g(n)+h(n)undefined


donde:



  • f(n)undefined es la función de evaluación, una estimación del camino de costo mínimo que va desde el principio hasta la meta y pasa por nundefined .
  • g(n)undefined es el costo del camino desde el principio hasta nundefined .
  • h(n)undefined es el costo estimado desde el nodo actual hasta la meta.

h(n)undefined es calculado utilizando una función heurística. Con una heurística no aceptable, el algoritmo A* podría pasar por alto la solución perfecta a lo largo de la busca debido a una sobreestimación de f(n)undefined. Las heurísticas aceptables son por su naturaleza optimistas, por el hecho de que creen que el costo de solventar el inconveniente es menor que el que verdaderamente es. Como g(n)undefined es el costo preciso de lograr nundefined, tenemos como consecuencia inmediata que f(n)undefined jamás sobreestima el costo auténtico de la solución por medio de nundefined. De estar h(n)undefined definida por una heurística aceptable, el algoritmo de busca A* va a devolver una solución perfecta.


Por ejemplo, si se quiere solucionar el quince-rompecabezas (o bien juego del quince) en la menor cantidad de pasos posible utilizando A*, es preciso emplear una heurística aceptable. Hay una larga historia de semejantes heurísticas para el quince-rompecabezas, acá tenemos 2 de las más generalmente usadas:


Queda claro que la Distancia de Hamming es aceptable, puesto que el total de movimientos para ordenar las fichas apropiadamente es cuando menos el número de fichas que no están en su sitio (si cada ficha no está en su situación original habrá de ser movida por lo menos una vez). La Distancia Manhattan asimismo va a ser una heurística aceptable pues cada ficha va a ser movida el menos la cantidad de pasos entre ella misma y su situación original. Considere el próximo rompecabezas:


la distribución de las distancias Manhattan para cada ficha quedaría así:


La distancia total de Manhattan para el rompecabezas quedaría:


h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36undefined


Una heurística aceptable puede derivar de una versión simplificada del inconveniente, o bien por información desde un patrón de base de datos que almacene la solución precisa de un inconveniente, o bien utilizando aprendizaje inductivo. Por servirnos de un ejemplo, del quince-rompecabezas visto previamente, podemos delimitar 3 inconvenientes más simples: La regla del juego original es "Una ficha se puede desplazar desde la casilla A hasta la casilla B si A es lindante a B y B está vacía".


Se pueden producir 3 inconvenientes quitando una o bien las dos condiciones:



  1. Una ficha se puede desplazar desde la casilla A hasta la casilla B si A es lindante a B.
  2. Una ficha se puede desplazar desde la casilla A hasta la casilla B si B está en blanco.
  3. Una ficha se puede desplazar desde la casilla A hasta la casilla B.

De 1) podemos derivar la Distancia Manhattan, de dos) podemos derivar otra heurística famosa como La heurística de Gaschnig y de tres) podemos derivar la Distancia de Hamming.


La idea tras el patrón de base de datos es guardar los costos de las soluciones precisas de cada posible instancia de un sub-inconveniente, en nuestro ejemplo las instancias de sub-inconvenientes podrían ser ocho casillas y el espacio en blanco o bien siete casilla y el espacio en blanco. Por servirnos de un ejemplo (1-dos-tres-cuatro-cinco-seis-siete-ocho) y (nueve-diez-once-doce-trece-catorce-quince). Si las casillas escogidas no se repiten en 2 sub-inconvenientes (o bien dicho por norma general, no hay solapamiento en 2 sub-inconvenientes), podemos crear una heurística aceptable que sea la suma de los dos costos guardados en la base de datos. Utilizando esta heurística se resolvería el quince-rompecabezas en unos pocos milisegundos, el número de nodos generados se reduce en diez equiparado con como cuando se utiliza la distancia Manhattan.


Si se tiene de una heurística aceptable, la que mejor funcione será la de mayor valor, es decir, la que mejor aproxime la solución inmejorable real sin exceder su valor. De ahí si tenemos múltiples heurísticas aceptables y no sabemos cuál escoger, podemos crear una nueva que sea el máximo de todas las demás.


Mientras que todas y cada una de las heurísticas consistentes son aceptable, no todas y cada una de las heurísticas aceptables son consistentes. Una heurísticah(n)undefined es consistente si, para todo nodo nundefined y todo sucesor n'undefined de nundefined generado por cualquier acción A, el costo estimado de lograr el propósito desde nundefined no es mayor que el costo de conseguir n'undefined más el costo estimado de conseguir el propósito desde n'undefined:


h(n)=c(n,A,n')+h(n')undefined


Para inconvenientes de busca en árbol, si una heurística aceptable es utilizada, el algoritmo A* jamás va a devolver un nodo objetivo subóptimo.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Heurística admisible : que es, definición y significado, descargar videos y fotos.

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas