esquemas algorítmicos: introducción• solución voraz: algoritmo de dijkstra – para grafos...

Introducción a los esquemas algorítmicos

Estructuras de datos y algoritmos - Javier Campos (Universidad de Zaragoza) 1


Algoritmia = = tratamiento sistemático de

técnicas fundamentales para el diseño y análisis de algoritmos eficientes

Algoritmia


• Computadores cada vez más rápidos y a más bajo precio: – Se resuelven problemas

de cálculo antes impensables. – Inconscientemente se tiende a restar

importancia al concepto de eficiencia. • Existen problemas que seguirán siendo intratables si se

aplican ciertos algoritmos por mucho que se aceleren los computadores

importancia de nuevas soluciones eficientes


⇒



Esquemas algorítmicos más conocidos (exactos): • Divide y vencerás • Búsqueda con retroceso (backtracking) • Algoritmos voraces • Programación dinámica • Ramificación y poda • Programación lineal y reducciones • …

Y algunas heurísticas (aproximadas): • Algoritmos aproximados • Algoritmos probabilistas • Algoritmos bioinspirados (genéticos, enfriamiento simulado…) • …


Ejemplo: Divide y vencerás

C.A.R. Hoare: “Quicksort”, Computer Journal, 5(1), pp. 10-15, 1962.

procedimiento ordRápida(e/s T:vect[1..n]de dato; ent iz,de:1..n) {Ordenación de las componentes iz..de de T.} variable me:1..n principio si de-iz es pequeño entonces ordInserción(T,iz,de) sino divide(T,iz,de,me); {iz≤k<me ⇒ T[k]≤T[me] ∧ me<k≤de ⇒ T[k]>T[me]} ordRápida(T,iz,me-1); ordRápida(T,me+1,de) fsi fin


Ejemplo: Divide y vencerás procedim. divide(e/s T:vect[1..n]de dato; ent iz,de:1..n; sal me:1..n) {Permuta los elementos iz..de de T de forma que: iz≤me≤de, ∀k t.q. iz≤k<me: T[k]≤p, T[me]=p, ∀k t.q. me<k≤de: T[k]>p, p se llama pivote y es, por ejemplo, el valor inicial de T[iz]. } variables p:dato; k:1..n principio p:=T[iz]; k:=iz; me:=de+1; repetir k:=k+1 hasta que (T[k]>p)or(k≥de); repetir me:=me-1 hasta que (T[me]≤p); mq k<me hacer intercambiar(T[k],T[me]); repetir k:=k+1 hasta que T[k]>p; repetir me:=me-1 hasta que T[me]≤p fmq; intercambiar(T[iz],T[me]) fin


• Coste en el peor caso: cuadrático (si la elección del pivote no es adecuada, los subejemplares

no tienen tamaño parecido…)

• Coste promedio: O(n log n) (la constante multiplicativa es menor que en otros algoritmos

de ordenación cuyo coste en el caso peor es O(n log n), como el mergesort o el heapsort)

Ejemplo: Divide y vencerás


Ejemplo: Búsqueda con retroceso

• Problema: – Nos encontramos en una entrada de

un laberinto y debemos intentar atravesarlo.

– Representación: matriz de dimensión

n×n de casillas marcadas como libre u ocupada por una pared.

– Es posible pasar de una casilla a otra moviéndose sólamente en vertical u horizontal.

– Se debe ir de la casilla (1,1) a la casilla (n,n).


– Diseñaremos un algoritmo de búsqueda con retroceso de forma que se marcará en la misma matriz del laberinto un camino solución (si existe).

– Si por un camino recorrido se llega a una casilla desde la que es imposible encontrar una solución, hay que volver atrás y buscar otro camino.

– Además hay que marcar las casillas por donde ya se ha pasado para evitar meterse varias veces en el mismo callejón sin salida, dar vueltas alrededor de columnas…



• Estructura de datos: • Solución de búsqueda con retroceso:


tipos casilla = (libre,pared,camino,imposible) laberinto = vector[1..n,1..n] de casilla

procedimiento ensayar(ent x,y:entero; e/s lab:laberinto; sal encontrado:booleano) principio si (x<1)∨(x>n)∨(y<1)∨(y>n) entonces {posición fuera del laberinto} encontrado:=falso sino si lab[x,y]≠libre entonces encontrado:=falso sino ...

procedimiento buscarCamino(e/s lab:laberinto; sal éxito:booleano) principio ensayar(1,1,lab,éxito) fin


Inicializado a “libre” (lo que no es “pared”)


... lab[x,y]:=camino; si (x=n)∧(y=n) entonces {se ha encontrado una solución} encontrado:=verdad sino ensayar(x+1,y,lab,encontrado); si not encontrado entonces ensayar(x,y+1,lab,encontrado) fsi; si not encontrado entonces ensayar(x-1,y,lab,encontrado) fsi; si not encontrado entonces ensayar(x,y-1,lab,encontrado) fsi; si not encontrado entonces lab[x,y]:=imposible fsi fsi fsi fsi fin



