Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Problemas de Decisión y Optimización (PPT) (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

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

Monografias.com

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.

Monografias.com

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

Monografias.com

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

Monografias.com

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;

Monografias.com

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)
Monografias.com

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)

Monografias.com

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
Monografias.com

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

Monografias.com

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
Monografias.com

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.

Monografias.com

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

Monografias.com

Á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

Monografias.com

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

Monografias.com

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.

Monografias.com

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)

Monografias.com

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]=

Monografias.com

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
Monografias.com

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)}

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.
(?)

Monografias.com

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]}

Monografias.com

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

Monografias.com

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;

Monografias.com


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

Monografias.com

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

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter