algoritmos


Algoritmo de recorrido
Algoritmos De Recorrido Y Búsqueda En ciencias de la computación, A* es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas delos viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.) Peter Hart , Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International ) describieron por primera vez el algoritmo en 1968.Se trata de una extensión de la Edsger Dijkstra algoritmo de 1959 .A* consigue un mejorrendimiento tiempo usando heurística. Ejemplo Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino: Clave: verde: inicio, el azul: objetivo, de color anaranjado: visited Nota: En este ejemplo se utiliza una coma como separador decimal.










Definición de árbol

Unárbol es una estructura de datos, que puede definirse de forma recursiva como:

- Una estructura vacía o
- Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol comoun tipo de grafo (ver grafos): un árbol es un grafo acíclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta implementación.








Formas derepresentación

- Mediante un grafo:



Figura 1


- Mediante un diagrama en columnado:

a
b
d
c
e
f



En la computación se utiliza mucho una estructura de datos, que son los árboles binarios. Estos árboles tienen 0, 1 ó 2 descendientes como máximo. El árbol de la figura anterior es un ejemplo válido de árbol binario.

Nomenclatura sobre árboles

-Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.
- Rama: arista entre dos nodos.
- Antecesor: un nodo X es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.
- Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.
- Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado0, a tiene grado 2.
- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d
- Nodo interno: aquel que tiene al menos un descendiente.
- Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.
- Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.
- Anchura: esel mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

Aclaraciones: se ha denominado a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la raíz, y a y d los sucesores inmediatos de la raíz b. Sin embargo, en las implementaciones sobre uncomputador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.

Grafo
Grafo etiquetado con 6 vértices y 7 aristas.
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre...