EcuRed - Contribuciones del colaborador [es]

Tableta electrónica

2012-09-18T16:25:29Z

Yrosario06: Página creada con '{{Ficha de computadora |Nombre = Tableta Electrónica |Logo = |Logo_tamaño = |Foto = Tableta_Electronica.JPG |Foto_tamaño = |Pie = |Tipo = |Desarrollador = |Comercializ...'

{{Ficha de computadora
|Nombre = Tableta Electrónica
|Logo =
|Logo_tamaño =
|Foto = Tableta_Electronica.JPG
|Foto_tamaño =
|Pie =
|Tipo =
|Desarrollador =
|Comercializado |Descatalogado =
|Arquitectura =
|Procesador =
|Rendimiento =
|Memoria =
|Media =
|Audio =
|Gráfica =
|Pantalla =
|Energía =
|Entrada =
|Conectividad =
|SO =
|Precio =
|Sitioweb =

|Ubicación =
|Instalación =
|Procesadores =
|Extensión =
|top500 =
|top500_mejor =
|top500_listas =
}}<div align="justify">

''' Tableta Electrónica ''' es un dispositivo ligero que ha tratado de integrar las mejores funcionalidades de un [[teléfono móvil]] y una [[computadora]] como son: acceder a toda la información contenida en la [[red]], al igual que podemos utilizarla para leer un [[e-book]], ver videos, películas escuchar música,ver fotografías o imágenes digitales, también son excelentes para capturar datos en texto, tomar video o fotografía incluso capturar audio.
== Historia==
La primera en llegar fue el [[iPad]], lanzada por [[Apple]] en el año 2010 con la promesa de revolucionar el mercado del ocio a través de un dispositivo con múltiples prestaciones alcanzando el éxito comercial al proveer por fin de la interfaz adecuada.
En la actualidad prácticamente todos los fabricantes de equipos electrónicos han incursionado en la producción de Tabletas electrónicas (por ejemplo,[[Samsung]], [[Blackberry]], [[Sony]], [[Toshiba]], [[Acer]], [[Hewlett Packard]] y [[Microsoft]] entre otros), lo cual ha generado que el mercado se vea inundado de una inmensa cantidad de Tabletas con diferentes tamaños, aplicaciones, precio y sistemas operativos.
== Características==
Integran procesadores que consumen menos energía aunque incorporan menos memoria. Existe modelos disponibles en el mercado que incluyen ranura para micro SD, incrementando así las posibilidades de almacenamiento. Por se un dispositovo de formato panorámico destacan por su ligereza, versatilidad y reducidas dimensiones (entre 7’ y 10’) lo que facilita enormemente su portabilidad.
Se hallan a medio camino entre un teléfono inteligente y un portátil. Están más enfocados al acceso de aplicaciones (apps) que a la creación de contenidos. Otra característica destacable de estos dispositivos es su naturaleza táctil lo que permite prescindir de teclado físico o ratón. Aunque algunos modelos nuevos como el nuevo HTC Flyer incorporan puntero o soporte teclado (modelos iPad, Samsung Galaxy Tab y Topaz de HP) el resto de los dispositivos no necesita más que el leve toque por parte del usuario para operar con las distintas aplicaciones. Son herramientas intuitivas, rápidas y que no precisan de aprendizaje instrumental por parte del usuario. Por primera vez es la tecnología la que se adapta al usuario y no al revés.
==Prestaciones de una tableta electronica==
*Permite satisfacer las las necesidades multimedia ya que permite: reproducir música, omar y reproducir fotos (marco digital), visionar y grabar vídeos(en algunos modelos incluso ofrece la posibilidad HDMI para poder ver vídeos en conexión con televisor o monitor), Sincronización en línea de contenidos multimedia
* Proporcionar opciones de acceso a Internet a través de WI-FI (conectividad a redes inalámbricas) o a través de soporte a redes 3G: navegación web, búsqueda, navegación por voz, GPS, estación meteorológica, envío y recepción de correos electrónicos, llamadas por Internet sin coste, acceso a RSS y foros, sincronización de cuentas tipo Google, seguimiento de redes sociales.
* Gestor de agenda, eventos y contactos.
* Soporte para tomar notas o realizar gráficos y dibujos.
* Gestor de documentos sencillos a través de aplicaciones que emulan a procesadores de texto, bases de datos y hojas de cálculo.
* Soporte de lectura a través de aplicaciones tipo e-reader (libros electrónicos) o la posibilidad de leer prensa y revistas en formato digital
* Recurso educativo por su versatilidad, portabilidad y funcionalidad..

</div>
== Fuentes ==
* http://www.informaticamoderna.com
* http://www.ehowenespanol.com
* http://recursostic.educacion.es
* http://todotabletaselectronicas.blogspot.com
* http://geekpro.es
[[Categoría:Computadoras_tabletas]]

Robot Deechee

2012-07-07T14:43:04Z

Yrosario06: Página creada con '{{Definición |nombre=Robot Deechee |imagen=Robot_DeeChee.png |tamaño= |concepto=Robot de aspecto infantil programado para desarrollar la capacidad del lenguaje de una ...'

{{Definición

|nombre=Robot Deechee

|imagen=Robot_DeeChee.png

|tamaño=

|concepto=[[Robot]] de aspecto infantil programado para desarrollar la capacidad del lenguaje de una forma más natural y rápida.

}}

<div align="justify">

'''Robot Deechee'''.

[[Robot]] que ha aprendido a hablar como un bebé humano, el aprendizaje de los nombres de las formas simples y colores.

== Creador ==

Ha sido creado por investigadores de la Universidad de [[Hertfordshire]], en Inglaterra. Deechee ha sido programado para reconocer todas las sílabas que existen en el idioma inglés, y con la capacidad de unir esas sílabas en respuesta a estímulos.

==Características==

El resultado es que, con cada nueva sesión, Deechee consigue aprender nuevas palabras uniéndo sílabas a partir de la repetición de vocablos oídos a sus improvisados profesores humanos, sigue el mismo proceso que un bebé: empieza balbuceando y finalmente acaba hablando.

== Objetivo==

El objetivo del experimento es doble. Por una parte se persigue comprender mejor como se forma el lenguaje en los niños muy pequeños que pasan de balbucear sílabas inconexas a unir esos sonidos en palabras coherentes.

El segundo objetivo no es otro que diseñar nuevas técnicas que permitan a sistemas de inteligencia artificial el desarrollar la capacidad del lenguaje de una forma más natural y rápida.

== Fuentes ==

*http://www.newscientist.com

*http://actualidad.rt.com

*http://www.unomasenlafamilia.com

[[Category:Inteligencia_Artificial]][[Category:Ciencias_informáticas]][[Category:Robótica]]

Técnicas de Representación de Conocimiento

2012-04-19T14:47:46Z

Yrosario06:

{{Ficha Software
|nombre= Técnicas de Representación de Conocimiento
|familia=
|imagen= Técnicas_de_Representación_de_Conocimiento.jpg
|tamaño=
|descripción= Representa gráficamente la organización de un contenido, de tal manera que facilite su retención
|imagen2=
|tamaño2=
|descripción2=
|creador=
|desarrollador=
|diseñador=
|modelo de desarrollo=
|fecha de creación=
|lanzamiento inicial=
|versiones=
|última versión estable=
|núcleo=
|tipo de núcleo=
|plataformas soportadas=
|género=
|sistemas operativos=
|idioma=
|licencia=
|premios=
|web=
}}
<div align="justify">
'''Técnicas para la Representación del Conocimiento'''.Analiza cómo pensar formalmente - cómo usar un sistema de símbolos para representar un dominio del discurso (aquello de lo que se puede
hablar), junto con funciones que permitan inferir (realizar un razonamiento formal) sobre los objetos.
==Historia==
La representación del conocimiento como tal, es una materia en la que se lleva trabajando desde hace varias décadas, desde mucho antes de que surgiera la [[web semántica]]. Surgió en el ámbito de la [[Inteligencia Artificial]] al tratar de crear representaciones de conocimiento que pudieran ser utilizadas por mecanismos que simulasen el razonamiento humano.
==Técnicas==
Existen diferentes técnicas de representación del conocimiento que se han utilizado, y sobre las que se han sustentado los lenguajes de representación del conocimiento. Una técnica no es mejor que las demás, sino que cada una de ellas ha sido aplicada con más éxito que otras en determinados ámbitos, por lo que disponen de características que las hacen más apropiadas para determinados problemas.
* Tripletas Objeto-Atributo-Valor: se utilizan para representar hechos acerca de objetos y sus atributos, especificando el valor de un atributo para un determinado objeto. Por ejemplo, para representar que el coche es rojo, se tendría una tripleta Coche-Color-Rojo. Típicamente estas tripletas se representan en forma de grafos, utilizando una elipse para el objeto, un cuadrado para el valor, y una flecha o arco dirigido entre ambos elementos representando el atributo.
* Uncertain Facts o Hechos Inciertos: las tripletas O-A-V indican que un objeto tiene un valor asociado a un atributo de forma completa y con toda la certeza, es decir, un coche es rojo o no lo es. No permiten asignar graduaciones de certeza en estas asignaciones. Ejemplo, existen situaciones en las que se puede necesitar representar que un determinado objeto que posee un atributo con una determinada certeza, lo que se suele denominar "certainty factor". Mediante esta técnica sería posible representar sentencias como “El coche es bastante potente”, asignando una factor de certeza de 0.7 al atributo potente
* Fuzzy Facts o Hechos Difusos: representa conocimiento impreciso o ambiguo. Ejemplo, la expresión “Juan es viejo”, en comparación con “Juan es joven” o “Juan es de mediana edad”, puede no ser sencilla de representar con otras técnicas, ya que la edad es algo gradual, no se pasa de ser joven un día a ser de mediana edad al siguiente. Esta ténica lo que permite es definir funciones de membresía que asignan un valor entre 0 y 1 a cada valor. Así por ejemplo, la función de membresía de edad, asignaría un 1 a joven si la persona tiene 10 años, pero este valor iría decreciendo conforme aumentase la edad hasta llegar a 0, pero teniendo en cuenta que antes de eso se habría ido incrementando el valor de membresía de “mediana edad” e incluso de “viejo”, pudiendo haber edades como los 45, en los que se podría decir que con una persona es joven con un 0.2, vieja con un 0.2 y de mediana edad con un 0.6.
* Rules: esta técnica representa el conocimiento presentando unas premisas o condiciones y las conclusiones o acciones que de ellas se derivan. Se suelen representar de la forma IF – THEN -. Las premisas se colocan a continuación del IF en forma normalmente de tripletas O-A-V y utilizando operadores booleanos, mientras que las conclusiones definirían nuevos hechos o realizarían acciones. Por ejemplo, podríamos tener la siguiente regla para representar que si hay que ir a trabajar y está lloviendo hay que coger el paraguas: IF “es hora de ir a trabajar” AND “está lloviendo” THEN “tengo que coger el paraguas”.
* Redes Semánticas o Mapas Conceptuales: se basa en la utilización de grafos que representan conceptos, objetos y relaciones entre ellos. Estas relaciones pueden ser de cualquier tipo, pero predominan las relaciones de tipo “kind-of”, “part-of” y “is-a”, que permiten representar estructuras jerárquicas de conocimiento. Están relacionadas también con las tripletas O-A-V, ya que en las redes semánticas se suelen incluir también estas estructuras para dar información sobre los atributos de los diferentes objetos.
* Frames o Marcos: es una técnica de representación muy similar a la utilizada en la programación orientada a objetos. Consta de class frames, similares a las clases, que representan conjuntos de objetos con características similares. A partir de ellas se crean las instance frames que representan elementos concretos de esa clase. Por ejemplo, podríamos tener el marco de clase “Persona” y la instancia “Juan”. Cada frame dispone por otra parte de una serie de slots equivalentes a los atributos y propiedades en orientación a objetos. Existe también la posibilidad, a diferencia de en las redes semánticas, de definir lo que se llaman facets sobre estos slots, de forma que se les aporte comportamiento procedural. Por ejemplo, sobre un slot edad podríamos añadir el facet “if-changed”, para comprobar el valor introducido.
== Véase también ==
*[[Inteligencia Artificial]]
*[[Lenguajes de Representación del Conocimiento]]
== Fuente ==
*Model Driven Architecture and Ontology Development
*www.representaciondelconocimiento.wordpress.com
*www.eslomas.com
*Association for the Advancement of Artificial Intelligence
[[Category:Inteligencia_Artificial]]

Técnicas de Representación de Conocimiento

2012-04-19T14:44:26Z

Yrosario06: Página creada con '{{Ficha Software |nombre= Técnicas de Representación de Conocimiento |familia= |imagen= Técnicas_de_Representación_de_Conocimiento.jpg |tamaño= |descripción= Representa gr...'

{{Ficha Software
|nombre= Técnicas de Representación de Conocimiento
|familia=
|imagen= Técnicas_de_Representación_de_Conocimiento.jpg
|tamaño=
|descripción= Representa gráficamente la organización de un contenido, de tal manera que facilite su retención
|imagen2=
|tamaño2=
|descripción2=
|creador=
|desarrollador=
|diseñador=
|modelo de desarrollo=
|fecha de creación=
|lanzamiento inicial=
|versiones=
|última versión estable=
|núcleo=
|tipo de núcleo=
|plataformas soportadas=
|género=
|sistemas operativos=
|idioma=
|licencia=
|premios=
|web=
}}
<div align="justify">
'''Técnicas para la Representación del Conocimiento'''.La representación del conocimiento como tal, es una materia en la que se lleva trabajando desde hace varias décadas, desde mucho antes de que surgiera la [[web semántica]]. Surgió en el ámbito de la [[Inteligencia Artificial]] al tratar de crear representaciones de conocimiento que pudieran ser utilizadas por mecanismos que simulasen el razonamiento humano. Analiza cómo pensar formalmente - cómo usar un sistema de símbolos para representar un dominio del discurso (aquello de lo que se puede hablar), junto con funciones que permitan inferir (realizar un razonamiento formal) sobre los objetos.

==Técnicas de Representación del Conocimiento==

Existen diferentes técnicas de representación del conocimiento que se han utilizado, y sobre las que se han sustentado los lenguajes de representación del conocimiento. Una técnica no es mejor que las demás, sino que cada una de ellas ha sido aplicada con más éxito que otras en determinados ámbitos, por lo que disponen de características que las hacen más apropiadas para determinados problemas.
* Tripletas Objeto-Atributo-Valor: se utilizan para representar hechos acerca de objetos y sus atributos, especificando el valor de un atributo para un determinado objeto. Por ejemplo, para representar que el coche es rojo, se tendría una tripleta Coche-Color-Rojo. Típicamente estas tripletas se representan en forma de grafos, utilizando una elipse para el objeto, un cuadrado para el valor, y una flecha o arco dirigido entre ambos elementos representando el atributo.
* Uncertain Facts o Hechos Inciertos: las tripletas O-A-V indican que un objeto tiene un valor asociado a un atributo de forma completa y con toda la certeza, es decir, un coche es rojo o no lo es. No permiten asignar graduaciones de certeza en estas asignaciones. Ejemplo, existen situaciones en las que se puede necesitar representar que un determinado objeto que posee un atributo con una determinada certeza, lo que se suele denominar "certainty factor". Mediante esta técnica sería posible representar sentencias como “El coche es bastante potente”, asignando una factor de certeza de 0.7 al atributo potente
* Fuzzy Facts o Hechos Difusos: representa conocimiento impreciso o ambiguo. Ejemplo, la expresión “Juan es viejo”, en comparación con “Juan es joven” o “Juan es de mediana edad”, puede no ser sencilla de representar con otras técnicas, ya que la edad es algo gradual, no se pasa de ser joven un día a ser de mediana edad al siguiente. Esta ténica lo que permite es definir funciones de membresía que asignan un valor entre 0 y 1 a cada valor. Así por ejemplo, la función de membresía de edad, asignaría un 1 a joven si la persona tiene 10 años, pero este valor iría decreciendo conforme aumentase la edad hasta llegar a 0, pero teniendo en cuenta que antes de eso se habría ido incrementando el valor de membresía de “mediana edad” e incluso de “viejo”, pudiendo haber edades como los 45, en los que se podría decir que con una persona es joven con un 0.2, vieja con un 0.2 y de mediana edad con un 0.6.
* Rules: esta técnica representa el conocimiento presentando unas premisas o condiciones y las conclusiones o acciones que de ellas se derivan. Se suelen representar de la forma IF – THEN -. Las premisas se colocan a continuación del IF en forma normalmente de tripletas O-A-V y utilizando operadores booleanos, mientras que las conclusiones definirían nuevos hechos o realizarían acciones. Por ejemplo, podríamos tener la siguiente regla para representar que si hay que ir a trabajar y está lloviendo hay que coger el paraguas: IF “es hora de ir a trabajar” AND “está lloviendo” THEN “tengo que coger el paraguas”.
* Redes Semánticas o Mapas Conceptuales: se basa en la utilización de grafos que representan conceptos, objetos y relaciones entre ellos. Estas relaciones pueden ser de cualquier tipo, pero predominan las relaciones de tipo “kind-of”, “part-of” y “is-a”, que permiten representar estructuras jerárquicas de conocimiento. Están relacionadas también con las tripletas O-A-V, ya que en las redes semánticas se suelen incluir también estas estructuras para dar información sobre los atributos de los diferentes objetos.
* Frames o Marcos: es una técnica de representación muy similar a la utilizada en la programación orientada a objetos. Consta de class frames, similares a las clases, que representan conjuntos de objetos con características similares. A partir de ellas se crean las instance frames que representan elementos concretos de esa clase. Por ejemplo, podríamos tener el marco de clase “Persona” y la instancia “Juan”. Cada frame dispone por otra parte de una serie de slots equivalentes a los atributos y propiedades en orientación a objetos. Existe también la posibilidad, a diferencia de en las redes semánticas, de definir lo que se llaman facets sobre estos slots, de forma que se les aporte comportamiento procedural. Por ejemplo, sobre un slot edad podríamos añadir el facet “if-changed”, para comprobar el valor introducido.

