Búsqueda de caminos - Historial de revisiones

Carlos idict: Texto reemplazado: «
» por «»

2019-07-28T22:09:20Z

Texto reemplazado: «<div align="justify">» por «»

Elizabeth jc en 02:10 6 nov 2013

2013-11-06T02:10:46Z

Mostrar los cambios

Eglis jc en 17:01 6 abr 2013

2013-04-06T17:01:55Z

Yrosario06 en 15:01 5 dic 2011

2011-12-05T15:01:32Z

Yrosario06 en 15:04 7 nov 2011

2011-11-07T15:04:58Z

Cinformpri jc en 19:28 31 oct 2011

2011-10-31T19:28:28Z

Cinformpri jc en 14:42 22 sep 2011

2011-09-22T14:42:22Z

Arletisjcconsolacion en 16:15 20 sep 2011

2011-09-20T16:15:35Z

Yrosario06 en 14:15 7 sep 2011

2011-09-07T14:15:36Z

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

2011-09-07T13:38:39Z

‎Breve reseña histórica

@@ Línea 5: / Línea 5: @@
 |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.

@@ Línea 1: / Línea 1: @@
 {{Definición
 |nombre=Búsqueda de caminos
-|imagen=Arboles_Busqueda.JPG
+|imagen=Algortimo_de_busqueda1.JPG
 |tamaño=
 |concepto=Es la forma en que una entidad en movimiento encuentra un  camino alrededor de un obstáculo.

@@ Línea 1: / Línea 1: @@
-{{normalizar}}{{Definición
+{{Definición
 |nombre=Búsqueda de caminos
 |imagen=Arboles_Busqueda.JPG
@@ Línea 96: / Línea 96: @@
 *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.
+*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.

@@ Línea 10: / Línea 10: @@
 == 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.
+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.

@@ Línea 36: / Línea 36: @@
 == Clasificación de algoritmos==
 Según la búsqueda los algoritmos se pueden clasificar en dos clases:
@@ Línea 121: / Línea 122: @@
 ==Fuente==
-* Fernández, M. O. (2003). "Algoritmos de búsqueda   heurística en tiempo real. Aplicación a la navegación en los videos juegos"
+* 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]]

@@ Línea 4: / Línea 4: @@
 |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 ==
@@ Línea 45: / Línea 47: @@
 == 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.
+* Completitud.
-*Complejidad en tiempo.
+* Complejidad en tiempo.
-*Complejidad en espacio.
+* Complejidad en espacio.
-*Optimización.
+* Optimización.
-== Análisis de Algoritmos ==
+== Análisis de algoritmos ==
-=== Depth-First o Búsqueda en Profundidad (LIFO) ===
+=== 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.
@@ Línea 64: / Línea 66: @@
 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===
+=== 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===
+===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.
@@ Línea 78: / Línea 80: @@
 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 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.
@@ Línea 84: / Línea 86: @@
 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)===
+=== 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.
@@ Línea 117: / Línea 119: @@
 *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==
+==Fuente==
-*Fernández, M. O. (2003). "Algoritmos de búsqueda   heurística en tiempo real. Aplicación a la navegación en los videos juegos"
+* 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]]

@@ Línea 17: / Línea 17: @@
 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.