Centro del universo (Nodo central de redes)

Ejercicio:

El número Bacon (por el actor Kevin Bacon) se define como la distancia mínima entre un actor y Kevin Bacon; dos actores que han trabajado juntos en la misma película tienen distancia uno; dos que no han trabajado juntos pero que han trabajado junto con un tercer actor tienen distancia dos, etc.

Este problema se puede modelar mediante un grafo dirigido (con una arista en cada sentido, puesto que “haber trabajado con” es, evidentemente, una relación conmutativa) y ponderado. El peso de todas las aristas es 1. Cada vértice es una cadena con el nombre del actor o actriz. Cuando existe arista entre dos vértices quiere decir que ambos han actuado juntos en al menos una película. En lo que sigue consideraremos que el grafo es no dirigido. De la misma forma que se define el número Bacon podría haberse definido cualquier otro; por ejemplo, el número Yola de un actor sería la distancia más corta (en el sentido enunciado anteriormente) entre Yola Berrocal y ese actor. Por ejemplo, Santiago Segura tiene número Yola 1 por haber trabajado junto a Yola Berrocal en “Torrente 2”. En este problema vamos a tratar de averiguar quién es el “Centro del Universo”. Para ello vamos a definir un nuevo concepto: se define la media de un actor x como la media de los números x de todos los demás actores y actrices. Por ejemplo, la media Bacon es la media de los números Bacon de todos los demás actores y actrices. Se puede suponer que cuanto más baja es la media de un actor, tanto más céntrico es (en el sentido Hollywood). De modo que se define el “Centro del Universo” como aquel actor o actriz con media más pequeña (puede haber varios). Esto es lo que queremos encontrar. Para ello escríbase un algoritmo que

a) convierta el grafo no dirigido etiquetado (ponderado) de entrada en la matriz de costes equivalente, creando dos Maps (funciones) auxiliares: una, que llamaremos indice que a cada nombre de actor/actriz le asocia el índice de la fila/columna que lo representa dentro de la matriz de costes; la otra la llamaremos nombre y hace corresponder a cada índice en la matriz el nombre correspondiente.

b) a partir de las funciones indice y nombre y de la matriz, encuentre y devuelva un conjunto con los nombres de los actores/actrices de menor media.

Notas:
- Supóngase que disponemos de métodos que implementan los algoritmos vistos en el tema Grafos; si hubiera varios con el mismo nombre, explíquese en un comentario cuál es el que se utiliza.
- Supóngase que el grafo es conexo.
Comentarios anecdóticos e intrascendentes: el día 27 de febrero de 2002 (estos números fluctúan con cada película que se estrena), Kevin Bacon tiene número Yola 3 (actuó con John Malkovich en “Queens Logic“ que a su vez actuó con Inés Sastre en “Beyond the clouds” que ha actuado con Yola Berrocal en “Torrente 2”). La media Bacon actual es 2,917; la media Yola es 3,780. El centro del universo es realmente el actor Christopher Lee (el mítico Drácula). Su media es 2,622940. En este momento se cuentan 498.374 actores/actrices enlazables (omitiendo los que trabajan exclusivamente en televisión) en la base de datos International Movie Data Base (imdb.com), por lo que la matriz de costes tendría 248.376.643.876 elementos: difícilmente se podría resolver por el método propuesto.

Una posible solución:

func centroDelUniverso(g:Graph) dev(actores:Set)
indice, nombre:Map
q: Entero[][]
i,j,k,m, min:Entero
itA,itB:Iterator
vVert,adj:Object

alg
nombre:=Map()
indice:=Map()
actores:=Set()
q:=< crea una matríz de Entero[0...g.size()-1,0...g.size()-1] inicializada a inf>