== Véase también ==

*[[Inteligencia Artificial]]
*[[Lenguajes de Representación del Conocimiento]]

== Fuente ==
*Model Driven Architecture and Ontology Development
*www.representaciondelconocimiento.wordpress.com
*www.eslomas.com
*Association for the Advancement of Artificial Intelligence
[[Category:Inteligencia_Artificial]]

Analista de sistemas

2012-03-27T17:12:01Z

Yrosario06: Página creada con '{{Definición |nombre= Analista de Sistemas |imagen=Analista_de_Sistemas.jpeg |tamaño= |concepto= Analiza los sistemas informáticos, con el fin de automatizarlos. }} <div...'

{{Definición
|nombre= Analista de Sistemas
|imagen=Analista_de_Sistemas.jpeg
|tamaño=
|concepto= Analiza los sistemas [[informático]]s, con el fin de automatizarlos.
}}
<div align="justify">
'''Analista de Sistemas'''. El analista tiene como cometido analizar un problema y describirlo con el propósito de ser solucionado mediante un [[sistema de información]]. Se vale de la información de entrada, los procesos modificadores y la información de salida, para así definir los procesos intermedios y poder entender con claridad a la organización.
==Funciones==
* Tiene que delimitar el análisis para ver lo que se quiere hacer inicialmente y después darle al usuario nuevas opciones de uso.
* Se encarga de idear y desarrollar nuevos sistemas o nuevas formas para aplicar los recursos existentes a operaciones adicionales.
* Es capaz de crear nuevos sistemas, ya sea de [[hardware]] y de [[software]].
==Características==
Las cualidades que se esperan de un analista son esencialmente la capacidad de abstracción y de análisis. Los conocimientos que requiere son aquellos relacionados con las técnicas de análisis de sistemas de información:
*Conocimiento del paradigma tradicional de la ingeniería del software y del tradicional ciclo de vida del software en cascada.
*Modelado funcional: Diagrama de flujo de datos, diagrama de estado, etc.
*Modelado de datos y sus técnicas: Diagrama entidad-relación, modelo relacional, etc.
*Conocimiento de la tecnología: arquitectura de software, bases de datos, etc.
==Roles==
Los tres roles principales del analista de sistemas son:
*El de consultor.
*Experto en soporte técnico
*Agente de cambio.
El Analistas de Sistemas debe mantenerse a la par de los últimos avances en cuanto a las metodologías y tendencias dentro del incesante mundo del manejo de la [[Información]]. Conforme pasa el tiempo el perfil del analista de sistemas irá incorporando nuevas posibilidades y deberes dentro de las organizaciones.

==Fuentes==
* KENDALL&KENDALL, Kenneth y Julie. (1997) Análisis y Diseño de Sistemas.
* www.monografias.com
* es.wikipedia.org

[[Category: Software]][[Category: Informática]]

El deseado de todas las gentes

2012-03-23T19:30:58Z

Yrosario06: Página creada con '{{Ficha Libro |nombre= El Deseado de Todas las Gentes |nombre original= |portada=El_Deseado_de_Todas_las Gentes.jpeg‎ |tamaño= |descripción= |autor(es)= [[Ellen Gould Ha...'

{{Ficha Libro
|nombre= El Deseado de Todas las Gentes
|nombre original=
|portada=El_Deseado_de_Todas_las Gentes.jpeg‎
|tamaño=
|descripción=
|autor(es)= [[Ellen Gould Harmon de White]] (Elena G de White).
|editorial=
|coleccion=
|genero=
|imprenta=
|edicion=
|diseño=
|Composición y emplane=
|primera edicion=
|ejemplares=
|isbn=
|segunda edicion=
|ejemplares2=
|isbn2=
|tercera edicion=
|ejemplares3=
|isbn3=
|pais=
|distribuidor(es)=
|premios=
|web=
|notas=
}}
<div align="justify">
'''El Deseado de Todas las Gentes'''. En esta hora de confusión, donde surgen de continuo nuevos mitos sobre todo lo humano y lo divino, conocer al verdadero [[Jesús]] se ha vuelto realmente difícil. Sin embargo, en este libro ya centenario, su autora ha sabido presentar al Jesús real, tan cercano, que todo lector bienintencionado verá surgir en cada una de sus páginas al [[Cristo]] auténtico: el único que en lugar de polémicas nos ofrece certezas, en lugar de confusión nos proporciona luz, y en lugar de incertidumbre la segura esperanza de la vida eterna. Por eso infinidad de lectores considera que este libro es, de todas las actuales, la mejor y más inspiradora biografía de Cristo.
== Sinopsis==
En el corazón de todos los seres humanos, sin distinción de raza o posición social, hay un indecible anhelo de algo que ahora no poseen. Este anhelo es implantado en la misma constitución del hombre por un [[Dios]] misericordioso, para que el hombre no se sienta satisfecho con su presente condición, sea mala o buena. Dios desea que el ser humano busque lo mejor, y lo halle en el bien eterno de su alma.
En vano procuran los hombres satisfacer este deseo con los placeres, las riquezas, la comodidad, la fama, o el poder. Los que tratan de hacerlo descubren que estas cosas hartan los sentidos, pero dejan el alma tan vacía como antes.
Es el propósito de este libro presentar a [[Jesucristo]] como Aquel en quien puede satisfacerse todo anhelo. Se han escrito muchos libros titulados la [[“La Vida de Cristo”]], libros excelentes, grandes acopios de información, elaborados ensayos sobre cronología, historia, costumbres, y acontecimientos contemporáneos, con abundante enseñanza y muchas vislumbres de la vida multiforme de [[Jesús de Nazaret]]. Sin embrago, no se ha dicho de ella ni aun la mitad.
Rogamos que la bendición del [[Altísimo]] acompañe esta obra, y que el [[Espíritu Santo]] haga de las palabras de este libro palabras de vida para muchas almas cuyos anhelos y deseos no están aun satisfechos.
==Contenido==
*Dios con nosotros/11
*El pueblo elegido/19
*El cumplimiento del tiempo/23
*Os ha nacido un Salvador/29
*La dedicación/35
*Su estrella hemos visto/43
*La niñez de Cristo/51
*La visita de Pascua/59
*Días de conflicto/67
*La vos que clamaba en el desierto/75
*El bautismo/87
*La tentación/93
*La victoria/105
*Hemos hallado al Mesías/111
*En las bodas de Caná/123
*En su templo/133
*Nicodemo/145
*A él conviene crecer/155
*Junto al pozo de Jacob/161
*Si no viereis señales y milagros/173
*Betesda y el Senedrín/177
*Encarcelamiento y muerte de Juan191
*El reino de Dios está cerca/203
*¿No es este el hijo del carpintero?/209
*El llamamiento a orillas del mar/217
*En Capernúm/223
*Puedes limpiarme/233
*Leví Mateo/243
*El sábado/253
*La ordenación de los doce/261
*El Sermón del Monte/269
*El centurión/285
*¿Quiénes son mis hermanos?/291
*La invitación/299
*Calla, enmudece/305
*El toque de fé/315
*Los primero evangelistas/321
*Venid, reposad un poco/331
*Dadles vosotros de comer/337
*Una noche sobre el lago/345
*La crisis Galilea/353
*La tradición/365
*Barreras quebrantadas/371
*La verdadera señal/377
*Previsiones de la cruz/385
*La transfiguración/395
*Nada os será imposible/401
*¿Quién es el mayor?/407
*La Fiesta de las Cabañas/419
*En medio de trampas y peligros/427
*La luz de la vida/437
*El Divino Pastor/451
*El último viaje desde Galilea/459
*El buen samaritano/469
*Sin manifestación exterior/477
*Dejad los niños venir a mí/483
*Una cosa te falta/489
*Lázaro, ven fuera/495
*Conspiraciones sacerdotales/507
*La ley del nuevo reino/513
*Zaqueo/519
*La fiesta en casa de Simón/525
*Tu rey viene/537
*Un pueblo condenado547
*Cristo purifica de nuevo el templo/555
*Controversias/567
*Ayes sobre los fariseos/577
*En el atrio exterior/589
*En el Monte de Olivos/597
*Estos mis hermanos pequeñitos/607
*Un siervo de siervos/613
*Haced en memoria de mí/623
*No se turbe nuestro corazón/633
*Getsemaní/651
*Ante Anás y Caifás/661
*Judas/677
*En el tribunal de Pilato/685
*El Calvario/703
*Consumado es/719
*En la tumba de José/727
*El Señor ha resucitado/739
*¿Por qué lloras?/747
*El viaje a Emaús/753
*Paz a vosotros/759
*De nuevo a orillas del mar/765
*Id, y haced discípulos a todas las naciones/773
*A mi Padre y a vuestro Padre/785

==Datos del Autor (a) ==

[[Ellen Gould Harmon de White]] nació en Gorham, Maine, Estados Unidos el 26 de noviembre de 1827 en la familia de Roberto y Eunice Harmon. Se hizo adventista, recibió mediante Dios 2000 visiones y sueňos.
== Fuente ==
Ellen Gould Harmon de White. El Deseado de Todas las Gentes.
[[Category: Libros]]

Archivo:El Deseado de Todas las Gentes.jpeg

2012-02-01T15:58:36Z

Yrosario06:

== Sumario ==

== Estado de copyright: ==

== Fuente: ==

Noche Buena

2012-01-27T14:32:40Z

Yrosario06: Página creada con '{{Definición |nombre=La Noche Buena |imagen= La_Noche_Buena.jpeg |tamaño= |concepto= La Noche Buena es una fiesta cristiana importante donde se reunen familiares y amigos. S...'

{{Definición
|nombre=La Noche Buena
|imagen= La_Noche_Buena.jpeg
|tamaño=
|concepto= La Noche Buena es una fiesta cristiana importante donde se reunen familiares y amigos. Se celebra mediante una cena íntima entre pocas personas, o una enorme fiesta familiar.
}}
<div align="justify">
'''La Noche Buena''' se celebra la noche del día 24 de diciembre, víspera del día de [[Navidad]] (25 de diciembre). Es la celebración cristiana del nacimiento de [[Jesús]], y las costumbres varían de unos a otros países pero es bastante común: una reunión familiar para cenar y sobre todo en los países protestantes intercambiarse regalos. Se considera ya como una fiesta de carácter cultural, ya que numerosas familias ateas también lo celebran. Sólo los testigos de Jehová son la excepción, ya que no la celebran por considerarla de carácter pagano.
==Historia==
Como los [[evangelios]] no mencionan fechas, no es seguro que Jesús naciera el 25 de diciembre. De hecho, el día de Navidad no fue oficialmente reconocido hasta el año 345, cuando por influencia de [[San Juan Crisóstomo]] y [[San Gregorio Nacianzeno]] se proclamó el 25 de diciembre como fecha de la Natividad del niño Jesús.
La Iglesia añadió posteriormente en la [[Edad Media]] el festejo del nacimiento a sus costumbres. En esta época, los banquetes eran el punto fuerte de las celebraciones, de la misma forma se mantiene hoy en día.
===En la actualidad===
Aparte del origen cristiano, esta fiesta ha ido mezclando su carácter religioso con la tradición de convivencia familiar, debido en gran medida a la popularidad de esta celebración y a la mercadotecnia.
Es desde el siglo XIX cuando la Navidad empieza a afianzarse con el carácter que tiene hoy día, pues en ese siglo se popularizó la costumbre del intercambio de regalos; se creó a [[Santa Claus]] y regalar tarjetas de Navidad. Costumbres que con el tiempo la mercadotecnia (en especial la norteamericana) aprovecharía para expandir por el mundo dándole un carácter distinto al religioso, y con temas que poco o nada tienen que ver con la tradicional celebración navideña.
==Celebración en distintos países==
En [[México]] se acostumbra presentar pastorelas, que son obras teatrales en las cuales se representa la historia del nacimiento de Jesús, algunas de las cuales les añaden toques cómicos, por ejemplo acerca de la situación política del momento. También se celebran tradicionales posadas, en las cuales se realiza la procesión de los peregrinos María y José cantando letanías, se reza el rosario y posteriormente se rompen las piñatas y se ameniza una fiesta para las que se elaboran ponche, buñuelos y tamales; se entregan aguinaldos rellenos de colaciones y frutas; la fiesta se prolonga hasta muy entrada la noche.

En [[Venezuela]], [[Colombia]], [[Ecuador]], [[Bolivia]] y [[Perú]], la costumbre es preparar desde días antes el Nacimiento o representación en figurillas del pesebre de Belén, con san José, María, los Reyes Magos, animalitos, pastores, plantitas, luces de colores, etc. También se arma un árbol navideño decorado con bolas, guirnaldas, luces de colores, etc., a cuyos pies se colocan los regalos que serán intercambiados. El 24 de diciembre se hace una cena familiar con pavo de Nochebuena, puré de manzana, ensalada, chocolate caliente y champán. Las familias católicas van a la Misa del Gallo (a las 23:00 h., generalmente). A la medianoche se hace "nacer" al Niño Jesús, se cantan villancicos y las personas se obsequian regalos. En las calles se queman fuegos artificiales, todo es un ambiente de algarabía. Al día siguiente, 25, las familias se visitan en las casas y se comparte.

En [[Puerto Rico]] las familias y amigos se reúnen para celebrar, cantar parrandas y compartir comidas tradicionales como arroz con gandules, lechón asado y pasteles. Las fiestas a veces siguen hasta la madrugada. En Navidad la gente comúnmente descansa la trasnochada de Nochebuena. A la medianoche los católicos celebran la Misa del Gallo. Las personas van a la iglesia, los niños se visten de pastores y de figuras alegóricas al Nacimiento: la Virgen María, san José, el Niñito Jesús, los Tres Reyes Magos, etc.

En la [[República Dominicana]] es costumbre que los hijos viajen a casa de sus padres y abuelos, donde, reunidos, cenan el tradicional pollo horneado y el puerco en puya (cerdo empalado y asado), ensalada rusa y moro de guandúes con coco, acompañado con lerenes, pasteles en hojas y frutas como manzanas, uvas, peras y nueces, además de pastelón de plátano maduro y lasaña; toda la cena se acompaña de vinos, dulces navideños y cerveza. Después de la reunión salen de casa en casa para compartir y juntarse con las viejas amistades compartiendo regalos y villancicos; todo como parte de la Nochebuena.

En [[Venezuela]] se acostumbra realizar las hallacas el 23 o 24 de diciembre para realizar la tradicional cena de Nochebuena, la cual se compone de hallacas, pan de jamón, pavo o pernil de cochino, jamón "planchado", vino o ponche crema; la mesa se adorna con quesos variados, avellanas, nueces, turrones, galletas (y golosinas variadas), partes es llamada Flor de Navidad.

En [[Cuba]] desde tempranas horas comienzan los preparativos para la cena. Los hombres se encargan del puerco asado mientras las mujeres se entretienen en hacer el arroz, ensalada fresca con tomate, lechuga, cebolla y la vianda (yuca salcochada o ñame). La cena además de la bebida, se acompaña con diferentes dulces.
==Fuente==
*http://www.blog-navidad.com.ar/navidad/historia-de-la-navidad-noche-buena-25-de-diciembre.htm
*http://www.euroresidentes.com/navidad/fiestas/fiestas_noche_buena.htm
[[Category:Tradición]] [[Category:Religión]]

Archivo:La Noche Buena.jpeg

2012-01-26T21:57:53Z

Yrosario06:

== Sumario ==

== Estado de copyright: ==

== Fuente: ==

Búsqueda de caminos

2011-12-05T15:01:32Z

Yrosario06:

{{Definición
|nombre=Búsqueda de caminos
|imagen=Arboles_Busqueda.JPG
|tamaño=
|concepto=Es la forma en que una entidad en movimiento encuentra un camino alrededor de un obstáculo.
}}
<div align="justify">
'''Búsqueda de caminos'''. Los algoritmos de búsqueda de caminos son usados para encontrar una ruta de navegación entre un punto de inicio y otro objetivo. Esta ruta es generalmente un pequeño subconjunto del mundo.

