El problema de la mochila {Pre: ?i?1..n:peso[i]>0, ?i?1..n-1: benef[i]/peso[i]=benef[i+1]/peso[i+1]} función mochila(benef,peso:vectReal; cap:real) devuelve vectReal variables resto:real; i:entero; sol:vectReal principio para todo i en 1..n hacer sol[i]:=0.0 {inicializar solución} fpara; resto:=cap; {capacidad restante} i:=1; mq (i=n) and (peso[i]=resto) hacer sol[i]:=1; resto:=resto-peso[i]; i:=i+1 fmq; si i=n entonces sol[i]:=resto/peso[i] fsi; devuelve sol
constante n=… {número de objetos} tipo vectReal=vector[1..n] de real
Caminos mínimos Dado un grafo G=(V,E) etiquetado con pesos no negativos y un vértice distinguido v, calcular el coste del camino mínimo desde v al resto de vértices. 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 E.W. Dijkstra: “A note on two problems in connexion with graphs”, Numerical Mathematica, 1, pp. 269-271, 1959.
Caminos mínimos
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 un valor 8 en la posición w del vector indica que no hay ningún camino desde v a w
Caminos mínimos {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
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
Caminos mínimos 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
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:=8; para todo u en T hacer si D[u]=val ent w:=u; val:=D[u] fsi fpara; …
Caminos mínimos … T:=T-{w}; {se recalculan las nuevas dist. mínimas} para todo u en T hacer si D[w]+etiqueta(g,w,u) 
Caminos mínimos 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)
Caminos mínimos Mejoras en el tiempo de ejecución Si la representación es por listas de adyacencia, la fase de recálculo se ejecuta sólo a (a 
Caminos mínimos
Implementación: heap junto con un vector indexado por vértices TAD cpa {cola Prior. De Aristas} operaciones creaVacía: ? cpa ?(1) inserta: cpa vért etiq ? cpa ?(log n) primero: cpa ? (vért,etiq) ?(1) borra: cpa ? cpa ?(log n) sustit: cpa vért etiq ? cpa ?(log n) valor: cpa vért ? etiq ?(1) está?: cpa vért ? bool ?(1) vacía?: cpa ? bool ?(1) (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) <4,20> (Gp:) <3,75> (Gp:) <2,8> (Gp:) <5,60>
el valor 8 de la etiqueta significa que el vértice no está en la cola
Caminos mínimos función Dijkstra(g:grafo; v:vért) devuelve vector[vért] de etiq variables A:cpa; {cola de aristas con prior.} D:vector[vért] de etiq; u,w:vért; et,val:etiq principio creaVacía(A); para todo w en vért hacer inserta(A,w,etiqueta(g,v,w)) fpara; mq no esVacía(A) hacer :=primero(A); D[w]:=val; borra(A);
para todo en suc(g,w) hacer si está(A,u) entonces si val+et 
Caminos mínimos Coste temporal: inicialización: ?(nlog n) selección y supresión: ?(nlog n) bucle interno: examina todas las aristas del grafo y en el caso peor efectúa una sustitución por arista, por tanto: ?(alog n) • El coste total es:?((a+n)log n), luego es mejor que la versión anterior si el grafo es disperso. • Si el grafo es denso, el algoritmo original es mejor.
Caminos mínimos Ejercicio: cálculo de la secuencia de nodos que componen el camino mínimo si el camino mínimo entre v y w pasa por u, el camino mínimo entre v y u es un prefijo del camino mínimo entre v y w basta con devolver un vector C tal que C[w] contenga el nodo anterior en el camino mínimo de v a w (que será v si está directamente unido al nodo de partida o si no hay camino entre v y w) el vector debe actualizarse al encontrarse un atajo en el camino es necesario también diseñar un nuevo algoritmo para recuperar el camino a un nodo dado, que tendría como parámetro C
Árboles de recubrimiento de coste mínimo (minimum spanning trees, MST) Objetivo: dado un grafo, obtener un nuevo grafo que sólo contenga las aristas imprescindibles para una optimización global de las conexiones entre todos los nodos
Aplicación: problemas que tienen que ver con distribuciones geográficas conjunto de computadores distribuidos geográficamente en diversas ciudades de diferentes países a los que se quiere conectar para intercambiar datos, compartir recursos, etc.; se pide a las compañías telefónicas respectivas los precios de alquiler de líneas entre ciudades asegurar que todos los computadores pueden comunicar entre sí, minimizando el precio total de la red
MSTs Terminología: árbol libre (spanning tree): es un grafo no dirigido conexo acíclico todo árbol libre con n vértices tiene n-1 aristas si se añade una arista se introduce un ciclo si se borra una arista quedan vértices no conectados cualquier par de vértices está unido por un único camino simple un árbol libre con un vértice distinguido es un árbol con raíz árbol de recubrimiento de un grafo no dirigido y etiquetado no negativamente: es cualquier subgrafo que contenga todos los vértices y que sea un árbol libre árbol de recubrimiento de coste mínimo:es un árbol de recubrimiento yno hay ningún otro árbol de recubrimiento cuya suma de aristas sea menor
MSTs
Algoritmo de Prim (debido a Jarník) Aplica reiteradamente la propiedad de los árboles de recubrimiento de coste mínimo incorporando a cada paso una arista Se usa un conjunto U de vértices tratados y se selecciona en cada paso la arista mínima que une un vértice de U con otro de su complementario (Gp:) V. Jarník: “O jistém problému minimálním”, Práca Moravské Prírodovedecké Spolecnosti, 6, pp. 57-63, 1930. (Gp:) ? (Gp:) ? (Gp:) ?
R.C. Prim: “Shortest connection networks and some generalizations”, Bell System Technical Journal, 36, pp. 1389-1401, 1957.
MSTs {Pre: g es un grafo no dirigido conexo etiquetado no negativamente} función Prim(g:grafo) devuelve grafo variables U:cjtVért; gsol:grafo; u,v:vért; x:etiq principio creaVacío(gsol); U:={cualquier vértice}; mq U no contenga todos los vért. hacer seleccionar mínima t.q. u?U;v?U añade(gsol,u,v,x); U:=U?{v} fmq; devuelve gsol fin {Post: gsol?arm(g)} Coste: ?(na) (es decir, ?(n3) si el grafo es denso)
MSTs La versión previa puede refinarse hasta obtener un algoritmo en ?(n2), es decir, mejor que el anterior (a=n-1).
Se usa un vector arisMín, indexado por vértices, que contiene: si v?U: arisMín[v]= t.q. es la arista más pequeña que conecta v con un vértice w?U si v?U: arisMín[v]=
MSTs {Pre: g es un grafo no dirigido conexo etiquetado no negativamente} función Prim(g:grafo) devuelve grafo variables arisMín:vector[vért] de ; gsol:grafo; prim,mín,v,w:vért; x:etiq principio prim:=unVérticeCualquiera; arisMín[prim]:=; para todo v en vért hacer arisMín[v]:= fpara;
creaVacío(gsol); hacer n-1 veces mín:=prim; {centinela: arisMín[mín].et=8} para todo v en vért hacer :=arisMín[v]; si x 
MSTs … añade(gsol,mín,arisMín[mín].v, arisMín[mín].et); arisMín[mín]:=; paratodo en adyacentes(g,mín) hacer si(arisMín[v].v?v)y(x fsi fpara frepetir; devuelve gsol fin {Post: gsol?arm(g)}
MSTs Eficiencia temporal: inicialización: lineal en caso de matriz de adyacencia y cuadrática en caso de listas bucle principal: el bucle de selección: ?(n) el añadido de una arista al grafo: constante usando matriz, lineal usando listas el bucle de reorganización: con matriz de adyacencia: el cálculo de los adyacentes es ?(n) y el coste total queda ?(n2) con listas: el coste total es ?(a+n) Coste total: ?(n2), independientemente de la representación.
Coste espacial: ?(n) de espacio adicional.
MSTs
Algoritmo de Kruskal: Partiendo del árbol vacío, se selecciona en cada paso la arista de menor etiqueta que no provoque ciclo sin requerir ninguna otra condición sobre sus extremos. J.B. Kruskal: “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proceedings of the American Mathematical Society, 7, pp. 48-50, 1956.
MSTs {Pre: g es un grafo no dirigido conexo etiquetado no negativamente} función Kruskal(g:grafo) devuelve grafo variables gsol:grafo; u,v:vért; x:etiq principio creaVacío(gsol); mq gsol no sea conexo hacer seleccionar mínima no examinada; si no provoca ciclo entonces añade(gsol,u,v,x) fsi fmq; devuelve gsol fin {Post: gsol?arm(g)} Nota: componentes(gsol) devuelve el conjunto de componentes conexos de gsol. (?) Utilizar una cola con prioridades. (?)
Implementación eficiente: En cada momento, los vértices que están dentro de una componente conexa en la solución forman una clase de equivalencia, y el algoritmo se puede considerar como la fusión continuada de clases hasta obtener una única componente con todos los vértices del grafo. MSTs (Gp:) C (Gp:) E (Gp:) A (Gp:) B (Gp:) D (Gp:) 30 (Gp:) 50 (Gp:) 50 (Gp:) 60 (Gp:) 40 (Gp:) 40 (Gp:) 10 (Gp:) 20 (Gp:) C (Gp:) E (Gp:) A (Gp:) B (Gp:) D (Gp:) 3 (Gp:) 4 (Gp:) 1 (Gp:) 2
Evolución de las clases de equivalencia:
{[A],[B],[C],[D],[E]} ? {[A],[B],[C,D],[E]} ?
? {[A],[B],[C,D,E]} ? {[A,B],[C,D,E]} ?
? {[A,B,C,D,E]}
Se utiliza el TAD “relación de equivalencia” sobre los vértices
Implementación asintóticamente óptima: MF sets el coste de creaREV es lineal el coste de numClases es constante el coste de k ejecuciones combinadas de fusiona y clase es ?(k?(k,n)), lo cual es prácticamente constante, porque? es una función inversa de la función de Ackerman que crece MUY despacio (?(k,n)=4, para todos los valores de k y n “imaginables”) MSTs género rev {relac. de equiv. sobre vért.} operaciones creaREV: ? rev {cada vért. una clase} clase: rev vért ? nat fusiona: rev nat nat ? rev numClases: rev ? nat
MSTs {Pre: g es un grafo no dirigido conexo etiquetado no negativamente} función Kruskal(g:grafo) devuelve grafo variables T:cpa; gsol:grafo; u,v:vért; x:etiq; C:rev; ucomp,vcomp:nat principio creaREV(C); {cada vért. forma una clase} creaVacío(gsol); creaVacía(T); {se colocan todas las aristas en la cola} para todo v en vért hacer para todo en adyacentes(g,v) hacer inserta(T,v,u,x) fpara fpara; …
… mq numClases(C)>1 hacer {obtener y eliminar la arista mín.de la cola} :=primero(T); borra(T); {si la arista no provoca ciclo se añade a la solución y se fusionan las clases corresp.} ucomp:=clase(C,u); vcomp:=clase(C,v); si ucomp?vcomp entonces fusiona(C,ucomp,vcomp); añade(gsol,u,v,x) fsi fmq; devuelve gsol fin {Post: gsol?arm(g)} MSTs
Coste del algoritmo: las a inserciones consecutivas de aristas en la cola con prioridades dan ?(alog a); como a=n2:?(alog a)<=?(alog n2)=?(2alog n)=?(alog n) como mucho hay a consultas y supresiones de la arista mínima, el coste de la consulta es constante y el de la supresión es ?(log a); por ello, este paso queda en ?(alog n) averiguar cuántas clases hay en la relación de equivalencia es constante en el caso peor, la operación de fusión de clases se ejecuta n-1 veces y la operación de localizar la clase 2a veces; por tanto, el coste total es en la práctica ?(a) las n-1 inserciones de aristas quedan en ?(n) con matriz de adyacencia y ?(n2) con listas, aunque en el caso de las listas puede reducirse también a ?(n) si se elimina en la operación de añade la comprobación de existencia de la arista (el algoritmo de Kruskal garantiza que no habrán inserciones repetidas de aristas)
Coste total: ?(alog n) (menos que el algoritmo de Prim, aunque con mayor espacio adicional) MSTs
| Página siguiente |