• Cálculo del coste del camino mínimo desde un vértice dado al resto, en un grafo etiquetado con pesos no negativos

• Utilidad:

el grafo representa una distribución geográfica, donde las aristas dan el coste (precio, distancia...) de la conexión entre dos lugares y se desea averiguar el camino más corto (barato...) para llegar a un punto partiendo de otro

Ejemplo: Algoritmos voraces



• Solución voraz: Algoritmo de Dijkstra

– para grafos dirigidos (la extensión a no dirigidos es inmediata) – genera uno a uno los caminos de un nodo v al resto por orden creciente de

longitud – usa un conjunto de vértices donde, a cada paso, se guardan los nodos para los que

ya se sabe el camino mínimo – devuelve un vector indexado por vértices: en cada posición w se guarda el coste

del camino mínimo que conecta v con w – cada vez que se incorpora un nodo a la solución se comprueba si los caminos

todavía no definitivos se pueden acortar pasando por él – se supone que el camino mínimo de un nodo a sí mismo tiene coste nulo – valor ∞ en la posición w del vector indica que no hay ningún camino desde v a w

E.W. Dijkstra: “A note on two problems in connexion with graphs”, Numerical Mathematica, 1, pp. 269-271, 1959.



{Pre: g es un grafo dirigido etiquetado no neg.} función Dijkstra(g:grafo; v:vért) devuelve vector[vért] de etiq variables S:cjtVért; D:vector[vért] de etiq principio ∀w∈vért:D[w]:=etiqueta(g,v,w); D[v]:=0; S:={v}; mq S no contenga todos los vértices hacer {D contiene caminos mínimos formados íntegramente por nodos de S (excepto el último), y los nodos de S corresponden a los caminos mínimos más cortos calculados hasta el momento} elegir w∉S t.q. D[w] es mínimo; S:=S∪{w}; ∀u∉ S:actualizar dist.mín. comprobando si por w hay un atajo fmq; devuelve D fin {Post: D=caminosMínimos(g,v)}



• Corrección: – Puede demostrarse formalmente.

• Se presenta a continuación una implementación más detallada – Se utiliza en lugar de S su complementario T – Se supone que n es el número de vértices


{Pre: g es un grafo dirigido etiquetado no neg.} función Dijkstra(g:grafo; v:vért) devuelve vector[vért] de etiq variables T:cjtVért; D:vector[vért] de etiq; u,w:vért; val:etiq principio T:=∅; para todo w en vért hacer D[w]:=etiqueta(g,v,w); T:=T∪{w} fpara; D[v]:=0; T:=T-{v}; repetir n-2 veces {quedan n-1 caminos por determinar} {selección del mín.w: w∈T ∧ ∀u∈ T:D[w]≤D[u]} val:=∞; para todo u en T hacer si D[u]≤val ent w:=u; val:=D[u] fsi {siempre hay un nodo que cumple la condición} fpara; ...



... {se marca w como vértice tratado} T:=T-{w}; {se recalculan las nuevas dist. mínimas} para todo u en T hacer si D[w]+etiqueta(g,w,u)<D[u] ent D[u]:=D[w]+etiqueta(g,w,u) fsi fpara frepetir; devuelve D fin {Post: D=caminosMínimos(g,v)

Nota: el bucle principal se ejecuta n-2 veces porque el último camino queda calculado después del último paso (no quedan vértices para hallar atajos)



• Tiempo de ejecución: – se supone que las operaciones sobre cjtos. están implementadas en tiempo

constante, excepto la creación (p.ej., mediante un vector de booleanos) – fase de inicialización:

• creación del cjto. y ejecución n veces de diversas operaciones constantes: Θ(n) – fase de selección:

• las instrucciones del interior del bucle son Θ(1) • nº de ejecuciones del bucle:

1ª vuelta: se consultan n-1 vértices, 2ª vuelta: n-2, etc. (el cardinal de T decrece en 1 en cada paso)

nº de ejecuciones: n(n-1)/2-1 ⇒ Θ(n2) – fase de “marcaje”:

• n supresiones a lo largo del algoritmo: Θ(n) – fase de recálculo de las distancias mínimas:

• queda Θ(n2) por igual razón que la selección Coste total: Θ(n2)


Para saber más…

• Asignatura obligatoria “Inteligencia artificial” – Incluye un tema sobre “técnicas de búsqueda”, entre las que se encuentra

la búsqueda con retroceso y otras.

• Especialidad en Computación – Dos asignaturas obligatorias de especialidad:

• “Algoritmia básica”, incluye esquemas algorítmicos (exactos) • “Algoritmia para problemas difíciles”, incluye heurísticas (aproximadas)

– Asignaturas optativas sobre dominios punteros de aplicación: • Videojuegos • Robótica • Visión por computador • Bioinformática


esquemas algorítmicos: introducción• solución voraz: algoritmo de dijkstra – para grafos...

Documents