Caminos en un grafo
Definir las funciones
|
1 2 |
grafo :: [(Int,Int)] -> Grafo Int Int caminos :: Grafo Int Int -> Int -> Int -> [[Int]] |
tales que
- (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,
|
1 2 |
ghci> grafo [(2,4),(4,5)] G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])]) |
- (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7) [[1,3,5,7],[1,3,7]] ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7) [[2,5,3,7],[2,5,7]] ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2) [[1,3,5,2],[1,3,7,5,2]] ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4 [] ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10) 109601 |
Soluciones
|
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 |
import Data.List (sort) import I1M.Grafo import I1M.BusquedaEnEspaciosDeEstados grafo :: [(Int,Int)] -> Grafo Int Int grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as] where ns = map fst as ++ map snd as m = minimum ns n = maximum ns -- 1ª solución -- =========== caminos :: Grafo Int Int -> Int -> Int -> [[Int]] caminos g a b = aux [[b]] where aux [] = [] aux ((x:xs):yss) | x == a = (x:xs) : aux yss | otherwise = aux ([z:x:xs | z <- adyacentes g x , z `notElem` (x:xs)] ++ yss) -- 2ª solución (mediante espacio de estados) -- ========================================= caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]] caminos2 g a b = buscaEE sucesores esFinal inicial where inicial = [b] sucesores (x:xs) = [z:x:xs | z <- adyacentes g x , z `notElem` (x:xs)] esFinal (x:xs) = x == a -- Comparación de eficiencia -- ========================= -- ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10) -- 109601 -- (3.57 secs, 500533816 bytes) -- ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10) -- 109601 -- (3.53 secs, 470814096 bytes) |