== Breve reseña histórica ==
Con el gran avance que ha tenido el conocimiento del hombre a través del devenir de los años hay momentos que marcan pautas en el desarrollo de la [[Inteligencia Artificial]], fue en la década del 50 donde se utilizó este término y logró captar la atención de muchos para su posterior evolución. La Inteligencia Artificial atiende una rama muy importante y ésta es la búsqueda de caminos.
Las raíces de los algoritmos de búsqueda de caminos hay que asociarlos a la constante evolución de los [[videojuegos]] ya que es una de las aplicaciones prácticas más interesantes en este entorno, son algoritmos por los cuales nuestro objetivo es capaz de eludir los obstáculos y llegar de un punto A a un punto B.
Es a partir de 1959 donde se empieza a buscar variantes para la problemática de la búsqueda de caminos en video-juegos, este proceso ha sido verdaderamente evolutivo ya que se comenzó con algoritmos como Dijkstra, también llamado algoritmo de caminos mínimos luego siguió el algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) éste fue introducido por primera vez en el año 1977 cuando Slate y Atkin presentaron un programa de ajedrez.
Con la constante optimización de los algoritmos de búsqueda aparece el algoritmo de búsqueda de caminos A*, éste fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
En Cuba comienza a lograrse un avance en este sentido, los video-juegos y simuladores son un campo reciente y por tanto, conllevan una simulación inteligente mucho más real y necesitan algoritmos más fuertes y de un nivel superior.

=== En entornos virtuales===
Una de las problemáticas más vistas en el mundo de los juegos es cómo encontrar el camino mínimo entre dos puntos, este estudio ha comenzado desde los métodos de búsqueda heurística tradicionales que en la mayoría de los casos son incapaces de resolver problemas donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido hasta los métodos de búsqueda heurística en tiempo real.
Existen algoritmos capaces de solucionar el problema de búsqueda de caminos de manera eficiente, mediante algoritmos de búsqueda heurística en tiempo real. Se presentan varios algoritmos que mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por etapa de planificación

== Aplicaciones de los algoritmos de búsqueda==
La investigación de algoritmos tanto exactos como heurísticos para resolver problemas de optimización tiene una vigencia inusualmente importante en estos días, de esta forma, actualmente es acuciante la necesidad de algoritmos muy eficientes que puedan dar respuesta en tiempo real a problemas del usuario o del sistema, y que permitan trabajar con los nuevos sistemas operativos y máquinas.
En el mundo de los video-juegos existen muchas aplicaciones para los algoritmos de búsqueda de caminos. Como todos sabemos una de las formas más comunes en las que se aplican estos algoritmos es en los juegos de estrategia y de rol, donde les decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de uno de estos algoritmos.
Los algoritmos de búsqueda de caminos tienen otras tantas aplicaciones muy útiles para el mundo actual, por ejemplo, algo que tiene mucho éxito en nuestros días son los GPS que poseen los carros de alta tecnología de hoy en día que se utilizan para ayudar al conductor a hallar caminos y sugerir los atajos o caminos más cortos. Esto resulta ser de gran utilidad para el turista que se encuentre en una cuidad desconocida para él.
En el mundo de la medicina también existen aplicaciones para estos algoritmos, los grandes programas hechos para realizar cirugías a pacientes están pensados para hallar el camino más corto y seguro considerando todos los factores como flujos sanguíneos, obstáculos y otros, para llegar a algún lugar decidido previamente por el cirujano dada una entrada. Parte importante de esta técnica está en la definición de la distancia heurística que debe recorrer.

== Conceptos para entender la búsqueda en árboles y grafos==
Para entender a cabalidad todo lo relacionado con los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda, por ejemplo, en problemas de este tipo se utiliza mucho el término búsqueda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

=== ¿Qué es búsqueda?===
Método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente.
En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

== Estructuras de datos para la búsqueda de camino==
En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

== Clasificación de algoritmos==

Según la búsqueda los algoritmos se pueden clasificar en dos clases:

=== Los métodos off-line===
Este método sigue el siguiente esquema, primero calculan el plan o ruta de mínimo coste de un problema mediante la búsqueda en el espacio de estados y luego ejecutan el plan realizando las acciones o secuencia de operaciones en el entorno. Este esquema, a menudo considerado de forma implícita, supone que ejecutar la solución en el mundo real es un proceso directo y no presenta ninguna dificultad, o sea, primero se realiza una búsqueda completa en el espacio de estados y luego se ejecuta una secuencia de acciones u operaciones en el entorno. En la siguiente figura se muestra su funcionamiento.
Un ejemplo típico de aplicación de los métodos off-line es la búsqueda de rutas. La búsqueda de rutas consiste en encontrar una ruta en un grafo desde el nodo inicial hasta el nodo objetivo.

=== Los métodos on-line===
En cambio, los métodos on-line intercalan planificación (mediante búsqueda local) y ejecución del plan mientras resuelven un problema. Debido a la propiedad on-line, los métodos tienen una gran flexibilidad para operar en entornos desconocidos y dinámicos. Además, no requieren conocer a-priori todo el espacio de estados, pueden adaptarse a objetos cambiantes y operar en entornos no determinados. Este modo de operación denominado on-line da lugar a los algoritmos de búsqueda en tiempo real. En la siguiente figura se representa el modo de operar de la búsqueda on-line.

== Criterios para evaluar las estrategias de búsqueda==
Cada algoritmo de búsqueda de caminos tiene una serie de características que lo identifican los cuales son:
* Completitud.
* Complejidad en tiempo.
* Complejidad en espacio.
* Optimización.

== Análisis de algoritmos ==
=== Depth-First o búsqueda en profundidad (LIFO) ===
Esta búsqueda se centra en expandir un único camino desde la raíz. Siempre se expande el nodo más profundo en la frontera actual. En el caso de llegar a un “callejón sin salida” se retrocede hasta el nodo más cercano (siguiendo al nodo padre) donde se puede tomar una rama alternativa para poder seguir avanzando.
Se puede implementar, mediante el Algoritmo General, considerando la lista, como una pila (cuyas operaciones funcionan en forma LIFO). De esta manera el siguiente nodo a expandir siempre será el último que se haya colocado en la pila de ese nivel, garantizando esto que la expansión vaya aumentando en la profundidad de los nodos.
Es común aplicar esta estrategia mediante un algoritmo recursivo que recorra el árbol en Pre-Orden. Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos en cada nodo. De aquí surge otro importante algoritmo, “el backtracking”

=== Breadth-First search (búsqueda a lo ancho)===
La búsqueda en anchura (BFS o 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 todos los 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.
Este algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente, este algoritmo tiene como ventaja que, al expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.
Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables y que además requiere de mucha memoria.
Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante. Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.
La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

=== Búsqueda bidireccional===
En la búsqueda bidireccional se llevan a la vez dos búsquedas, una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que los recorridos ascendente y descendente puedan encontrarse en algún momento. (Tener en cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsqueda bidireccional). Por lo demás este método no tiene ninguna dificultad, naturalmente, se podría realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial en profundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro.
Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

===Búsqueda de profundidad limitada===
Para evitar caer en caminos de profundidad muy grande, a la mayoría de los algoritmos que usan depth-first se les impone un límite de profundidad máxima. Por tanto es similar a la estrategia de Primero en Profundidad, pero se trata de eliminar el problema de que se puedan generar árboles “ilimitados”.
Para ello se establece un límite L a la profundidad del árbol. Todo nodo cuya profundidad sea L, no es expandido (se considera sin sucesores). El problema que puede pasar es si escogemos un valor de L menor que la profundidad del objetivo, en cuyo caso no llegaríamos a la solución. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo.

=== Algoritmo DFID (primero en profundidad con profundidad iterativa)===
El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) fue introducido por primera vez cuando Slate y Atkin presentaron un programa de ajedrez.
El algoritmo combina la estrategia de Primero en Profundidad con la de Profundidad Limitada, comenzando con límite igual a 0, aumentándolo de 1 en 1 hasta encontrar el objetivo. Combina las ventajas de las dos estrategias
Para asegurar el completamiento del algoritmo, el DFID introduce un límite de profundidad en cada una de sus iteraciones. El desarrollo del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda limitada en profundidad. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda

=== Backtracking simple (Vuelta atrás) = Fuerza bruta===
Backtracking es una versión de Depth-First. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. Es un método de búsqueda en profundidad que termina encontrando la primera solución sin embargo garantiza encontrar la solución de mínimo coste (óptima), el problema es el tiempo que toma en hacerlo. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor.
A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta) .Este método no utiliza información heurística para elegir el sucesor a expandir aunque existe una variante llamada Backtracking Ordenado que sí utiliza información heurística.
Es un método sistemático que itera a través de todas las combinaciones posibles del espacio de búsqueda. Es una técnica general que debe ser adaptada para cada aplicación particular.
El algoritmo backtracking se aplica en la implementación de los lenguajes de programación, tales como, lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores.

=== Búsqueda en profundidad Branch and Bound (Ramificación y Límite)===
Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Este método imagina el espacio de búsqueda como un árbol de decisión, en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.
Branch and Bound procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar), se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cota, en ese caso, se descarta la rama completa.
Además de ramificar una solución padre (branch) en hijos, se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound), o sea, utiliza la poda para eliminar las ramas del árbol que no conducen a una solución óptima.
La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subárboles de descendientes costosos.
Puede seguir un recorrido en anchura (estrategia FIFO), profundidad (estrategia LIFO) o cálculo de funciones de coste para seleccionar el nodo más prometedor.
Es un algoritmo muy dependiente de la función heurística. En este algoritmo se manejan términos cómo:
*Nodos vivos, que no es más que un nodo factible y prometedor del que no se han generado todos sus hijos.
*Nodo muerto, es aquel del que no se generan más hijos porque ya se han generado todos sus hijos o no es factible ni prometedor.
*Nodo en expansión, es aquel del que se están generando todos sus hijos en ese instante.
El método funciona de la siguiente forma:
*Se selecciona un nodo del conjunto de nodos vivos.
*Se construyen los posibles nodos hijos del nodo seleccionado anteriormente
*Se eliminan algunos de los nodos creados anteriormente reduciendo así el espacio de búsqueda.
El método finaliza cuando se encuentra la solución o cuando se terminan los nodos vivos.

=== Algoritmo de Dijkstra===
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.
Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. Este algoritmo permite computar el camino de costo mínimo de un nodo dado al resto de los nodos de un grafo.
El algoritmo de Dijkstra utiliza una técnica de diseño de algoritmos conocida como greedy (también llamados algoritmos ávidos). Su correcto funcionamiento requiere que los costos asociados a los arcos sean no negativos.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, cuando se obtiene el camino más corto desde el vértice origen al resto de vértices que componen el grafo, el algoritmo se detiene.
El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

=== El algoritmo de búsqueda A*===
Se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
Este es un algoritmo de búsqueda de caminos para encontrar el camino más corto entre dos nodos, mientras intenta evitar obstáculos.
El algoritmo A* además de encontrar el nodo objetivo, nos asegura que es el camino más corto. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados.
En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la función f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.
El ciclo en el algoritmo A* consiste en:
*Buscar el nodo más prometedor.
*Analizar a sus nodos adyacentes.
*Poner el nodo analizado en la lista de cerrados.
El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad, mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia el camino en la búsqueda cada vez que existen nodos más prometedores.
==Fuente==

* Fernández, M. O. (2003). "Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los vídeos juegos"

[[Category:Algoritmos]]

RTP/RTCP

2011-12-05T14:52:45Z

Yrosario06:

{{Ficha Software
|nombre= Protocolo RTP y RTCP
|familia=
|imagen=Protocolo_RTP.JPG‎
|tamaño=
|descripción=RTP es un protocolo basado en IP que proporciona soporte para el transporte de datos en tiempo real (flujos de vídeo y de audio).
|tipo=Protocolo
}}
<div align="justify">
'''Protocolo RTP y RTCP''': Real-time Transport Protocol (Protocolo en Tiempo Real) es una aplicación que envía contenido multimedia sobre la red en tiempo real, le debe agregar números de secuencia y marcas de tiempo a los segmentos antes de pasarlo a la capa de transporte. Estos son necesarios para reconstruir el contenido en el receptor sin tener que esperar a bajar el contenido completo (o una parte suficientemente grande). Es conveniente tener una estructura estandarizada de paquetes que tenga campos que indiquen el tipo de codificación, marcas de tiempo, número de secuencia y otros campos potencialmente útiles.
En el RFC 1889 se define el estándar RTP que cumple con las características mencionadas.
Puede ser utilizado para transportar formatos comunes como [[WAV]] o [[GSM]] para audio y [[MPEG1]] o [[MPEG2]] para video. También permite utilizar formatos propietarios de sonido y video.
==Historia==
RTP fue en un principio diseñado para emisiones multicast de tráfico en tiempo real (aunque también se puede utilizar en emisiones unicast) y puede ser utilizado para el video bajo demanda y servicios interactivos tales como telefonía en Internet.
RTP ha sido diseñado para funcionar junto con el protocolo de control auxiliar RTCP para conseguir mantener la calidad en la transmisión de datos y proporcionar información sobre los participantes al iniciarse la sesión.
==Características==
El objetivo de RTP es que sea maleable y proporcionar la información requerida por una
aplicación particular y normalmente será integrada dentro de la aplicación en vez de constituir un nivel separado. La intención de RTP es que sea adaptado a través de las modificaciones y/o adiciones de las cabeceras necesarias. Dentro de sus principales características se tienen:
* Se encapsula sobre [[UDP]] ([[TCP]] no sirve para aplicaciones de tiempo real).
*Usa puertos de usuario para cada medio que se transfiere.
*Puede enviar tramas generadas por cualquier algoritmo de Codificación: [[H261]], [[MPEG-1]], [[MPEG-2]].
*Puede usarse con direcciones de destino [[unicast]] o [[multicast]].
*Identifica los orígenes del tráfico, lo que permite reencapsular agrupando tráficos a mitad de camino.
*Incorpora marcas de tiempo para cada medio:
**Para sincronización intra-flujo (eliminar [[jitter]]).
**Para sincronización inter-medios (coincidencia audio/vídeo).
*Incluye números de secuencia para detectar pérdidas dentro de un flujo.
===Cabecera de los paquetes===
Los primeros 12 octetos (es decir, los campos V, P, X, CC, M, PT, sequence number, timestamp y SSRC) siempre están presentes, en tanto que los identificadores de "fuentes contribuyentes" (nodos que generan información al mismo tiempo para, supongamos, una videoconferencia) son utilizados sólo en ciertas circunstancias. Después del header "básico" puede tenerse extensiones opcionales para el header (Extension header).
Finalmente el header es seguido por los datos (payload) que transporta RTP y su formato es definido por la aplicación.
El diseño del header de RTP busca llevar sólo aquellos campos que son necesarios para diversos tipos de aplicaciones.
*V (versión), 2 bits: los primeros dos bits identifican la versión del protocolo.
*P (padding), 1 bit: el siguiente bit identifica el padding. Informa que los datos de RTP llevan un "relleno" para completar un bloque de cierto tamaño. El último byte en el mensaje UDP dice de qué tamaño es el padding.
*X (extensión), 1 bit: indica si a continuación viene una cabecera de extensión.
*CC (CSRC count), 4 bits: número de indentificadores CSRC que siguen a la cabercera fija.
*M (marker), 1 bit: está indicada para señalar elementos especiales como salirse de los límites.
*PT (payload type), 7 bits: formato de la información que se transporta para que lo interprete la aplicación.
*Número de secuencia, 16 bits: se incrementa en uno por cada paquete que se envía y sirve para que el receptor detecte pérdidas de paquetes.
*Timestamp, 32 bits: tiempo en el que se muestra el primer octeto de los datos transmitidos en el paquete.
*SSRC, 32 bits: identifica la fuente del paquete.
*CSRC, 32 bits: esta información es introducida por los mezcladores para indicar que han contribuido a modificar la información.
==Protocolo RTCP==

El protocolo RTCP (Protocolo de Control RTP) se basa en la transmisión periódica de paquetes de control a todos los participantes de la sesión, utilizando el mismo mecanismo de transporte que los paquetes RTP. Utiliza un puerto distinto que RTP, por lo general se utilizan puertos consecutivos donde el par es asignado a el flujo RTP y el impar al flujo RTCP.

===Principales Funciones===

*Feedback RTCP: es el encargado de la distribución de la información de realimentación
de la calidad de los datos. Uno podría tomar acciones para mejorar el rendimiento de la
aplicación con esta información, por ejemplo cambiar la codificación, para disminuir la tasa
de bits.

