Caminos en un grafo

Definir las funciones

   grafo   :: [(Int,Int)] -> Grafo Int Int
   caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

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,

     ghci> grafo [(2,4),(4,5)]
     G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

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,

     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

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

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

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)

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)

2 Comentarios

Posiblemente, esta solución esté incorrecta. Me salen bastantes más caminos en la última prueba de todas.

import Data.List
import I1M.Grafo

-- grafo no dirigido definido por sus aristas
grafo   :: [(Int,Int)] -> Grafo Int Int
grafo xs = creaGrafo ND (a,b) [ (i,j,0) | (i,j) <- xs ]
    where ys = map fst xs ++ map snd xs
          (a,b) = (minimum ys, maximum ys)

-- lista los caminos en el grafo g desde a hasta b sin
-- pasar dos veces por el mismo nodo
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos g a b = aux a []
    where
        -- 'vs' es la lista de nodos visitados
        aux v vs
            | v == b    = [[b]]
            | otherwise = [ v:xs | c <- adyacentes g v,
                                   c `notElem` vs,
                                   xs <- aux c (c:vs)]

import Data.List

import I1M.Grafo

-- grafo no dirigido definido por sus aristas

grafo :: [(Int,Int)] -> Grafo Int Int

grafo xs = creaGrafo ND (a,b) [ (i,j,0) | (i,j) <- xs ]

where ys = map fst xs ++ map snd xs

(a,b) = (minimum ys, maximum ys)

-- lista los caminos en el grafo g desde a hasta b sin

-- pasar dos veces por el mismo nodo

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos g a b = aux a []

where

-- 'vs' es la lista de nodos visitados

aux v vs

| v == b = [[b]]

| otherwise = [ v:xs | c <- adyacentes g v,

c `notElem` vs,

xs <- aux c (c:vs)]

Falla en esta prueba:

ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
986410

1 2	ghci> length (caminos (grafo [(i,j) \| i <- [1..10], j <- [i..10]]) 1 10) 986410

Responder

Ésta es la versión corregida:

import Data.List
import I1M.Grafo

-- grafo no dirigido definido por sus aristas
grafo   :: [(Int,Int)] -> Grafo Int Int
grafo xs = creaGrafo ND (a,b) [ (i,j,0) | (i,j) <- xs]
    where ys = map fst xs ++ map snd xs
          (a,b) = (minimum ys, maximum ys)

-- lista los caminos en el grafo g desde a hasta b sin
-- pasar dos veces por el mismo nodo
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos g a b = aux a [a]
    where
        -- 'vs' es la lista de nodos visitados
        aux v vs
            | v == b    = [[b]]
            | otherwise = [ v:xs | c <- adyacentes g v,
                                   c `notElem` vs,
                                   xs <- aux c (c:vs)]

import Data.List

import I1M.Grafo

-- grafo no dirigido definido por sus aristas

grafo :: [(Int,Int)] -> Grafo Int Int

grafo xs = creaGrafo ND (a,b) [ (i,j,0) | (i,j) <- xs]

where ys = map fst xs ++ map snd xs

(a,b) = (minimum ys, maximum ys)

-- lista los caminos en el grafo g desde a hasta b sin

-- pasar dos veces por el mismo nodo

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos g a b = aux a [a]

where

-- 'vs' es la lista de nodos visitados

aux v vs

| v == b = [[b]]

| otherwise = [ v:xs | c <- adyacentes g v,

c `notElem` vs,

xs <- aux c (c:vs)]

Responder

Caminos en un grafo

Soluciones

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico