0votos

Camino de Hamilton en Haskell

por josejuan usando GLPK hace 6 años

El enunciado no está muy bien planteado, porque se pide claramente un camino de hamilton, luego se ponen datos de un grafo direccional con pesos (que apunta al problema del viajante) y con una solución que es un ciclo (¿de viajante o de hamilton?). Se que se pide un algoritmo explícito, pero eso es más aburrido que buscar soluciones prácticas (como usar LPI :)

Resolver el problema del camino de Hamilton, por backtrack, ramifica y poda o cualquier otra técnica

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
-- 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 
 
{-- 
 
  Aquí soluciono el ciclo de hamilton. 
 
  Si se desea un camino de hamilton, es lanzar la solución 
  para todos los pares de vértices (compartan arista o no) hasta 
  ver si hacen ciclo. 
 
  Si se quiere el TSP (el del viajante), sólo hay que añadir el peso 
  de las aristas en la función a minimizar. 
 
  Es trivial resolverlo aplicando LPI porque las restricciones a 
  plantear son muy simples: "dos y sólo dos aristas por vértice". 
 
  En la práctica, con pocos datos podría valer LPI. Sino, un 
  algoritmo "eficiente" (exponencial en cualquier caso), es muy 
  difícil (véase http://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms). 
 
--} 
 
hamiltonianCycle :: [(Int, Int)] -> LP (Int, Int) Int 
hamiltonianCycle es = execLPM $ do mapM_ (\j -> equalTo (varSum (vertexEdges j)) 2) vertex 
                                   mapM_ (\v -> setVarKind v BinVar) es 
                                   setDirection Max 
                                   setObjective $ linCombination [(1, e) | e <- es] 
 
  where vertex = nub (map fst es ++ map snd es) 
        vertexEdges e = filter (\(a, b) -> a == e || b == e) es 
 
hamiltonianCycleSolver :: [(Int, Int)] -> IO (Maybe [(Int, Int)]) 
hamiltonianCycleSolver es = do 
  (status, solution) <- glpSolveVars (mipDefaults { msgLev = MsgErr }) $ hamiltonianCycle es 
  case status of 
    Success -> return . Just . map fst . M.toList . snd . fromJust $ solution 
    _       -> return Nothing 
1 comentario
0votos

Escrito por josejuan hace 6 años

Una tesis interesante hablando del tema

ftp://www.combinatorialmath.ca/g&g/chalaturnykthesis.pdf

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.