*Identificación: es necesario tener un identificador persistente a nivel de capa de transporte
para las fuentes RTP. Este identificador se llama Nombre Canónico. Dado que el SSRC
puede cambiar debido a un conflicto o debido a el reinicio del programa, los receptores utilizan
el nombre canónico para mantener una lista de los participantes de la sesión. También se
utiliza para agrupar distintos [[streams]] de un participante, por ejemplo para sincronizar audio
con video.

Control de Participantes: las funciones anteriores obligan a los participantes de la
sesión a enviar periódicamente paquetes RTCP, la tasa de envío de esos paquetes tiene que ser controlada para permitir acceso a mas participantes. Dado que los participantes envían los
paquetes de control a todos los demás participantes, cada uno observa localmente el número
de participantes y calcula a partir de este número la tasa de envío de paquetes de control.
===Cabecera de los paquetes===
Cada paquete RTCP empieza con una parte fija que es similar a los paquetes de datos
RTP, seguido por elementos estructurados que pueden ser de longitud variable de acuerdo con el tipo de paquete.

Para cumplir las funciones de este protocolo se imponen las siguientes condiciones:

* Las estadísticas de recepción (en SR o RR) deben ser enviadas tan a menudo como lo
permita el ancho de banda para maximizar la resolución de las estadísticas.
* Los nuevos receptores deben recibir el CNAME de una fuente tan pronto como sea
posible para identificar la fuente.
*El número de tipos de paquetes deben aparecer en el primer paquete para determinar
su tratamiento.

El intervalo de transmisión de paquetes RTCP debe ser calculado de forma que se
permita tener sesiones que vayan desde pocos participantes a miles. Para ello, en cada sesión se asume que el tráfico de datos está sujeto a un límite denominado “ancho de banda de sesión” que se divide entre los participantes. Este ancho de banda debe ser reservado y limitado por la red. El parámetro de ancho de banda de sesión debe ser proporcionado por la aplicación de control de sesión. A partir de este valor y en función del número de participantes se calcula el intervalo con una formula empírica.
==Fuentes==
*http://www.arcesio.net/rtp/rtprtcp1.html
* Protocolos para telefonía sobre IP.
[[Category:Telecomunicaciones]] [[Category:Protocolos]]

RTP/RTCP

2011-12-01T22:02:15Z

Yrosario06: Página creada con '{{Ficha Software |nombre= Protocolo RTP y RTCP |familia= |imagen=Protocolo_RTP.JPG‎ |tamaño= |descripción=RTP es un protocolo basado en IP que proporciona soporte para el t...'

{{Ficha Software
|nombre= Protocolo RTP y RTCP
|familia=
|imagen=Protocolo_RTP.JPG‎
|tamaño=
|descripción=RTP es un protocolo basado en IP que proporciona soporte para el transporte de datos en tiempo real (flujos de vídeo y de audio).
|tipo=Protocolo
}}
<div align="justify">
'''Protocolo RTP: Real-time Transport Protocol (Protocolo en Tiempo Real)'''. Es una aplicación que envía contenido multimedia sobre la red en tiempo real, le debe agregar números de secuencia y marcas de tiempo a los segmentos antes de pasarlo a la capa de transporte. Estos son necesarios para reconstruir el contenido en el receptor sin tener que esperar a bajar el contenido completo (o una parte suficientemente grande). Es conveniente tener una estructura estandarizada de paquetes que tenga campos que indiquen el tipo de codificación, marcas de tiempo, número de secuencia y otros campos potencialmente útiles.
En el RFC 1889 se define el estándar RTP que cumple con las características mencionadas.
Puede ser utilizado para transportar formatos comunes como [[WAV]] o [[GSM]] para audio y [[MPEG1]] o [[MPEG2]] para video. También permite utilizar formatos propietarios de sonido y video.
==Historia==
RTP fue en un principio diseñado para emisiones multicast de tráfico en tiempo real (aunque también se puede utilizar en emisiones unicast) y puede ser utilizado para el video bajo demanda y servicios interactivos tales como telefonía en Internet.
RTP ha sido diseñado para funcionar junto con el protocolo de control auxiliar [[RTCP]] para conseguir mantener la calidad en la transmisión de datos y proporcionar información sobre los participantes al iniciarse la sesión.
==Características==
El objetivo de RTP es que sea maleable y proporcionar la información requerida por una
aplicación particular y normalmente será integrada dentro de la aplicación en vez de constituir un nivel separado. La intención de RTP es que sea adaptado a través de las modificaciones y/o adiciones de las cabeceras necesarias. Dentro de sus principales características se tienen:
* Se encapsula sobre [[UDP]] ([[TCP]] no sirve para aplicaciones de tiempo real).
*Usa puertos de usuario para cada medio que se transfiere.
*Puede enviar tramas generadas por cualquier algoritmo de Codificación: [[H261]], [[MPEG-1]], [[MPEG-2]].
*Puede usarse con direcciones de destino [[unicast]] o [[multicast]].
*Identifica los orígenes del tráfico, lo que permite reencapsular agrupando tráficos a mitad de camino.
*Incorpora marcas de tiempo para cada medio:
**Para sincronización intra-flujo (eliminar [[jitter]]).
**Para sincronización inter-medios (coincidencia audio/vídeo).
*Incluye números de secuencia para detectar pérdidas dentro de un flujo.
===Cabecera de los paquetes===
Los primeros 12 octetos (es decir, los campos V, P, X, CC, M, PT, sequence number, timestamp y SSRC) siempre están presentes, en tanto que los identificadores de "fuentes contribuyentes" (nodos que generan información al mismo tiempo para, supongamos, una videoconferencia) son utilizados sólo en ciertas circunstancias. Después del header "básico" puede tenerse extensiones opcionales para el header (Extension header).
Finalmente el header es seguido por los datos (payload) que transporta RTP y su formato es definido por la aplicación.
El diseño del header de RTP busca llevar sólo aquellos campos que son necesarios para diversos tipos de aplicaciones.
*V (versión), 2 bits: los primeros dos bits identifican la versión del protocolo.
*P (padding), 1 bit: el siguiente bit identifica el padding. Informa que los datos de RTP llevan un "relleno" para completar un bloque de cierto tamaño. El último byte en el mensaje UDP dice de qué tamaño es el padding.
*X (extensión), 1 bit: indica si a continuación viene una cabecera de extensión.
*CC (CSRC count), 4 bits: número de indentificadores CSRC que siguen a la cabercera fija.
*M (marker), 1 bit: está indicada para señalar elementos especiales como salirse de los límites.
*PT (payload type), 7 bits: formato de la información que se transporta para que lo interprete la aplicación.
*Número de secuencia, 16 bits: se incrementa en uno por cada paquete que se envía y sirve para que el receptor detecte pérdidas de paquetes.
*Timestamp, 32 bits: tiempo en el que se muestra el primer octeto de los datos transmitidos en el paquete.
*SSRC, 32 bits: identifica la fuente del paquete.
*CSRC, 32 bits: esta información es introducida por los mezcladores para indicar que han contribuido a modificar la información.
==Protocolo RTCP==

El protocolo RTCP (Protocolo de Control RTP) se basa en la transmisión periódica de paquetes de control a todos los participantes de la sesión, utilizando el mismo mecanismo de transporte que los paquetes RTP. Utiliza un puerto distinto que RTP, por lo general se utilizan puertos consecutivos donde el par es asignado a el flujo RTP y el impar al flujo RTCP.

===Principales Funciones===

*Feedback RTCP: es el encargado de la distribución de la información de realimentación
de la calidad de los datos. Uno podría tomar acciones para mejorar el rendimiento de la
aplicación con esta información, por ejemplo cambiar la codificación, para disminuir la tasa
de bits.

*Identificación: es necesario tener un identificador persistente a nivel de capa de transporte
para las fuentes RTP. Este identificador se llama Nombre Canónico. Dado que el SSRC
puede cambiar debido a un conflicto o debido a el reinicio del programa, los receptores utilizan
el nombre canónico para mantener una lista de los participantes de la sesión. También se
utiliza para agrupar distintos [[streams]] de un participante, por ejemplo para sincronizar audio
con video.

Control de Participantes: las funciones anteriores obligan a los participantes de la
sesión a enviar periódicamente paquetes RTCP, la tasa de envío de esos paquetes tiene que ser controlada para permitir acceso a mas participantes. Dado que los participantes envían los
paquetes de control a todos los demás participantes, cada uno observa localmente el número
de participantes y calcula a partir de este número la tasa de envío de paquetes de control.
===Cabecera de los paquetes===
Cada paquete RTCP empieza con una parte fija que es similar a los paquetes de datos
RTP, seguido por elementos estructurados que pueden ser de longitud variable de acuerdo con el tipo de paquete.

Para cumplir las funciones de este protocolo se imponen las siguientes condiciones:

* Las estadísticas de recepción (en SR o RR) deben ser enviadas tan a menudo como lo
permita el ancho de banda para maximizar la resolución de las estadísticas.
* Los nuevos receptores deben recibir el CNAME de una fuente tan pronto como sea
posible para identificar la fuente.
*El número de tipos de paquetes deben aparecer en el primer paquete para determinar
su tratamiento.

El intervalo de transmisión de paquetes RTCP debe ser calculado de forma que se
permita tener sesiones que vayan desde pocos participantes a miles. Para ello, en cada sesión se asume que el tráfico de datos está sujeto a un límite denominado “ancho de banda de sesión” que se divide entre los participantes. Este ancho de banda debe ser reservado y limitado por la red. El parámetro de ancho de banda de sesión debe ser proporcionado por la aplicación de control de sesión. A partir de este valor y en función del número de participantes se calcula el intervalo con una formula empírica.
==Fuentes==
*http://www.arcesio.net/rtp/rtprtcp1.html
* Protocolos para telefonía sobre IP.
[[Category:Ciencias_informáticas_y_Telecomunicaciones]]
[[Category:Ciencias_informáticas]] [[Category:Software]]

Búsqueda de caminos

2011-11-07T15:04:58Z

Yrosario06:

{{normalizar}}{{Definición
|nombre=Búsqueda de caminos
|imagen=Arboles_Busqueda.JPG
|tamaño=
|concepto=Es la forma en que una entidad en movimiento encuentra un camino alrededor de un obstáculo.
}}
<div align="justify">
'''Búsqueda de caminos'''. Los algoritmos de búsqueda de caminos son usados para encontrar una ruta de navegación entre un punto de inicio y otro objetivo. Esta ruta es generalmente un pequeño subconjunto del mundo.

== Breve reseña histórica ==
Con el gran avance que ha tenido el conocimiento del hombre a través del devenir de los años hay momentos que marcan pautas en el desarrollo de la [[Inteligencia Artificial]], fue en la década del 50 donde se utilizó este término y logró captar la atención de muchos para su posterior evolución. La Inteligencia Artificial atiende una rama muy importante y ésta es la búsqueda de caminos.
Las raíces de los algoritmos de búsqueda de caminos hay que asociarlos a la constante evolución de los [[videojuegos]] ya que es una de las aplicaciones prácticas más interesantes en este entorno, son algoritmos por los cuales nuestro objetivo es capaz de eludir los obstáculos y llegar de un punto A a un punto B.
Es a partir de 1959 donde se empieza a buscar variantes para la problemática de la búsqueda de caminos en video-juegos, este proceso ha sido verdaderamente evolutivo ya que se comenzó con algoritmos como Dijkstra, también llamado algoritmo de caminos mínimos luego siguió el algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) éste fue introducido por primera vez en el año 1977 cuando Slate y Atkin presentaron un programa de ajedrez.
Con la constante optimización de los algoritmos de búsqueda aparece el algoritmo de búsqueda de caminos A*, éste fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
En Cuba comienza a lograrse un avance en este sentido, los video-juegos y simuladores son un campo reciente y por tanto, conllevan una simulación inteligente mucho más real y necesitan algoritmos más fuertes y de un nivel superior.

=== En entornos virtuales===
Una de las problemáticas más vistas en el mundo de los juegos es cómo encontrar el camino mínimo entre dos puntos, este estudio ha comenzado desde los métodos de búsqueda heurística tradicionales que en la mayoría de los casos son incapaces de resolver problemas donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido hasta los métodos de búsqueda heurística en tiempo real.
Existen algoritmos capaces de solucionar el problema de búsqueda de caminos de manera eficiente, mediante algoritmos de búsqueda heurística en tiempo real. Se presentan varios algoritmos que mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por etapa de planificación

== Aplicaciones de los algoritmos de búsqueda==
La investigación de algoritmos tanto exactos como heurísticos para resolver problemas de optimización tiene una vigencia inusualmente importante en estos días, de esta forma, actualmente es acuciante la necesidad de algoritmos muy eficientes que puedan dar respuesta en tiempo real a problemas del usuario o del sistema, y que permitan trabajar con los nuevos sistemas operativos y máquinas.
En el mundo de los video-juegos existen muchas aplicaciones para los algoritmos de búsqueda de caminos. Como todos sabemos una de las formas más comunes en las que se aplican estos algoritmos es en los juegos de estrategia y de rol, donde les decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de uno de estos algoritmos.
Los algoritmos de búsqueda de caminos tienen otras tantas aplicaciones muy útiles para el mundo actual, por ejemplo, algo que tiene mucho éxito en nuestros días son los GPS que poseen los carros de alta tecnología de hoy en día que se utilizan para ayudar al conductor a hallar caminos y sugerir los atajos o caminos más cortos. Esto resulta ser de gran utilidad para el turista que se encuentre en una cuidad desconocida para él.
En el mundo de la medicina también existen aplicaciones para estos algoritmos, los grandes programas hechos para realizar cirugías a pacientes están pensados para hallar el camino más corto y seguro considerando todos los factores como flujos sanguíneos, obstáculos y otros, para llegar a algún lugar decidido previamente por el cirujano dada una entrada. Parte importante de esta técnica está en la definición de la distancia heurística que debe recorrer.

== Conceptos para entender la búsqueda en árboles y grafos==
Para entender a cabalidad todo lo relacionado con los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda, por ejemplo, en problemas de este tipo se utiliza mucho el término búsqueda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

=== ¿Qué es búsqueda?===
Método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente.
En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

== Estructuras de datos para la búsqueda de camino==
En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

== Clasificación de algoritmos==

Según la búsqueda los algoritmos se pueden clasificar en dos clases:

=== Los métodos off-line===
Este método sigue el siguiente esquema, primero calculan el plan o ruta de mínimo coste de un problema mediante la búsqueda en el espacio de estados y luego ejecutan el plan realizando las acciones o secuencia de operaciones en el entorno. Este esquema, a menudo considerado de forma implícita, supone que ejecutar la solución en el mundo real es un proceso directo y no presenta ninguna dificultad, o sea, primero se realiza una búsqueda completa en el espacio de estados y luego se ejecuta una secuencia de acciones u operaciones en el entorno. En la siguiente figura se muestra su funcionamiento.
Un ejemplo típico de aplicación de los métodos off-line es la búsqueda de rutas. La búsqueda de rutas consiste en encontrar una ruta en un grafo desde el nodo inicial hasta el nodo objetivo.

=== Los métodos on-line===
En cambio, los métodos on-line intercalan planificación (mediante búsqueda local) y ejecución del plan mientras resuelven un problema. Debido a la propiedad on-line, los métodos tienen una gran flexibilidad para operar en entornos desconocidos y dinámicos. Además, no requieren conocer a-priori todo el espacio de estados, pueden adaptarse a objetos cambiantes y operar en entornos no determinados. Este modo de operación denominado on-line da lugar a los algoritmos de búsqueda en tiempo real. En la siguiente figura se representa el modo de operar de la búsqueda on-line.

== Criterios para evaluar las estrategias de búsqueda==
Cada algoritmo de búsqueda de caminos tiene una serie de características que lo identifican los cuales son:
* Completitud.
* Complejidad en tiempo.
* Complejidad en espacio.
* Optimización.

== Análisis de algoritmos ==
=== Depth-First o búsqueda en profundidad (LIFO) ===
Esta búsqueda se centra en expandir un único camino desde la raíz. Siempre se expande el nodo más profundo en la frontera actual. En el caso de llegar a un “callejón sin salida” se retrocede hasta el nodo más cercano (siguiendo al nodo padre) donde se puede tomar una rama alternativa para poder seguir avanzando.
Se puede implementar, mediante el Algoritmo General, considerando la lista, como una pila (cuyas operaciones funcionan en forma LIFO). De esta manera el siguiente nodo a expandir siempre será el último que se haya colocado en la pila de ese nivel, garantizando esto que la expansión vaya aumentando en la profundidad de los nodos.
Es común aplicar esta estrategia mediante un algoritmo recursivo que recorra el árbol en Pre-Orden. Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos en cada nodo. De aquí surge otro importante algoritmo, “el backtracking”