// Pasar de grafo a matriz de adyacencias
i:=0
j:=0
k:=0
itA:=g.vertices().iterator()
mientras itA.hasNext() //Recorremos todos los vertices del grafo
vVert:=itA.next()
si NO indice.containsKey(vVert) // Si no está en los maps añade al actor
indice.put(vVert,j)
nombre.put(j,Vvert)
j:=j+1
fsi
i:=indice.get(vVert)
q[i][i]:=0 // Del actor a si mismo 0 para que no influya en la media
itB:=g.getAdjacents(vVert).iterator() //Para todos los adyacentes hacer:
mientras itB.hasNext()
adj:=itB.next()
si NO indice.containsKey(adj) // Si no está en los maps añade al actor
indice.put(adj,j)
nombre.put(j,adj)
j:=j+1
fsi
k:=indice.get(adj)
q[i][k]:=1; //Poner distancia 1
fmientras
fmientras


//Algoritmo de Floyd
m := c.length -1
desde k := 0 hasta m
desde i := 0 hasta m
desde j := 0 hasta m
si q[i, k] + q[k, j] < q[i, j]:
q[i, j] := q[i, k] + q[k, j]
fsi
fdesde
fdesde
fdesde

// Resolucion problema

min:=inf
desde i:=0 hasta m //Para todos los actores
desde j:=0 hasta m //suma de las distancias al resto de actores
k:=k + q[i,j]
fdesde
si k < min // si las distancias son menores, es que la media es menor, por tanto elimina la lista
actores:=Set() // y empieza una con el actor que posee el mínimo hasta este momento.
actores.add(nombre.get(i))
min:=k // actualizamos k
| k=min
actores.add(nombre.get(i)) // Si tienen igual media, lo añadimos a la lista
fsi
fdesde
fin

Salida de un laberinto por búsqueda en profundidad

Ejercicio:

El problema del laberinto puede verse como una serie de habitaciones con puertas por las que se puede pasar a habitaciones adyacentes. La idea es que empezando por una habitación de entrada, hay que encontrar el camino que nos lleva a la habitación de salida. Para ello, de una habitación a otra sólo se puede pasar si hay una puerta entre las dos habitaciones. Todo esto se puede representar mediante un grafo. a) Indíquese cuáles serán los vértices, las aristas y qué tipo de grafo necesitaremos.

b) Escríbase un procedimiento que, tomando una habitación de entrada, otra de salida y el grafo representando el laberinto, escriba, si existe, las habitaciones que componen el camino desde la entrada a la salida. ¿En qué algoritmo se basa la solución propuesta?

Notas:
1. Si se usan estructuras auxiliares, justifíquese su uso.
2. Úsense todas las estructuras necesarias manipulándolas como TAD.
3. El camino resultante, si existe, se puede escribir tanto desde la entrada a la salida, como desde la salida a la entrada.
4. En el caso de que exista más de un camino desde la entrada a la salida, sólo se escribirá el primero que se encuentre.
5. Los vértices no tienen ningún tipo de información asociada, y no se puede modificar su estructura.

Una posible solución en pseudocódigo:

Los nodos son las habitaciones y las puertas las arístas. Necesitaremos un grafo no dirigido y no etiquetado ya que las puertas suponemos que se pueden abrir desde los dos lados.

clase SalidaLaberinto

proc SalidaLaberinto(u,dest: Object, g:Graph)
sol:List
visitados: Set
alg
sol:=List()
visitados:=Set()
si depthFirstSearchModified(u,dest,g,visitados,sol)
mostrar(sol)
| otros:
mostrar("No hay camino hacia la salida")
fsi
fin

func depthFirstSearchModified(u: Object, dest:Object, g: Graph; ent/sal visitados: Set, sol:List) dev(b:Boolean)
v: Object
adyacentes: Set
itd: Iterator
alg
b:=false
sol.add(u)
si u.equals(dest)
b:=true
|otros:
visitados.add(u)
adyacentes := g.getAdjacents(u)
itd := adyacentes.iterator()
mientras itd.hasNext() y no b
v := itd.next()
si no visitados.contains(v):// Equivalente a “si no visitado”
b:=depthFirstSearch(v, g, visitados, sol)
fsi
fmientras
si no b
sol.remove(u)
fsi
fsi
fin
finClase