0votos

Amigos en Haskell

por josejuan hace 6 años

¡Quien ha borrado el desafío "Amigos de Facebook"! argh!, bueno, aquí pongo mi solución. El problema puede resolverse de una forma muy sencilla.

¿Cómo de cerca están dos personas de ser amigos?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
{-- 
  El problema puede resolverse eficientemente con un A* y heurísticas apropiadas. 
 
  De todos modos, hay una forma sencilla de resolverlo que aunque no sea tan eficiente 
  como un A* apropiado no es deficiente. 
 
  Consiste sencillamente en obtener todos los nodos entre el orígen y el destino, obtener 
  todas las combinaciones de ellos, ordenar por el nº de elementos y quedarse con el primero 
  que consiga que no sean 3-amigos. 
 
--} 
 
import Data.List 
 
-- Tomamos el primer que incumpla, ordenando las combinaciones por longitud 
dropFriends3 gs a b = 
  if (a, b) `elem` gs 
    then Nothing -- Imposible, son amigos del alma 
    else Just $ head $ dropWhile test $ sortBy ((.length).compare.length) $ variations $ adyacencies3internal gs a b 
  where test ds = [] /= adyacencies3internal (filter (\(x, y) -> not (x `elem` ds || y `elem` ds)) gs) a b 
 
-- Dado un único nodo, obtiene todos los nodos a distancia menor o igual que 3 saltos de aristas 
adyacencies3 gs n = nodes $ adyacencies gs $ adyacencies gs $ filter ((==n).fst) gs 
 
-- Obtiene la lista de nodos INTERNOS en un radio de 3 saltos de aristas desde 'a' yendo a 'b' 
-- siempre que 'b' sea accesible (si no es accesible, no hay camino a 3 saltos): 
adyacencies3internal gs a b = if b `elem` rs then filter (\n -> n /= a && n /= b) rs else [] 
  where rs = adyacencies3 gs a 
 
 
 
-- === funciones genéricas que pueden estar "por ahí" ========== 
 
-- Cambia la representación de los datos de entrada 
friends xs = filter (\(x, y) -> (ys!!y)!!x == 'Y') [(x, y) | x <- sz, y <- sz] 
  where ys = lines xs 
        sz = [0..(length.head) ys - 1] 
 
-- Dado un conjunto de aristas, retorna los nodos 
nodes gs = nub $ (map fst gs) ++ (map snd gs) 
 
-- Dado el grafo "gs", expande el grupo de las aristas "ps" incluyendo sus adyacentes 
adyacencies gs ps = nub $ ps ++ filter (flip elem (nodes ps).fst) gs 
 
-- Obtiene todas las combinaciones de los elementos (tomados de 0 en 0, de 1 en 1, ...y de n en n) 
variations [] = [[]] 
variations (x:xs) = (map (x:) xs') ++ xs' 
  where xs' = variations xs 
 
 
 
-- Algunos test 
 
test = "NYYNNNN\n" ++ 
       "YNYYNNN\n" ++ 
       "YYNYNNN\n" ++ 
       "NYYNYNN\n" ++ 
       "NNNYNYN\n" ++ 
       "NNNNYNY\n" ++ 
       "NNNNNYN" 
 
 
test1 = "NYYYYNNNN\n" ++ 
        "YNNNNYYYN\n" ++ 
        "YNNNNNNYN\n" ++ 
        "YNNNNNNYN\n" ++ 
        "YNNNNNNNY\n" ++ 
        "NYNNNNNNY\n" ++ 
        "NYNNNNNNY\n" ++ 
        "NYYYNNNNY\n" ++ 
        "NNNNYYYYN" 
 
-- Por ejemplo 
doTest = dropFriends3 (friends test) 0 3 -- deben eliminarse los nodos [1, 2] 
4 comentarios
0votos

Escrito por Javier J. hace 6 años

Una solución estupenda, sin embargo creo que ta,mbién podría solucionarse bien aplicando un clásico Dijsktra (casi seguro que lo he escrito mal) o un Floyd-Wharsall que es más sencillo de implementar y ya tienes la matriz de todos con todos.

Un saludo.
0votos

Escrito por josejuan hace 6 años

Dijkstra y Floyd, determinan el camino más corto de un vértice al resto.

Esa información es útil para determinar el conjunto de potenciales nodos necesarios a eliminar, pero no es suficiente, puesto que una vez eliminado el nodo, debes volver a recalcular las rutas mínimas (volver a lanzar un Dijkstra).

En mi solución, por simplicidad, conecto 3 veces las aristas a partir de uno sólo de los dos nodos iniciales. Usar Dijkstra mejoraría en el sentido que minimizaría el nº de nodos potenciales a eliminar (y por tanto el nº de variaciones), pero no lo haría más rápida (ni tan sencilla) la búsqueda en sí de los nodos.

Es por eso que puestos a hacer una solución eficiente, trataría de hacer un A* con una heurística adecuada, que permitiría rastrear las alternativas sin tener que recalcular el estado completo de la búsqueda.

Lo que no creo que pudiera eliminarse sin encontrar alguna propiedad global es el backtracking para seleccionar los nodos óptimos a eliminar, pero fíjate que precisamente la heurística del A* ayudaría enormemente a optimizar el branch&bound (eg. tratando de eliminar primero los nodos más conectados).
0votos

Escrito por Javier J. hace 6 años

Dijkstra es un A* con una heurística que siempre devuelve 0 (o, en su defecto, que no afecta a la hora de decidir el siguiente nodo a visitar) ;)

Un saludo.
0votos

Escrito por josejuan hace 6 años

No te confundas, la forma en la que puedes aplicar Dijkstra con la forma en la que puedes aplicar un A* adecuado no tienen nada que ver.

Que Dijkstra sea A* no implica que tu A* sea Dijkstra y ya te he mostrado porqué.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.