=== Breadth-First search (búsqueda a lo ancho)===
La búsqueda en anchura (BFS o 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 todos los 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.
Este algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente, este algoritmo tiene como ventaja que, al expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.
Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables y que además requiere de mucha memoria.
Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante. Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.
La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

=== Búsqueda bidireccional===
En la búsqueda bidireccional se llevan a la vez dos búsquedas, una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que los recorridos ascendente y descendente puedan encontrarse en algún momento. (Tener en cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsqueda bidireccional). Por lo demás este método no tiene ninguna dificultad, naturalmente, se podría realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial en profundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro.
Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

===Búsqueda de profundidad limitada===
Para evitar caer en caminos de profundidad muy grande, a la mayoría de los algoritmos que usan depth-first se les impone un límite de profundidad máxima. Por tanto es similar a la estrategia de Primero en Profundidad, pero se trata de eliminar el problema de que se puedan generar árboles “ilimitados”.
Para ello se establece un límite L a la profundidad del árbol. Todo nodo cuya profundidad sea L, no es expandido (se considera sin sucesores). El problema que puede pasar es si escogemos un valor de L menor que la profundidad del objetivo, en cuyo caso no llegaríamos a la solución. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo.

=== Algoritmo DFID (primero en profundidad con profundidad iterativa)===
El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) fue introducido por primera vez cuando Slate y Atkin presentaron un programa de ajedrez.
El algoritmo combina la estrategia de Primero en Profundidad con la de Profundidad Limitada, comenzando con límite igual a 0, aumentándolo de 1 en 1 hasta encontrar el objetivo. Combina las ventajas de las dos estrategias
Para asegurar el completamiento del algoritmo, el DFID introduce un límite de profundidad en cada una de sus iteraciones. El desarrollo del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda limitada en profundidad. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda

=== Backtracking simple (Vuelta atrás) = Fuerza bruta===
Backtracking es una versión de Depth-First. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. Es un método de búsqueda en profundidad que termina encontrando la primera solución sin embargo garantiza encontrar la solución de mínimo coste (óptima), el problema es el tiempo que toma en hacerlo. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor.
A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta) .Este método no utiliza información heurística para elegir el sucesor a expandir aunque existe una variante llamada Backtracking Ordenado que sí utiliza información heurística.
Es un método sistemático que itera a través de todas las combinaciones posibles del espacio de búsqueda. Es una técnica general que debe ser adaptada para cada aplicación particular.
El algoritmo backtracking se aplica en la implementación de los lenguajes de programación, tales como, lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores.

=== Búsqueda en profundidad Branch and Bound (Ramificación y Límite)===
Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Este método imagina el espacio de búsqueda como un árbol de decisión, en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.
Branch and Bound procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar), se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cota, en ese caso, se descarta la rama completa.
Además de ramificar una solución padre (branch) en hijos, se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound), o sea, utiliza la poda para eliminar las ramas del árbol que no conducen a una solución óptima.
La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subárboles de descendientes costosos.
Puede seguir un recorrido en anchura (estrategia FIFO), profundidad (estrategia LIFO) o cálculo de funciones de coste para seleccionar el nodo más prometedor.
Es un algoritmo muy dependiente de la función heurística. En este algoritmo se manejan términos cómo:
*Nodos vivos, que no es más que un nodo factible y prometedor del que no se han generado todos sus hijos.
*Nodo muerto, es aquel del que no se generan más hijos porque ya se han generado todos sus hijos o no es factible ni prometedor.
*Nodo en expansión, es aquel del que se están generando todos sus hijos en ese instante.
El método funciona de la siguiente forma:
*Se selecciona un nodo del conjunto de nodos vivos.
*Se construyen los posibles nodos hijos del nodo seleccionado anteriormente
*Se eliminan algunos de los nodos creados anteriormente reduciendo así el espacio de búsqueda.
El método finaliza cuando se encuentra la solución o cuando se terminan los nodos vivos.

=== Algoritmo de Dijkstra===
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.
Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. Este algoritmo permite computar el camino de costo mínimo de un nodo dado al resto de los nodos de un grafo.
El algoritmo de Dijkstra utiliza una técnica de diseño de algoritmos conocida como greedy (también llamados algoritmos ávidos). Su correcto funcionamiento requiere que los costos asociados a los arcos sean no negativos.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, cuando se obtiene el camino más corto desde el vértice origen al resto de vértices que componen el grafo, el algoritmo se detiene.
El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

=== El algoritmo de búsqueda A*===
Se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
Este es un algoritmo de búsqueda de caminos para encontrar el camino más corto entre dos nodos, mientras intenta evitar obstáculos.
El algoritmo A* además de encontrar el nodo objetivo, nos asegura que es el camino más corto. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados.
En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la función f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.
El ciclo en el algoritmo A* consiste en:
*Buscar el nodo más prometedor.
*Analizar a sus nodos adyacentes.
*Poner el nodo analizado en la lista de cerrados.
El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad, mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia el camino en la búsqueda cada vez que existen nodos más prometedores.
==Fuente==

* Fernández, M. O. (2003). "Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los vídeos juegos"

[[Category:Algoritmos]]

Calidad de servicio

2011-10-13T14:23:41Z

Yrosario06: Página creada con '{{Ficha Software |nombre=Calidad de Servicios en VoIP |familia= |imagen=Calidad_de_Servicio.JPEG‎ |tamaño= |descripción=La Calidad de Servicio o QoS (Quality of Service) es ...'

{{Ficha Software
|nombre=Calidad de Servicios en VoIP
|familia=
|imagen=Calidad_de_Servicio.JPEG‎
|tamaño=
|descripción=La Calidad de Servicio o QoS (Quality of Service) es el efecto global de las prestaciones de un servicio que determinan el grado de satisfacción de un usuario al utilizar dicho servicio.
|imagen2=
|tamaño2=
|descripción2=
|creador=
|desarrollador=
|diseñador=
|modelo de desarrollo=
|lanzamiento inicial=
|versiones=
|última versión estable=
|género=
|sistemas operativos=
|idioma=
|licencia=
|premios=
|web=
}}
<div align="justify">

<big>'''La Calidad de Servicio o QoS'''</big> (Quality of Service), se define como la capacidad que tiene una red de proveer diferentes niveles de servicio para asegurar distintos perfiles de tráfico. Según IETF RFC 2386 es un conjunto de requisitos del servicio que debe cumplir la red en el transporte de un flujo. Puede ser implementada en diferentes situaciones, para gestionar la congestión o para evitarla. Permite controlar algunas características significativas de la transmisión de paquetes. Estas características pueden especificarse en términos cuantitativos o estadísticos tales como: [[ancho de banda]], [[latencia]], [[jitter]], [[pérdida de paquetes en la red]]; asegurando un grado de fiabilidad preestablecido que cumpla los requisitos de tráfico, en función del perfil y ancho de banda para un determinado flujo de datos.
== Aplicaciones ==
La motivación para aplicar Calidad de Servicio en redes [[IP]] se resume en las siguientes necesidades:
*Priorizar ciertas aplicaciones en la red que requieren de un alto nivel de servicio [[VOIP]].
*Maximizar el uso de la infraestructura de red, manteniendo un margen de flexibilidad, seguridad y crecimiento para servicios emergentes.
*Mejorar las prestaciones para servicios en tiempo real.
*Responder a los cambios en el perfil de tráfico establecido.
*Proporcionar mecanismos para priorizar tráfico.
== Puntos de vista==
Para brindar un mejor entendimiento sobre lo que significa QoS, se aprecian dos puntos de vista diferentes: el primero desde el punto de vista del usuario final y otro, desde el punto de vista del funcionamiento de la red. Para el usuario, es cómo él percibe el recibo de un determinado servicio, ya sea voz, audio o video. Para la red, es la capacidad de proporcionar un servicio al usuario, acorde al acuerdo del mismo entre el usuario y el proveedor, para esto debe ser capaz de diferenciar entre las distintas clases de tráfico y una vez diferenciadas proporcionar el servicio y además ser capaz de hacer diferenciación en la red mediante prioridades.
==Factores que la afectan==
Son diversas las causas que pueden atentar contra el correcto funcionamiento de la [[red]] o que el usuario tenga una percepción negativa del servicio recibido. Estos factores están dados en su mayoría a que la voz debe viajar en un entorno diseñado para paquetes de datos, sufriendo cambios de paquetización, fragmentación, intercalado, codificación o descodificación a través de la red. Algunos de estos parámetros se describen a continuación.
==Especificaciones==
El objetivo básico de las clases de tráfico (CT) y el tipo de servicio (ToS) es conseguir el ancho de banda y la latencia necesarios para una aplicación determinada. Las clases de tráficos permiten al administrador de la red agrupar diferentes flujos de paquetes, teniendo cada uno: requisitos de latencia y ancho de banda diferentes. El tipo de servicio es un campo en una cabecera IP, que permite que tenga lugar una clase de servicio determinada. Mientras que las clases de servicio (CoS) es un esquema de clasificación con que son agrupados los tráficos que tienen requerimientos de tratamiento similares, para diferenciar los tipos de tráfico y por ende poder priorizarlos.
==Niveles==
Los niveles de Calidad de Servicio están referidos a las actuales capacidades de las conexiones fin a fin, o sea, las capacidades que tiene una red determinada de realizar un servicio para un tráfico específico. Los servicios difieren en cuán estrictos pueden ser los niveles de QoS, o sea, que tiene que ser específico para un ancho de banda, jitter o pérdida de paquetes determinado estos son:
*Nivel Best Effort: básicamente estos servicios no ofrecen ninguna garantía. Usualmente utiliza técnicas FIFO (First in First Out o Primero en Entrar Primero en Salir), que no tienen ninguna diferenciación entre los distintos flujos.
*Nivel para Servicios Diferenciados (Diffserv): se basa en la división del tráfico en diferentes clases y en la asignación de prioridades.
*Nivel Garantizado: está destinada para aplicaciones con requerimientos exigentes de tiempo real. Esta calidad asegura un ancho de banda, un límite en el retardo y ninguna pérdida en las colas.
==Mecanismos==
Son diversos los mecanismos existentes que se implementan para garantizar una adecuada Calidad de Servicio, los cuales se muestran a continuación:
*Gestión de colas: por la naturaleza que tiene la transmisión de aplicaciones multimedia a través de la red, propicia que la cantidad de tráfico no exceda la velocidad de la conexión haciendo varias colas para los diferentes servicios.
*Clasificación de paquetes: para manipular los tráficos y otorgarles QoS, se utilizan los procedimientos básicos de clasificación y asignación de prioridad.
*Medición y flujo de formación de tráfico: en muchas ocasiones es necesario limitar la cantidad de tráfico de una aplicación a través de varias interfaces. Estas funcionalidades de control vienen determinadas por las herramientas de límites de tasa y las herramientas de formación.
*Gestión de colas de altas velocidades: se basa en la manera que los [[protocolo]]s operan, con el fin de no llegar a la congestión de la red.
*Metodologías de Estimación de Calidad de Servicio Percibida: es la calidad percibida por el usuario independientemente de lo que la red transporte. Las medidas de calidad percibida pueden realizarse usando métodos objetivos o subjetivos.
==Herramientas==
Son múltiples las herramientas que hacen uso de los factores que se encuentran presentes a la hora de asegurar que una determinada red presenta una adecuada Calidad de Servicioentre ellos se encuentran la herramienta PING (Packet Internet Groper), la Traceroute o Tracert, la VQManager, MyConnection Server entre otras.
==Véase también==
[[Factores que afectan la Calidad de Servicios.]]
==Fuentes==
*http://qos.iespana.es/capitulo2.htm
*García Ivanova, Natacha y Alvarez Rosario, Yisleivis.Propuesta de métricas para medir Calidad de Servicio en Voz sobre IP.2009.
[[Category:Procesamiento_de_voz]]

Maqueta de la Ciudad Santiago de Cuba

2011-10-13T14:18:20Z

Yrosario06:

{{Ficha_Obra_de_Arte
|nombre=Maqueta de la Ciudad Santiago de Cuba
|imagen=Maqueta_de_la_ciudad.JPG
|descripción=La maqueta representa el área urbana de la ciudad de Santiago de Cuba, con una extensión de 91 Km<sup>2</sup>.
|tipo=Maqueta
|autor=
|año=
|país={{Bandera2|Cuba}}
}}
<div align="justify">
'''Maqueta de la Ciudad de Santiago de Cuba'''. La [[maqueta]] representa un espacio de interés, de conocimiento, distracción, instrucción y educación para todos los visitantes.

==Historia==
La elaboración de la maqueta comenzó en los años 90. Es un proyecto en ejecución, la instalación que lo expone fue inaugurada el 1 de agosto de 2003.
Donde se aprecian las zonas: urbanas, industrial y suburbana. Se destaca el Centro Histórico con una extensión de 3.2 Km<sup>2</sup>, declarado [[Monumento Nacional]] en 1978. Nos da la bienvenida a la bahía la [[Fortaleza del Morro]], devenido museo y declarado [[Patrimonio Mundial]] por la [[UNESCO]] en 1997.

==Creador==
La creación de la maqueta en Santiago de Cuba se debe al Grupo de Desarrollo Integral de [[Santiago de Cuba]], grupo creado para evaluar proyectos de arquitectura y urbanismo en la ciudad con proyección futurista. Uno de sus objetivos fue la creación de una maqueta en la ciudad a escala de 1.1000, la cual no pudieron continuar desarrollando por la desintegración del mismo y ésta fue asumida como proyecto por la [[Oficina del Conservador de la Ciudad]]. Su realización está en manos de un grupo de personas graduadas de estudios relacionados con el trabajo que realizan, llamados maquetistas.

==Ubicación==
Cuando existían varias piezas se hizo necesaria la búsqueda de un edificio para exponerla, cercano a la Oficina del Conservador. Se aprovechó toda el área asignada, así como también la estructura y algunas áreas ya construidas que se encontraban en buen estado de conservación y que permitieron ser reutilizadas.
El inmueble anterior era de estilo Art-decó estilo que fue desarrollado en la etapa republicana y data su construcción de finales de la década de los 40, principios del 50, que después se utilizó como academia de deportes en la etapa revolucionaria.

==Descripción ==
La maqueta le permite visualizar las características propias de la ciudad, a nivel morfológico e irregularidad de lotes y calles en general. Así como su desarrollo físico incluso por etapas de construcción que son diferenciadas por colores según los períodos históricos. Existe un nivel de detalle que posibilita disfrutar de plazas, iglesias, las montañas, casas, la bahía y sus barcos para el cual se utilizaron materiales como cartulina, madera, esponja, arena, papel vinilo.
El edificio para la Maqueta de la Ciudad se construye con el objetivo de exponer al visitante (ya sea local, foráneo o extranjero), la ciudad de Santiago de Cuba en miniatura (o sea en maqueta). Muestra la arquitectura, topografía, representa la ciudad con un nivel de detalles adecuados. Visualiza el desarrollo urbano y aprovecha su exposición con fines didácticos.
Cuenta con una cafetería al aire libre que brinda una hermosa vista a la ciudad y su bahía. Además tiene un espacio dedicado al arte donde se hacen expociones que caracterizan y representan a Santiago de Cuba.
Su recorrido es facilitado por las guías que allí se encuentran.

==Aporte Social==
Es un lugar frecuentado por centros estudiantiles y de trabajo, personas de la tercera edad, visitantes de otra provincia y el extranjero que se impresionan por el trabajo que se realiza. En la lista de personalidades que han pasado por la instalación se encuentran embajadores, ministros, familiares de los [[Cinco Héroes]], el [[Comandante Juan Almeida Bosque]] y nuestro Ministro de Cultura Abel Prieto.
==Fuentes==
*Entrevista: Mercedes Adión Díaz museóloga de la Maqueta de la Ciudad.
*Entrevista: Bertha Morales Guilarte guía de la Maqueta de la Ciudad.
[[Category:Urbanismo]][[Category:Modelismo]]

Maqueta de la Ciudad Santiago de Cuba

2011-09-19T13:57:29Z

Yrosario06: Página creada con '{{Ficha_Obra_de_Arte |nombre=Maqueta de la Ciudad Santiago de Cuba |imagen=Maqueta_de_la_ciudad.JPG |descripción=La maqueta representa el área urbana de la ciudad de Santiago ...'

{{Ficha_Obra_de_Arte
|nombre=Maqueta de la Ciudad Santiago de Cuba
|imagen=Maqueta_de_la_ciudad.JPG
|descripción=La maqueta representa el área urbana de la ciudad de Santiago de Cuba, con una extensión de 91 Km<sup>2</sup>.
|tipo=Maqueta
|autor=
|año=
|país={{Bandera2|Cuba}}
}}
<div align="justify">
'''Maqueta de la Ciudad de Santiago de Cuba'''.La [[maqueta]] representa un espacio de interés, de conocimiento, distracción, instrucción y educación para todos los visitantes.

==Historia==
La elaboración de la maqueta comenzó en los años 90. Es un proyecto en ejecución, la instalación que lo expone fue inaugurada el 1 de agosto de 2003.
Donde se aprecian las zonas: urbanas, industrial y suburbana. Se destaca el Centro Histórico con una extensión de 3.2 Km<sup>2</sup>, declarado [[Monumento Nacional]] en 1978. Nos da la bienvenida a la bahía la [[Fortaleza del Morro]], devenido museo y declarado [[Patrimonio Mundial]] por la [[UNESCO]] en 1997.

