0votos

longitud minima entre 20 ptos,python o sage en Haskell

por josejuan hace 4 años

Al estar conectados todos los puntos la mejor estrategia es usar un algoritmo voraz, pero es muy cómodo usar LPI para resolver este tipo de problemas.

¿Cuál es la conexion por cable de mínima longitud,entre las 20 ciudades más pobladas de Galicia?

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
-- Usando GLPK, http://www.gnu.org/software/glpk/  
import System.Environment (getArgs)  
import Data.List  
import Control.Monad  
import Data.LinearProgram  
import Data.LinearProgram.GLPK  
import qualified Data.Map as M  
import Data.Map ((!))  
import Data.Maybe  
import Control.Applicative 
 
data Edge = Edge { from :: !Int, to :: !Int, cost :: !Double } deriving (Eq, Ord, Show) 
 
tspCycle :: [Edge] -> LP Edge Double 
tspCycle es = execLPM $ do 
     
    let vs    = nub (map from es ++ map to es) 
        n     = maximum vs 
        n'    = fromIntegral n 
        u i   = Edge (-1) i 0 
        e i j = head $ filter (\e -> from e == i && to e == j) es 
 
    forM_ vs $ \j -> do 
        varSum [e i j | i <- vs, i /= j] `equalTo` 1                            -- sólo una arista de entrada 
        varSum [e j i | i <- vs, i /= j] `equalTo` 1                            -- y sólo otra de salida por cada vértice 
 
    forM_ [(i, j) | i <- [1..n], j <- [1..n], i /= j] $ \(i, j) -> 
        ( (var (u i) ^-^ var (u j)) ^+^ (n' *^ var (e i j)) ) `leqTo` (n' - 1)  -- no hay lazos internos (u1 < u2 < ... < un) 
 
    forM_ es     $ flip setVarKind BinVar 
    forM_ [1..n] $ flip setVarKind IntVar . u 
 
    setDirection Min 
    setObjective $ linCombination [(cost g, g) | g <- es]                       -- mínimo coste 
 
tspCycleSolver :: [Edge] -> IO (Maybe [Edge])  
tspCycleSolver es = do  
  (status, solution) <- glpSolveVars (mipDefaults { msgLev = MsgErr }) $ tspCycle es  
  case status of  
    Success -> return . fmap (filter ((>=0).from)) . Just . map fst . filter ((1==).snd) . M.toList . snd . fromJust $ solution  
    _       -> return Nothing 
 
 
 
 
 
-- leer ciudades y mostrar resultados 
data City = City { name :: !String, longitude :: !Double, latitude :: !Double } deriving Show 
 
readCities :: FilePath -> IO [City] 
readCities file = (map (\[n,o,a] -> City n (read o) (read a)) . map words . lines) <$> readFile file 
 
cities2edges :: [City] -> [Edge] 
cities2edges cs = [Edge a b d | let s = length cs - 1, a <- [0..s], b <- [0..s], a /= b, let d = distance (cs!!a) (cs!!b)] 
                  where distance (City _ u v) (City _ x y) = sqrt ((u - x)**2 + (v - y)**2) 
 
main = do 
 
  cities <- readCities "cities.gps" 
  Just cycle <- tspCycleSolver $ cities2edges cities 
  mapM_ (\(Edge a b c) -> putStrLn $ "FROM: " ++ name (cities!!a) ++ ", TO: " ++ name (cities!!b) ++ ", DISTANCE: " ++ show c) cycle 
  putStrLn $ "TOTAL DISTANCE: " ++ show (sum $ map cost cycle) 
 
 
{- 
 
josejuantsp$ time -f "%E, %M" ./tsp +RTS -N4 
FROM: Vigo, TO: Cangas, DISTANCE: 6.480368484368662e-2 
FROM: Corunha, TO: Culleredo, DISTANCE: 7.73179430384726e-2 
FROM: Orense, TO: Puenteareas, DISTANCE: 0.6622559822437993 
FROM: Lugo, TO: Orense, DISTANCE: 0.7406293294696424 
FROM: Santiago, TO: Ames, DISTANCE: 0.11637155772992817 
FROM: Pontevedra, TO: Santa_Eugenia, DISTANCE: 0.3691419840961195 
FROM: Ferrol, TO: Naron, DISTANCE: 2.9376660104239054e-2 
FROM: Naron, TO: Lugo, DISTANCE: 0.8035110550327543 
FROM: Villagarcia, TO: Santiago, DISTANCE: 0.35899862663985255 
FROM: Oleiros, TO: Ferrol, DISTANCE: 0.18415895187323886 
FROM: Carballo, TO: Arteixo, DISTANCE: 0.20281379098217106 
FROM: Arteixo, TO: Corunha, DISTANCE: 0.11477092407653053 
FROM: Redondela, TO: Vigo, DISTANCE: 0.11893974399354307 
FROM: Ames, TO: Carballo, DISTANCE: 0.3107929242223665 
FROM: Culleredo, TO: Cambre, DISTANCE: 4.752855726034601e-2 
FROM: Santa_Eugenia, TO: Villagarcia, DISTANCE: 0.23007466219957648 
FROM: Cangas, TO: Marin, DISTANCE: 0.14939995420926555 
FROM: Marin, TO: Pontevedra, DISTANCE: 6.911185910449825e-2 
FROM: Cambre, TO: Oleiros, DISTANCE: 4.810112645853582e-2 
FROM: Puenteareas, TO: Redondela, DISTANCE: 0.1477563868650358 
TOTAL DISTANCE: 4.845855704443602 
2:33.99, 22336 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.