==Creador==
La creación de la maqueta en Santiago de Cuba se debe al Grupo de Desarrollo Integral de [[Santiago de Cuba]], grupo creado para evaluar proyectos de arquitectura y urbanismo en la ciudad con proyección futurista. Uno de sus objetivos fue la creación de una maqueta en la ciudad a escala de 1.1000, la cual no pudieron continuar desarrollando por la desintegración del mismo y ésta fue asumida como proyecto por la [[Oficina del Conservador de la Ciudad]]. Su realización está en manos de un grupo de personas graduadas de estudios relacionados con el trabajo que realizan, llamados maquetistas.

==Ubicación==
Cuando existían varias piezas se hizo necesaria la búsqueda de un edificio para exponerla, cercano a la Oficina del Conservador. Se aprovechó toda el área asignada, así como también la estructura y algunas áreas ya construidas que se encontraban en buen estado de conservación y que permitieron ser reutilizadas.
El inmueble anterior era de estilo Art-decó estilo que fue desarrollado en la etapa republicana y data su construcción de finales de la década de los 40, principios del 50, que después se utilizó como academia de deportes en la etapa revolucionaria.

==Descripción ==
La maqueta le permite visualizar las características propias de la ciudad, a nivel morfológico e irregularidad de lotes y calles en general. Así como su desarrollo físico incluso por etapas de construcción que son diferenciadas por colores según los períodos históricos. Existe un nivel de detalle que posibilita disfrutar de plazas, iglesias, las montañas, casas, la bahía y sus barcos para el cual se utilizaron materiales como cartulina, madera, esponja, arena, papel vinilo.
El edificio para la Maqueta de la Ciudad se construye con el objetivo de exponer al visitante (ya sea local, foráneo o extranjero), la ciudad de Santiago de Cuba en miniatura (o sea en maqueta). Muestra la arquitectura, topografía, representa la ciudad con un nivel de detalles adecuados. Visualiza el desarrollo urbano y aprovecha su exposición con fines didácticos.
Cuenta con una cafetería al aire libre que brinda una hermosa vista a la ciudad y su bahía. Además tiene un espacio dedicado al arte donde se hacen expociones que caracterizan y representan a Santiago de Cuba.
Su recorrido es facilitado por las guías que allí se encuentran.

==Aporte Social==
Es un lugar frecuentado por centros estudiantiles y de trabajo, personas de la tercera edad, visitantes de otra provincia y el extranjero que se impresionan por el trabajo que se realiza. En la lista de personalidades que han pasado por la instalación se encuentran embajadores, ministros, familiares de los [[Cinco Héroes]], el [[Comandante Juan Almeida Bosque]] y nuestro Ministro de Cultura Abel Prieto.
==Fuentes==
*Entrevista: Mercedes Adión Díaz museóloga de la Maqueta de la Ciudad.
*Entrevista: Bertha Morales Guilarte guía de la Maqueta de la Ciudad.
[[Category:Urbanismo]][[Category:Modelismo]]

Búsqueda de caminos

2011-09-07T14:15:36Z

Yrosario06:

{{Definición
|nombre=Búsqueda de caminos
|imagen=Arboles_Busqueda.JPG
|tamaño=
|concepto=Es la forma en que una entidad en movimiento encuentra un camino alrededor de un obstáculo.
}}'''Búsqueda de caminos'''. Los algoritmos de búsqueda de caminos son usados para encontrar una ruta de navegación entre un punto de inicio y otro objetivo. Esta ruta es generalmente un pequeño subconjunto del mundo.

== Breve reseña histórica ==
Con el gran avance que ha tenido el conocimiento del hombre a través del devenir de los años hay momentos que marcan pautas en el desarrollo de la [[Inteligencia Artificial]], fue en la década del 50 donde se utilizó este término y logró captar la atención de muchos para su posterior evolución. La Inteligencia Artificial atiende una rama muy importante y ésta es la búsqueda de caminos.
Las raíces de los algoritmos de búsqueda de caminos hay que asociarlos a la constante evolución de los [[video-juegos]] ya que es una de las aplicaciones prácticas más interesantes en este entorno, son algoritmos por los cuales nuestro objetivo es capaz de eludir los obstáculos y llegar de un punto A a un punto B.
Es a partir de 1959 donde se empieza a buscar variantes para la problemática de la búsqueda de caminos en video-juegos, este proceso ha sido verdaderamente evolutivo ya que se comenzó con algoritmos como Dijkstra, también llamado algoritmo de caminos mínimos luego siguió el algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) éste fue introducido por primera vez en el año 1977 cuando Slate y Atkin presentaron un programa de ajedrez.
Con la constante optimización de los algoritmos de búsqueda aparece el algoritmo de búsqueda de caminos A*, éste fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
En Cuba comienza a lograrse un avance en este sentido, los video-juegos y simuladores son un campo reciente y por tanto, conllevan una simulación inteligente mucho más real y necesitan algoritmos más fuertes y de un nivel superior.

=== En entornos virtuales===
Una de las problemáticas más vistas en el mundo de los juegos es cómo encontrar el camino mínimo entre dos puntos, este estudio ha comenzado desde los métodos de búsqueda heurística tradicionales que en la mayoría de los casos son incapaces de resolver problemas donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido hasta los métodos de búsqueda heurística en tiempo real.
Existen algoritmos capaces de solucionar el problema de búsqueda de caminos de manera eficiente, mediante algoritmos de búsqueda heurística en tiempo real. Se presentan varios algoritmos que mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por etapa de planificación

== Aplicaciones de los algoritmos de búsqueda==
La investigación de algoritmos tanto exactos como heurísticos para resolver problemas de optimización tiene una vigencia inusualmente importante en estos días, de esta forma, actualmente es acuciante la necesidad de algoritmos muy eficientes que puedan dar respuesta en tiempo real a problemas del usuario o del sistema, y que permitan trabajar con los nuevos sistemas operativos y máquinas.
En el mundo de los video-juegos existen muchas aplicaciones para los algoritmos de búsqueda de caminos. Como todos sabemos una de las formas más comunes en las que se aplican estos algoritmos es en los juegos de estrategia y de rol, donde les decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de uno de estos algoritmos.
Los algoritmos de búsqueda de caminos tienen otras tantas aplicaciones muy útiles para el mundo actual, por ejemplo, algo que tiene mucho éxito en nuestros días son los GPS que poseen los carros de alta tecnología de hoy en día que se utilizan para ayudar al conductor a hallar caminos y sugerir los atajos o caminos más cortos. Esto resulta ser de gran utilidad para el turista que se encuentre en una cuidad desconocida para él.
En el mundo de la medicina también existen aplicaciones para estos algoritmos, los grandes programas hechos para realizar cirugías a pacientes están pensados para hallar el camino más corto y seguro considerando todos los factores como flujos sanguíneos, obstáculos y otros, para llegar a algún lugar decidido previamente por el cirujano dada una entrada. Parte importante de esta técnica está en la definición de la distancia heurística que debe recorrer.

== Conceptos para entender la búsqueda en árboles y grafos==
Para entender a cabalidad todo lo relacionado con los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda, por ejemplo, en problemas de este tipo se utiliza mucho el término búsqueda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

=== ¿Qué es búsqueda?===
Método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente.
En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

== Estructuras de datos para la búsqueda de camino==
En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

== Clasificación de algoritmos==
Según la búsqueda los algoritmos se pueden clasificar en dos clases:

=== Los métodos off-line===
Este método sigue el siguiente esquema, primero calculan el plan o ruta de mínimo coste de un problema mediante la búsqueda en el espacio de estados y luego ejecutan el plan realizando las acciones o secuencia de operaciones en el entorno. Este esquema, a menudo considerado de forma implícita, supone que ejecutar la solución en el mundo real es un proceso directo y no presenta ninguna dificultad, o sea, primero se realiza una búsqueda completa en el espacio de estados y luego se ejecuta una secuencia de acciones u operaciones en el entorno. En la siguiente figura se muestra su funcionamiento.
Un ejemplo típico de aplicación de los métodos off-line es la búsqueda de rutas. La búsqueda de rutas consiste en encontrar una ruta en un grafo desde el nodo inicial hasta el nodo objetivo.

=== Los métodos on-line===
En cambio, los métodos on-line intercalan planificación (mediante búsqueda local) y ejecución del plan mientras resuelven un problema. Debido a la propiedad on-line, los métodos tienen una gran flexibilidad para operar en entornos desconocidos y dinámicos. Además, no requieren conocer a-priori todo el espacio de estados, pueden adaptarse a objetos cambiantes y operar en entornos no determinados. Este modo de operación denominado on-line da lugar a los algoritmos de búsqueda en tiempo real. En la siguiente figura se representa el modo de operar de la búsqueda on-line.

== Criterios para evaluar las estrategias de búsqueda==
Cada algoritmo de búsqueda de caminos tiene una serie de características que lo identifican los cuales son:
*Completitud.
*Complejidad en tiempo.
*Complejidad en espacio.
*Optimización.

== Análisis de Algoritmos ==
=== Depth-First o Búsqueda en Profundidad (LIFO) ===
Esta búsqueda se centra en expandir un único camino desde la raíz. Siempre se expande el nodo más profundo en la frontera actual. En el caso de llegar a un “callejón sin salida” se retrocede hasta el nodo más cercano (siguiendo al nodo padre) donde se puede tomar una rama alternativa para poder seguir avanzando.
Se puede implementar, mediante el Algoritmo General, considerando la lista, como una pila (cuyas operaciones funcionan en forma LIFO). De esta manera el siguiente nodo a expandir siempre será el último que se haya colocado en la pila de ese nivel, garantizando esto que la expansión vaya aumentando en la profundidad de los nodos.
Es común aplicar esta estrategia mediante un algoritmo recursivo que recorra el árbol en Pre-Orden. Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos en cada nodo. De aquí surge otro importante algoritmo, “el backtracking”

=== Breadth-First search (búsqueda a lo ancho)===
La búsqueda en anchura (BFS o 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 todos los 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.
Este algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente, este algoritmo tiene como ventaja que, al expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.
Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables y que además requiere de mucha memoria.
Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante. Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.
La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

=== Búsqueda Bidireccional===
En la búsqueda bidireccional se llevan a la vez dos búsquedas, una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que los recorridos ascendente y descendente puedan encontrarse en algún momento. (Tener en cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsqueda bidireccional). Por lo demás este método no tiene ninguna dificultad, naturalmente, se podría realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial en profundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro.
Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

===Búsqueda de Profundidad Limitada===
Para evitar caer en caminos de profundidad muy grande, a la mayoría de los algoritmos que usan depth-first se les impone un límite de profundidad máxima. Por tanto es similar a la estrategia de Primero en Profundidad, pero se trata de eliminar el problema de que se puedan generar árboles “ilimitados”.
Para ello se establece un límite L a la profundidad del árbol. Todo nodo cuya profundidad sea L, no es expandido (se considera sin sucesores). El problema que puede pasar es si escogemos un valor de L menor que la profundidad del objetivo, en cuyo caso no llegaríamos a la solución. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo.

=== Algoritmo DFID (primero en profundidad con profundidad iterativa)===
El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) fue introducido por primera vez cuando Slate y Atkin presentaron un programa de ajedrez.
El algoritmo combina la estrategia de Primero en Profundidad con la de Profundidad Limitada, comenzando con límite igual a 0, aumentándolo de 1 en 1 hasta encontrar el objetivo. Combina las ventajas de las dos estrategias
Para asegurar el completamiento del algoritmo, el DFID introduce un límite de profundidad en cada una de sus iteraciones. El desarrollo del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda limitada en profundidad. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda

=== Backtracking Simple (Vuelta atrás) = Fuerza Bruta===
Backtracking es una versión de Depth-First. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. Es un método de búsqueda en profundidad que termina encontrando la primera solución sin embargo garantiza encontrar la solución de mínimo coste (óptima), el problema es el tiempo que toma en hacerlo. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor.
A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta) .Este método no utiliza información heurística para elegir el sucesor a expandir aunque existe una variante llamada Backtracking Ordenado que sí utiliza información heurística.
Es un método sistemático que itera a través de todas las combinaciones posibles del espacio de búsqueda. Es una técnica general que debe ser adaptada para cada aplicación particular.
El algoritmo backtracking se aplica en la implementación de los lenguajes de programación, tales como, lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores.

=== Búsqueda en Profundidad Branch and Bound (Ramificación y Límite)===
Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Este método imagina el espacio de búsqueda como un árbol de decisión, en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.
Branch and Bound procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar), se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cota, en ese caso, se descarta la rama completa.
Además de ramificar una solución padre (branch) en hijos, se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound), o sea, utiliza la poda para eliminar las ramas del árbol que no conducen a una solución óptima.
La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subárboles de descendientes costosos.
Puede seguir un recorrido en anchura (estrategia FIFO), profundidad (estrategia LIFO) o cálculo de funciones de coste para seleccionar el nodo más prometedor.
Es un algoritmo muy dependiente de la función heurística. En este algoritmo se manejan términos cómo:
*Nodos vivos, que no es más que un nodo factible y prometedor del que no se han generado todos sus hijos.
*Nodo muerto, es aquel del que no se generan más hijos porque ya se han generado todos sus hijos o no es factible ni prometedor.
*Nodo en expansión, es aquel del que se están generando todos sus hijos en ese instante.
El método funciona de la siguiente forma:
*Se selecciona un nodo del conjunto de nodos vivos.
*Se construyen los posibles nodos hijos del nodo seleccionado anteriormente
*Se eliminan algunos de los nodos creados anteriormente reduciendo así el espacio de búsqueda.
El método finaliza cuando se encuentra la solución o cuando se terminan los nodos vivos.

=== Algoritmo de Dijkstra===
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.
Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. Este algoritmo permite computar el camino de costo mínimo de un nodo dado al resto de los nodos de un grafo.
El algoritmo de Dijkstra utiliza una técnica de diseño de algoritmos conocida como greedy (también llamados algoritmos ávidos). Su correcto funcionamiento requiere que los costos asociados a los arcos sean no negativos.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, cuando se obtiene el camino más corto desde el vértice origen al resto de vértices que componen el grafo, el algoritmo se detiene.
El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

=== El algoritmo de búsqueda A*===
Se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
Este es un algoritmo de búsqueda de caminos para encontrar el camino más corto entre dos nodos, mientras intenta evitar obstáculos.
El algoritmo A* además de encontrar el nodo objetivo, nos asegura que es el camino más corto. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados.
En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la función f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.
El ciclo en el algoritmo A* consiste en:
*Buscar el nodo más prometedor.
*Analizar a sus nodos adyacentes.
*Poner el nodo analizado en la lista de cerrados.
El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad, mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia el camino en la búsqueda cada vez que existen nodos más prometedores.
==Fuentes==

*Fernández, M. O. (2003). "Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los videos juegos"

[[Category:Algoritmos]]

Búsqueda de caminos

2011-09-07T13:38:39Z

Yrosario06: /* Breve reseña histórica */

{{Normalizar}}
{{Definición
|nombre=
|imagen=
|tamaño=
|concepto=
}}'''Búsqueda de caminos'''. Los algoritmos de búsqueda de caminos son usados para encontrar una ruta de navegación entre un punto de inicio y otro objetivo. Esta ruta es generalmente un pequeño subconjunto del mundo.

== Breve reseña histórica ==
Con el gran avance que ha tenido el conocimiento del hombre a través del devenir de los años hay momentos que marcan pautas en el desarrollo de la [[Inteligencia Artificial]], fue en la década del 50 donde se utilizó este término y logró captar la atención de muchos para su posterior evolución. La Inteligencia Artificial atiende una rama muy importante y ésta es la búsqueda de caminos.
Las raíces de los algoritmos de búsqueda de caminos hay que asociarlos a la constante evolución de los [[video-juegos]] ya que es una de las aplicaciones prácticas más interesantes en este entorno, son algoritmos por los cuales nuestro objetivo es capaz de eludir los obstáculos y llegar de un punto A a un punto B.
Es a partir de 1959 donde se empieza a buscar variantes para la problemática de la búsqueda de caminos en video-juegos, este proceso ha sido verdaderamente evolutivo ya que se comenzó con algoritmos como Dijkstra, también llamado algoritmo de caminos mínimos luego siguió el algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) éste fue introducido por primera vez en el año 1977 cuando Slate y Atkin presentaron un programa de ajedrez.
Con la constante optimización de los algoritmos de búsqueda aparece el algoritmo de búsqueda de caminos A*, éste fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
En Cuba comienza a lograrse un avance en este sentido, los video-juegos y simuladores son un campo reciente y por tanto, conllevan una simulación inteligente mucho más real y necesitan algoritmos más fuertes y de un nivel superior.

=== En entornos virtuales===
Una de las problemáticas más vistas en el mundo de los juegos es cómo encontrar el camino mínimo entre dos puntos, este estudio ha comenzado desde los métodos de búsqueda heurística tradicionales que en la mayoría de los casos son incapaces de resolver problemas donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido hasta los métodos de búsqueda heurística en tiempo real.
Existen algoritmos capaces de solucionar el problema de búsqueda de caminos de manera eficiente, mediante algoritmos de búsqueda heurística en tiempo real. Se presentan varios algoritmos que mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por etapa de planificación

== Aplicaciones de los algoritmos de búsqueda==
La investigación de algoritmos tanto exactos como heurísticos para resolver problemas de optimización tiene una vigencia inusualmente importante en estos días, de esta forma, actualmente es acuciante la necesidad de algoritmos muy eficientes que puedan dar respuesta en tiempo real a problemas del usuario o del sistema, y que permitan trabajar con los nuevos sistemas operativos y máquinas.
En el mundo de los video-juegos existen muchas aplicaciones para los algoritmos de búsqueda de caminos. Como todos sabemos una de las formas más comunes en las que se aplican estos algoritmos es en los juegos de estrategia y de rol, donde les decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de uno de estos algoritmos.
Los algoritmos de búsqueda de caminos tienen otras tantas aplicaciones muy útiles para el mundo actual, por ejemplo, algo que tiene mucho éxito en nuestros días son los GPS que poseen los carros de alta tecnología de hoy en día que se utilizan para ayudar al conductor a hallar caminos y sugerir los atajos o caminos más cortos. Esto resulta ser de gran utilidad para el turista que se encuentre en una cuidad desconocida para él.
En el mundo de la medicina también existen aplicaciones para estos algoritmos, los grandes programas hechos para realizar cirugías a pacientes están pensados para hallar el camino más corto y seguro considerando todos los factores como flujos sanguíneos, obstáculos y otros, para llegar a algún lugar decidido previamente por el cirujano dada una entrada. Parte importante de esta técnica está en la definición de la distancia heurística que debe recorrer.

== Conceptos para entender la búsqueda en árboles y grafos==
Para entender a cabalidad todo lo relacionado con los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda, por ejemplo, en problemas de este tipo se utiliza mucho el término búsqueda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

=== ¿Qué es búsqueda?===
Método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente.
En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

== Estructuras de datos para la búsqueda de camino==
En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

== Clasificación de algoritmos==
Según la búsqueda los algoritmos se pueden clasificar en dos clases:

=== Los métodos off-line===
Este método sigue el siguiente esquema, primero calculan el plan o ruta de mínimo coste de un problema mediante la búsqueda en el espacio de estados y luego ejecutan el plan realizando las acciones o secuencia de operaciones en el entorno. Este esquema, a menudo considerado de forma implícita, supone que ejecutar la solución en el mundo real es un proceso directo y no presenta ninguna dificultad, o sea, primero se realiza una búsqueda completa en el espacio de estados y luego se ejecuta una secuencia de acciones u operaciones en el entorno. En la siguiente figura se muestra su funcionamiento.
Un ejemplo típico de aplicación de los métodos off-line es la búsqueda de rutas. La búsqueda de rutas consiste en encontrar una ruta en un grafo desde el nodo inicial hasta el nodo objetivo.

=== Los métodos on-line===
En cambio, los métodos on-line intercalan planificación (mediante búsqueda local) y ejecución del plan mientras resuelven un problema. Debido a la propiedad on-line, los métodos tienen una gran flexibilidad para operar en entornos desconocidos y dinámicos. Además, no requieren conocer a-priori todo el espacio de estados, pueden adaptarse a objetos cambiantes y operar en entornos no determinados. Este modo de operación denominado on-line da lugar a los algoritmos de búsqueda en tiempo real. En la siguiente figura se representa el modo de operar de la búsqueda on-line.

== Criterios para evaluar las estrategias de búsqueda==
Cada algoritmo de búsqueda de caminos tiene una serie de características que lo identifican los cuales son:
*Completitud.
*Complejidad en tiempo.
*Complejidad en espacio.
*Optimización.

== Análisis de Algoritmos ==
=== Depth-First o Búsqueda en Profundidad (LIFO) ===
Esta búsqueda se centra en expandir un único camino desde la raíz. Siempre se expande el nodo más profundo en la frontera actual. En el caso de llegar a un “callejón sin salida” se retrocede hasta el nodo más cercano (siguiendo al nodo padre) donde se puede tomar una rama alternativa para poder seguir avanzando.
Se puede implementar, mediante el Algoritmo General, considerando la lista, como una pila (cuyas operaciones funcionan en forma LIFO). De esta manera el siguiente nodo a expandir siempre será el último que se haya colocado en la pila de ese nivel, garantizando esto que la expansión vaya aumentando en la profundidad de los nodos.
Es común aplicar esta estrategia mediante un algoritmo recursivo que recorra el árbol en Pre-Orden. Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos en cada nodo. De aquí surge otro importante algoritmo, “el backtracking”

=== Breadth-First search (búsqueda a lo ancho)===
La búsqueda en anchura (BFS o 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 todos los 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.
Este algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente, este algoritmo tiene como ventaja que, al expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.
Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables y que además requiere de mucha memoria.
Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante. Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.
La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

=== Búsqueda Bidireccional===
En la búsqueda bidireccional se llevan a la vez dos búsquedas, una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que los recorridos ascendente y descendente puedan encontrarse en algún momento. (Tener en cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsqueda bidireccional). Por lo demás este método no tiene ninguna dificultad, naturalmente, se podría realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial en profundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro.
Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

===Búsqueda de Profundidad Limitada===
Para evitar caer en caminos de profundidad muy grande, a la mayoría de los algoritmos que usan depth-first se les impone un límite de profundidad máxima. Por tanto es similar a la estrategia de Primero en Profundidad, pero se trata de eliminar el problema de que se puedan generar árboles “ilimitados”.
Para ello se establece un límite L a la profundidad del árbol. Todo nodo cuya profundidad sea L, no es expandido (se considera sin sucesores). El problema que puede pasar es si escogemos un valor de L menor que la profundidad del objetivo, en cuyo caso no llegaríamos a la solución. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo.

=== Algoritmo DFID (primero en profundidad con profundidad iterativa)===
El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) fue introducido por primera vez cuando Slate y Atkin presentaron un programa de ajedrez.
El algoritmo combina la estrategia de Primero en Profundidad con la de Profundidad Limitada, comenzando con límite igual a 0, aumentándolo de 1 en 1 hasta encontrar el objetivo. Combina las ventajas de las dos estrategias
Para asegurar el completamiento del algoritmo, el DFID introduce un límite de profundidad en cada una de sus iteraciones. El desarrollo del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda limitada en profundidad. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda

=== Backtracking Simple (Vuelta atrás) = Fuerza Bruta===
Backtracking es una versión de Depth-First. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. Es un método de búsqueda en profundidad que termina encontrando la primera solución sin embargo garantiza encontrar la solución de mínimo coste (óptima), el problema es el tiempo que toma en hacerlo. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor.
A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta) .Este método no utiliza información heurística para elegir el sucesor a expandir aunque existe una variante llamada Backtracking Ordenado que sí utiliza información heurística.
Es un método sistemático que itera a través de todas las combinaciones posibles del espacio de búsqueda. Es una técnica general que debe ser adaptada para cada aplicación particular.
El algoritmo backtracking se aplica en la implementación de los lenguajes de programación, tales como, lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores.

=== Búsqueda en Profundidad Branch and Bound (Ramificación y Límite)===
Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Este método imagina el espacio de búsqueda como un árbol de decisión, en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.
Branch and Bound procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar), se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cota, en ese caso, se descarta la rama completa.
Además de ramificar una solución padre (branch) en hijos, se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound), o sea, utiliza la poda para eliminar las ramas del árbol que no conducen a una solución óptima.
La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subárboles de descendientes costosos.
Puede seguir un recorrido en anchura (estrategia FIFO), profundidad (estrategia LIFO) o cálculo de funciones de coste para seleccionar el nodo más prometedor.
Es un algoritmo muy dependiente de la función heurística. En este algoritmo se manejan términos cómo:
*Nodos vivos, que no es más que un nodo factible y prometedor del que no se han generado todos sus hijos.
*Nodo muerto, es aquel del que no se generan más hijos porque ya se han generado todos sus hijos o no es factible ni prometedor.
*Nodo en expansión, es aquel del que se están generando todos sus hijos en ese instante.
El método funciona de la siguiente forma:
*Se selecciona un nodo del conjunto de nodos vivos.
*Se construyen los posibles nodos hijos del nodo seleccionado anteriormente
*Se eliminan algunos de los nodos creados anteriormente reduciendo así el espacio de búsqueda.
El método finaliza cuando se encuentra la solución o cuando se terminan los nodos vivos.

=== Algoritmo de Dijkstra===
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.
Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. Este algoritmo permite computar el camino de costo mínimo de un nodo dado al resto de los nodos de un grafo.
El algoritmo de Dijkstra utiliza una técnica de diseño de algoritmos conocida como greedy (también llamados algoritmos ávidos). Su correcto funcionamiento requiere que los costos asociados a los arcos sean no negativos.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, cuando se obtiene el camino más corto desde el vértice origen al resto de vértices que componen el grafo, el algoritmo se detiene.
El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

=== El algoritmo de búsqueda A*===
Se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
Este es un algoritmo de búsqueda de caminos para encontrar el camino más corto entre dos nodos, mientras intenta evitar obstáculos.
El algoritmo A* además de encontrar el nodo objetivo, nos asegura que es el camino más corto. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados.
En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la función f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.
El ciclo en el algoritmo A* consiste en:
*Buscar el nodo más prometedor.
*Analizar a sus nodos adyacentes.
*Poner el nodo analizado en la lista de cerrados.
El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad, mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia el camino en la búsqueda cada vez que existen nodos más prometedores.
==Fuentes==

Fernández, M. O. (2003). "Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los videos juegos"

[[Categoría:Informática]]

Búsqueda de caminos

2011-09-05T20:33:16Z

Yrosario06:

{{Definición
|nombre=
|imagen=
|tamaño=
|concepto=
}}'''Búsqueda de caminos'''. Los algoritmos de búsqueda de caminos son usados para encontrar una ruta de navegación entre un punto de inicio y otro objetivo. Esta ruta es generalmente un pequeño subconjunto del mundo.

== Breve reseña histórica ==
Con el gran avance que ha tenido el conocimiento del hombre a través del devenir de los años hay momentos que marcan pautas en el desarrollo de la [[Inteligencia Artificial]], fue en la década del 50 donde se utilizó este término y logró captar la atención de muchos para su posterior evolución. La Inteligencia Artificial atiende una rama muy importante y ésta es la búsqueda de caminos.
Las raíces de los algoritmos de búsqueda de caminos hay que asociarlos a la constante evolución de los [[video-juegos]] ya que es una de las aplicaciones prácticas más interesantes en este entorno, son algoritmos por los cuales nuestro objetivo es capaz de eludir los obstáculos y llegar de un punto A a un punto B.
Es a partir de 1959 donde se empieza a buscar variantes para la problemática de la búsqueda de caminos en video-juegos, este proceso ha sido verdaderamente evolutivo ya que se comenzó con algoritmos como Dijkstra, también llamado algoritmo de caminos mínimos luego siguió el algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) éste fue introducido por primera vez en el año 1977 cuando Slate y Atkin presentaron un programa de ajedrez.
Con la constante optimización de los algoritmos de búsqueda aparece el algoritmo de búsqueda de caminos A*, éste fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
En Cuba comienza a lograrse un avance en este sentido, los video-juegos y simuladores son un campo reciente y por tanto, conllevan una simulación inteligente mucho más real y necesitan algoritmos más fuertes y de un nivel superior.

=== En entornos virtuales===
Una de las problemáticas más vistas en el mundo de los juegos es cómo encontrar el camino mínimo entre dos puntos, este estudio ha comenzado desde los métodos de búsqueda heurística tradicionales que en la mayoría de los casos son incapaces de resolver problemas donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido hasta los métodos de búsqueda heurística en tiempo real.
Existen algoritmos capaces de solucionar el problema de búsqueda de caminos de manera eficiente, mediante algoritmos de búsqueda heurística en tiempo real. Se presentan varios algoritmos que mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por etapa de planificación
== Aplicaciones de los algoritmos de búsqueda==
La investigación de algoritmos tanto exactos como heurísticos para resolver problemas de optimización tiene una vigencia inusualmente importante en estos días, de esta forma, actualmente es acuciante la necesidad de algoritmos muy eficientes que puedan dar respuesta en tiempo real a problemas del usuario o del sistema, y que permitan trabajar con los nuevos sistemas operativos y máquinas.
En el mundo de los video-juegos existen muchas aplicaciones para los algoritmos de búsqueda de caminos. Como todos sabemos una de las formas más comunes en las que se aplican estos algoritmos es en los juegos de estrategia y de rol, donde les decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de uno de estos algoritmos.
Los algoritmos de búsqueda de caminos tienen otras tantas aplicaciones muy útiles para el mundo actual, por ejemplo, algo que tiene mucho éxito en nuestros días son los GPS que poseen los carros de alta tecnología de hoy en día que se utilizan para ayudar al conductor a hallar caminos y sugerir los atajos o caminos más cortos. Esto resulta ser de gran utilidad para el turista que se encuentre en una cuidad desconocida para él.
En el mundo de la medicina también existen aplicaciones para estos algoritmos, los grandes programas hechos para realizar cirugías a pacientes están pensados para hallar el camino más corto y seguro considerando todos los factores como flujos sanguíneos, obstáculos y otros, para llegar a algún lugar decidido previamente por el cirujano dada una entrada. Parte importante de esta técnica está en la definición de la distancia heurística que debe recorrer.

== Conceptos para entender la búsqueda en árboles y grafos==
Para entender a cabalidad todo lo relacionado con los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda, por ejemplo, en problemas de este tipo se utiliza mucho el término búsqueda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

=== ¿Qué es búsqueda?===
Método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente.
En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

== Estructuras de datos para la búsqueda de camino==
En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

== Clasificación de algoritmos==
Según la búsqueda los algoritmos se pueden clasificar en dos clases:

=== Los métodos off-line===
Este método sigue el siguiente esquema, primero calculan el plan o ruta de mínimo coste de un problema mediante la búsqueda en el espacio de estados y luego ejecutan el plan realizando las acciones o secuencia de operaciones en el entorno. Este esquema, a menudo considerado de forma implícita, supone que ejecutar la solución en el mundo real es un proceso directo y no presenta ninguna dificultad, o sea, primero se realiza una búsqueda completa en el espacio de estados y luego se ejecuta una secuencia de acciones u operaciones en el entorno. En la siguiente figura se muestra su funcionamiento.
Un ejemplo típico de aplicación de los métodos off-line es la búsqueda de rutas. La búsqueda de rutas consiste en encontrar una ruta en un grafo desde el nodo inicial hasta el nodo objetivo.

=== Los métodos on-line===
En cambio, los métodos on-line intercalan planificación (mediante búsqueda local) y ejecución del plan mientras resuelven un problema. Debido a la propiedad on-line, los métodos tienen una gran flexibilidad para operar en entornos desconocidos y dinámicos. Además, no requieren conocer a-priori todo el espacio de estados, pueden adaptarse a objetos cambiantes y operar en entornos no determinados. Este modo de operación denominado on-line da lugar a los algoritmos de búsqueda en tiempo real. En la siguiente figura se representa el modo de operar de la búsqueda on-line.

== Criterios para evaluar las estrategias de búsqueda==
Cada algoritmo de búsqueda de caminos tiene una serie de características que lo identifican los cuales son:
*Completitud.
*Complejidad en tiempo.
*Complejidad en espacio.
*Optimización.

== Análisis de Algoritmos ==
=== Depth-First o Búsqueda en Profundidad (LIFO) ===
Esta búsqueda se centra en expandir un único camino desde la raíz. Siempre se expande el nodo más profundo en la frontera actual. En el caso de llegar a un “callejón sin salida” se retrocede hasta el nodo más cercano (siguiendo al nodo padre) donde se puede tomar una rama alternativa para poder seguir avanzando.
Se puede implementar, mediante el Algoritmo General, considerando la lista, como una pila (cuyas operaciones funcionan en forma LIFO). De esta manera el siguiente nodo a expandir siempre será el último que se haya colocado en la pila de ese nivel, garantizando esto que la expansión vaya aumentando en la profundidad de los nodos.
Es común aplicar esta estrategia mediante un algoritmo recursivo que recorra el árbol en Pre-Orden. Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos en cada nodo. De aquí surge otro importante algoritmo, “el backtracking”

=== Breadth-First search (búsqueda a lo ancho)===
La búsqueda en anchura (BFS o 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 todos los 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.
Este algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente, este algoritmo tiene como ventaja que, al expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.
Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables y que además requiere de mucha memoria.
Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante. Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.
La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

=== Búsqueda Bidireccional===
En la búsqueda bidireccional se llevan a la vez dos búsquedas, una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que los recorridos ascendente y descendente puedan encontrarse en algún momento. (Tener en cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsqueda bidireccional). Por lo demás este método no tiene ninguna dificultad, naturalmente, se podría realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial en profundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro.
Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

===Búsqueda de Profundidad Limitada===
Para evitar caer en caminos de profundidad muy grande, a la mayoría de los algoritmos que usan depth-first se les impone un límite de profundidad máxima. Por tanto es similar a la estrategia de Primero en Profundidad, pero se trata de eliminar el problema de que se puedan generar árboles “ilimitados”.
Para ello se establece un límite L a la profundidad del árbol. Todo nodo cuya profundidad sea L, no es expandido (se considera sin sucesores). El problema que puede pasar es si escogemos un valor de L menor que la profundidad del objetivo, en cuyo caso no llegaríamos a la solución. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo.

=== Algoritmo DFID (primero en profundidad con profundidad iterativa)===
El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) fue introducido por primera vez cuando Slate y Atkin presentaron un programa de ajedrez.
El algoritmo combina la estrategia de Primero en Profundidad con la de Profundidad Limitada, comenzando con límite igual a 0, aumentándolo de 1 en 1 hasta encontrar el objetivo. Combina las ventajas de las dos estrategias
Para asegurar el completamiento del algoritmo, el DFID introduce un límite de profundidad en cada una de sus iteraciones. El desarrollo del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda limitada en profundidad. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda

=== Backtracking Simple (Vuelta atrás) = Fuerza Bruta===
Backtracking es una versión de Depth-First. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. Es un método de búsqueda en profundidad que termina encontrando la primera solución sin embargo garantiza encontrar la solución de mínimo coste (óptima), el problema es el tiempo que toma en hacerlo. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor.
A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta) .Este método no utiliza información heurística para elegir el sucesor a expandir aunque existe una variante llamada Backtracking Ordenado que sí utiliza información heurística.
Es un método sistemático que itera a través de todas las combinaciones posibles del espacio de búsqueda. Es una técnica general que debe ser adaptada para cada aplicación particular.
El algoritmo backtracking se aplica en la implementación de los lenguajes de programación, tales como, lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores.

=== Búsqueda en Profundidad Branch and Bound (Ramificación y Límite)===
Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Este método imagina el espacio de búsqueda como un árbol de decisión, en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.
Branch and Bound procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar), se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cota, en ese caso, se descarta la rama completa.
Además de ramificar una solución padre (branch) en hijos, se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound), o sea, utiliza la poda para eliminar las ramas del árbol que no conducen a una solución óptima.
La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subárboles de descendientes costosos.
Puede seguir un recorrido en anchura (estrategia FIFO), profundidad (estrategia LIFO) o cálculo de funciones de coste para seleccionar el nodo más prometedor.
Es un algoritmo muy dependiente de la función heurística. En este algoritmo se manejan términos cómo:
*Nodos vivos, que no es más que un nodo factible y prometedor del que no se han generado todos sus hijos.
*Nodo muerto, es aquel del que no se generan más hijos porque ya se han generado todos sus hijos o no es factible ni prometedor.
*Nodo en expansión, es aquel del que se están generando todos sus hijos en ese instante.
El método funciona de la siguiente forma:
*Se selecciona un nodo del conjunto de nodos vivos.
*Se construyen los posibles nodos hijos del nodo seleccionado anteriormente
*Se eliminan algunos de los nodos creados anteriormente reduciendo así el espacio de búsqueda.
El método finaliza cuando se encuentra la solución o cuando se terminan los nodos vivos.

=== Algoritmo de Dijkstra===
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.
Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. Este algoritmo permite computar el camino de costo mínimo de un nodo dado al resto de los nodos de un grafo.
El algoritmo de Dijkstra utiliza una técnica de diseño de algoritmos conocida como greedy (también llamados algoritmos ávidos). Su correcto funcionamiento requiere que los costos asociados a los arcos sean no negativos.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, cuando se obtiene el camino más corto desde el vértice origen al resto de vértices que componen el grafo, el algoritmo se detiene.
El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

=== El algoritmo de búsqueda A*===
Se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
Este es un algoritmo de búsqueda de caminos para encontrar el camino más corto entre dos nodos, mientras intenta evitar obstáculos.
El algoritmo A* además de encontrar el nodo objetivo, nos asegura que es el camino más corto. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados.
En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la función f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.
El ciclo en el algoritmo A* consiste en:
*Buscar el nodo más prometedor.
*Analizar a sus nodos adyacentes.
*Poner el nodo analizado en la lista de cerrados.
El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad, mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia el camino en la búsqueda cada vez que existen nodos más prometedores.
==Fuentes==

Fernández, M. O. (2003). "Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los videos juegos"

[[Categoría:Informática]]

Búsqueda de caminos

2011-09-05T20:32:13Z

Yrosario06: Página creada con '{{Definición |nombre= Búsqueda de caminos en entornos virtuales |imagen= |tamaño= |concepto= }}'''Búsqueda de caminos'''. Los algoritmos de búsqueda de caminos son usados p...'

{{Definición
|nombre= Búsqueda de caminos en entornos virtuales
|imagen=
|tamaño=
|concepto=
}}'''Búsqueda de caminos'''. Los algoritmos de búsqueda de caminos son usados para encontrar una ruta de navegación entre un punto de inicio y otro objetivo. Esta ruta es generalmente un pequeño subconjunto del mundo.

== Breve reseña histórica ==
Con el gran avance que ha tenido el conocimiento del hombre a través del devenir de los años hay momentos que marcan pautas en el desarrollo de la [[Inteligencia Artificial]], fue en la década del 50 donde se utilizó este término y logró captar la atención de muchos para su posterior evolución. La Inteligencia Artificial atiende una rama muy importante y ésta es la búsqueda de caminos.
Las raíces de los algoritmos de búsqueda de caminos hay que asociarlos a la constante evolución de los [[video-juegos]] ya que es una de las aplicaciones prácticas más interesantes en este entorno, son algoritmos por los cuales nuestro objetivo es capaz de eludir los obstáculos y llegar de un punto A a un punto B.
Es a partir de 1959 donde se empieza a buscar variantes para la problemática de la búsqueda de caminos en video-juegos, este proceso ha sido verdaderamente evolutivo ya que se comenzó con algoritmos como Dijkstra, también llamado algoritmo de caminos mínimos luego siguió el algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) éste fue introducido por primera vez en el año 1977 cuando Slate y Atkin presentaron un programa de ajedrez.
Con la constante optimización de los algoritmos de búsqueda aparece el algoritmo de búsqueda de caminos A*, éste fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
En Cuba comienza a lograrse un avance en este sentido, los video-juegos y simuladores son un campo reciente y por tanto, conllevan una simulación inteligente mucho más real y necesitan algoritmos más fuertes y de un nivel superior.

=== En entornos virtuales===
Una de las problemáticas más vistas en el mundo de los juegos es cómo encontrar el camino mínimo entre dos puntos, este estudio ha comenzado desde los métodos de búsqueda heurística tradicionales que en la mayoría de los casos son incapaces de resolver problemas donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido hasta los métodos de búsqueda heurística en tiempo real.
Existen algoritmos capaces de solucionar el problema de búsqueda de caminos de manera eficiente, mediante algoritmos de búsqueda heurística en tiempo real. Se presentan varios algoritmos que mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por etapa de planificación
== Aplicaciones de los algoritmos de búsqueda==
La investigación de algoritmos tanto exactos como heurísticos para resolver problemas de optimización tiene una vigencia inusualmente importante en estos días, de esta forma, actualmente es acuciante la necesidad de algoritmos muy eficientes que puedan dar respuesta en tiempo real a problemas del usuario o del sistema, y que permitan trabajar con los nuevos sistemas operativos y máquinas.
En el mundo de los video-juegos existen muchas aplicaciones para los algoritmos de búsqueda de caminos. Como todos sabemos una de las formas más comunes en las que se aplican estos algoritmos es en los juegos de estrategia y de rol, donde les decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de uno de estos algoritmos.
Los algoritmos de búsqueda de caminos tienen otras tantas aplicaciones muy útiles para el mundo actual, por ejemplo, algo que tiene mucho éxito en nuestros días son los GPS que poseen los carros de alta tecnología de hoy en día que se utilizan para ayudar al conductor a hallar caminos y sugerir los atajos o caminos más cortos. Esto resulta ser de gran utilidad para el turista que se encuentre en una cuidad desconocida para él.
En el mundo de la medicina también existen aplicaciones para estos algoritmos, los grandes programas hechos para realizar cirugías a pacientes están pensados para hallar el camino más corto y seguro considerando todos los factores como flujos sanguíneos, obstáculos y otros, para llegar a algún lugar decidido previamente por el cirujano dada una entrada. Parte importante de esta técnica está en la definición de la distancia heurística que debe recorrer.

== Conceptos para entender la búsqueda en árboles y grafos==
Para entender a cabalidad todo lo relacionado con los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda, por ejemplo, en problemas de este tipo se utiliza mucho el término búsqueda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

=== ¿Qué es búsqueda?===
Método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente.
En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

== Estructuras de datos para la búsqueda de camino==
En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

== Clasificación de algoritmos==
Según la búsqueda los algoritmos se pueden clasificar en dos clases:

=== Los métodos off-line===
Este método sigue el siguiente esquema, primero calculan el plan o ruta de mínimo coste de un problema mediante la búsqueda en el espacio de estados y luego ejecutan el plan realizando las acciones o secuencia de operaciones en el entorno. Este esquema, a menudo considerado de forma implícita, supone que ejecutar la solución en el mundo real es un proceso directo y no presenta ninguna dificultad, o sea, primero se realiza una búsqueda completa en el espacio de estados y luego se ejecuta una secuencia de acciones u operaciones en el entorno. En la siguiente figura se muestra su funcionamiento.
Un ejemplo típico de aplicación de los métodos off-line es la búsqueda de rutas. La búsqueda de rutas consiste en encontrar una ruta en un grafo desde el nodo inicial hasta el nodo objetivo.

=== Los métodos on-line===
En cambio, los métodos on-line intercalan planificación (mediante búsqueda local) y ejecución del plan mientras resuelven un problema. Debido a la propiedad on-line, los métodos tienen una gran flexibilidad para operar en entornos desconocidos y dinámicos. Además, no requieren conocer a-priori todo el espacio de estados, pueden adaptarse a objetos cambiantes y operar en entornos no determinados. Este modo de operación denominado on-line da lugar a los algoritmos de búsqueda en tiempo real. En la siguiente figura se representa el modo de operar de la búsqueda on-line.

== Criterios para evaluar las estrategias de búsqueda==
Cada algoritmo de búsqueda de caminos tiene una serie de características que lo identifican los cuales son:
*Completitud.
*Complejidad en tiempo.
*Complejidad en espacio.
*Optimización.

== Análisis de Algoritmos ==
=== Depth-First o Búsqueda en Profundidad (LIFO) ===
Esta búsqueda se centra en expandir un único camino desde la raíz. Siempre se expande el nodo más profundo en la frontera actual. En el caso de llegar a un “callejón sin salida” se retrocede hasta el nodo más cercano (siguiendo al nodo padre) donde se puede tomar una rama alternativa para poder seguir avanzando.
Se puede implementar, mediante el Algoritmo General, considerando la lista, como una pila (cuyas operaciones funcionan en forma LIFO). De esta manera el siguiente nodo a expandir siempre será el último que se haya colocado en la pila de ese nivel, garantizando esto que la expansión vaya aumentando en la profundidad de los nodos.
Es común aplicar esta estrategia mediante un algoritmo recursivo que recorra el árbol en Pre-Orden. Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos en cada nodo. De aquí surge otro importante algoritmo, “el backtracking”

=== Breadth-First search (búsqueda a lo ancho)===
La búsqueda en anchura (BFS o 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 todos los 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.
Este algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente, este algoritmo tiene como ventaja que, al expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.
Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables y que además requiere de mucha memoria.
Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante. Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.
La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

=== Búsqueda Bidireccional===
En la búsqueda bidireccional se llevan a la vez dos búsquedas, una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que los recorridos ascendente y descendente puedan encontrarse en algún momento. (Tener en cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsqueda bidireccional). Por lo demás este método no tiene ninguna dificultad, naturalmente, se podría realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial en profundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro.
Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

===Búsqueda de Profundidad Limitada===
Para evitar caer en caminos de profundidad muy grande, a la mayoría de los algoritmos que usan depth-first se les impone un límite de profundidad máxima. Por tanto es similar a la estrategia de Primero en Profundidad, pero se trata de eliminar el problema de que se puedan generar árboles “ilimitados”.
Para ello se establece un límite L a la profundidad del árbol. Todo nodo cuya profundidad sea L, no es expandido (se considera sin sucesores). El problema que puede pasar es si escogemos un valor de L menor que la profundidad del objetivo, en cuyo caso no llegaríamos a la solución. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo.

=== Algoritmo DFID (primero en profundidad con profundidad iterativa)===
El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) fue introducido por primera vez cuando Slate y Atkin presentaron un programa de ajedrez.
El algoritmo combina la estrategia de Primero en Profundidad con la de Profundidad Limitada, comenzando con límite igual a 0, aumentándolo de 1 en 1 hasta encontrar el objetivo. Combina las ventajas de las dos estrategias
Para asegurar el completamiento del algoritmo, el DFID introduce un límite de profundidad en cada una de sus iteraciones. El desarrollo del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda limitada en profundidad. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda

=== Backtracking Simple (Vuelta atrás) = Fuerza Bruta===
Backtracking es una versión de Depth-First. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. Es un método de búsqueda en profundidad que termina encontrando la primera solución sin embargo garantiza encontrar la solución de mínimo coste (óptima), el problema es el tiempo que toma en hacerlo. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor.
A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta) .Este método no utiliza información heurística para elegir el sucesor a expandir aunque existe una variante llamada Backtracking Ordenado que sí utiliza información heurística.
Es un método sistemático que itera a través de todas las combinaciones posibles del espacio de búsqueda. Es una técnica general que debe ser adaptada para cada aplicación particular.
El algoritmo backtracking se aplica en la implementación de los lenguajes de programación, tales como, lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores.

=== Búsqueda en Profundidad Branch and Bound (Ramificación y Límite)===
Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Este método imagina el espacio de búsqueda como un árbol de decisión, en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.
Branch and Bound procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar), se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cota, en ese caso, se descarta la rama completa.
Además de ramificar una solución padre (branch) en hijos, se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound), o sea, utiliza la poda para eliminar las ramas del árbol que no conducen a una solución óptima.
La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subárboles de descendientes costosos.
Puede seguir un recorrido en anchura (estrategia FIFO), profundidad (estrategia LIFO) o cálculo de funciones de coste para seleccionar el nodo más prometedor.
Es un algoritmo muy dependiente de la función heurística. En este algoritmo se manejan términos cómo:
*Nodos vivos, que no es más que un nodo factible y prometedor del que no se han generado todos sus hijos.
*Nodo muerto, es aquel del que no se generan más hijos porque ya se han generado todos sus hijos o no es factible ni prometedor.
*Nodo en expansión, es aquel del que se están generando todos sus hijos en ese instante.
El método funciona de la siguiente forma:
*Se selecciona un nodo del conjunto de nodos vivos.
*Se construyen los posibles nodos hijos del nodo seleccionado anteriormente
*Se eliminan algunos de los nodos creados anteriormente reduciendo así el espacio de búsqueda.
El método finaliza cuando se encuentra la solución o cuando se terminan los nodos vivos.

=== Algoritmo de Dijkstra===
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista.
Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. Este algoritmo permite computar el camino de costo mínimo de un nodo dado al resto de los nodos de un grafo.
El algoritmo de Dijkstra utiliza una técnica de diseño de algoritmos conocida como greedy (también llamados algoritmos ávidos). Su correcto funcionamiento requiere que los costos asociados a los arcos sean no negativos.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, cuando se obtiene el camino más corto desde el vértice origen al resto de vértices que componen el grafo, el algoritmo se detiene.
El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

=== El algoritmo de búsqueda A*===
Se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística.
Este es un algoritmo de búsqueda de caminos para encontrar el camino más corto entre dos nodos, mientras intenta evitar obstáculos.
El algoritmo A* además de encontrar el nodo objetivo, nos asegura que es el camino más corto. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados.
En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la función f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.
El ciclo en el algoritmo A* consiste en:
*Buscar el nodo más prometedor.
*Analizar a sus nodos adyacentes.
*Poner el nodo analizado en la lista de cerrados.
El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad, mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia el camino en la búsqueda cada vez que existen nodos más prometedores.
==Fuentes==

Fernández, M. O. (2003). "Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los videos juegos"

[[Categoría:Informática]]