{"id":8262,"date":"2023-08-09T06:00:29","date_gmt":"2023-08-09T04:00:29","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8262"},"modified":"2023-08-03T12:33:33","modified_gmt":"2023-08-03T10:33:33","slug":"09-ago-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/09-ago-23\/","title":{"rendered":"El algoritmo de Prim del \u00e1rbol de expansi\u00f3n m\u00ednimo por escalada"},"content":{"rendered":"<p>El <a href=\"https:\/\/bit.ly\/466fwRe\">algoritmo de Prim<\/a> calcula un  recubridor m\u00ednimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un \u00e1rbol, incluyen todos los v\u00e9rtices y donde el valor de la suma de todas las aristas del \u00e1rbol es el m\u00ednimo.<\/p>\n<p>El algoritmo de Prim funciona de la siguiente manera:<\/p>\n<ul>\n<li>Inicializar un \u00e1rbol con un \u00fanico v\u00e9rtice, elegido arbitrariamente, del grafo.<\/li>\n<li>Aumentar el \u00e1rbol por un lado. Llamamos lado a la uni\u00f3n entre dos v\u00e9rtices: de las posibles uniones que pueden conectar el \u00e1rbol a los v\u00e9rtices que no est\u00e1n a\u00fan en el \u00e1rbol, encontrar el lado de menor distancia y unirlo al \u00e1rbol.<\/li>\n<li>Repetir el paso 2 (hasta que todos los v\u00e9rtices pertenezcan al \u00e1rbol)<\/li>\n<\/ul>\n<p>Usando la <a href=\"https:\/\/bit.ly\/3Kk4A99\">b\u00fasqueda en escalada<\/a> el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\n<\/pre>\n<p>tal que <code>prim g<\/code> es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo <code>g<\/code> calculado mediante el algoritmo de Prim con b\u00f1usqueda en escalada. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por<\/p>\n<pre lang=\"text\">\n   g1, g2, g3, g4 :: Grafo Int Int\n   g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                            (2,4,55),(2,5,32),\n                            (3,4,61),(3,5,44),\n                            (4,5,93)]\n   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                            (2,4,12),(2,5,32),\n                            (3,4,14),(3,5,44),\n                            (4,5,93)]\n   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,7),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,1),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n<\/pre>\n<p>entonces<\/p>\n<pre lang=\"text\">\n   prim g1 == [(2,4,55),(1,3,34),(2,5,32),(1,2,12)]\n   prim g2 == [(2,5,32),(2,4,12),(1,2,13),(1,3,11)]\n   prim g3 == [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)]\n   prim g4 == [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Escalada_Prim where\n\nimport BusquedaEnEscalada (buscaEscalada)\nimport TAD.Grafo (Grafo, Orientacion (ND), aristaEn, creaGrafo, nodos, peso)\nimport Data.Ix (Ix)\nimport Data.List (delete)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ng1, g2, g3, g4 :: Grafo Int Int\ng1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                         (2,4,55),(2,5,32),\n                         (3,4,61),(3,5,44),\n                         (4,5,93)]\ng2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                         (2,4,12),(2,5,32),\n                         (3,4,14),(3,5,44),\n                         (4,5,93)]\ng3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,7),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\ng4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,1),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\n\n-- Una arista esta formada por dos v\u00e9rtices junto con su peso.\ntype Arista a b = (a,a,b)\n\n-- Un estado (Estado (p,t,r,aem)) est\u00e1 formado por el peso p de la\n-- \u00faltima arista a\u00f1adida el \u00e1rbol de expansi\u00f3n m\u00ednimo (aem), la lista t\n-- de nodos del grafo que est\u00e1n en el aem, la lista r de nodos del\n-- grafo que no est\u00e1n en el aem y el aem.\ntype Estado a b = (b,[a],[a],[Arista a b])\n\n-- (inicial g) es el estado inicial correspondiente al grafo g.\ninicial :: (Ix a, Num b, Ord b) => Grafo a b -> Estado a b\ninicial g = (0,[n],ns,[])\n  where (n:ns) = nodos g\n\n-- (esFinal e) se verifica si e es un estado final; es decir, si no\n-- queda ning\u00fan elemento en la lista de nodos sin colocar en el \u00e1rbol de\n-- expansi\u00f3n m\u00ednimo.\nesFinal :: Estado a b -> Bool\nesFinal (_,_,[],_) = True\nesFinal _          = False\n\n-- (sucesores g e) es la lista de los sucesores del estado e en el\n-- grafo g. Por ejemplo,\n--    \u03bb> sucesores g1 (0,[1],[2..5],[])\n--    [(12,[2,1],[3,4,5],[(1,2,12)]),\n--     (34,[3,1],[2,4,5],[(1,3,34)]),\n--     (78,[5,1],[2,3,4],[(1,5,78)])]\nsucesores\n  :: (Ix a, Num b, Eq b) => Grafo a b -> Estado a b -> [Estado a b]\nsucesores g (_,t,r,aem) =\n  [(peso x y g, y:t, delete y r, (x,y,peso x y g):aem)\n   | x <- t , y <- r, aristaEn g (x,y)]\n\nprim :: (Ix a, Num b, Ord b) => Grafo a b -> [Arista a b]\nprim g = sol\n  where [(_,_,_,sol)] = buscaEscalada (sucesores g)\n                                      esFinal\n                                      (inicial g)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    prim g1 `shouldBe` [(2,4,55),(1,3,34),(2,5,32),(1,2,12)]\n  it \"e2\" $\n    prim g2 `shouldBe` [(2,5,32),(2,4,12),(1,2,13),(1,3,11)]\n  it \"e3\" $\n    prim g3 `shouldBe` [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)]\n  it \"e4\" $\n    prim g4 `shouldBe` [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0043 seconds\n--    4 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import Optional\n\nfrom src.BusquedaEnEscalada import buscaEscalada\nfrom src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristaEn,\n                           creaGrafo, nodos, peso)\n\ng1 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((1,2),12),((1,3),34),((1,5),78),\n                 ((2,4),55),((2,5),32),\n                 ((3,4),61),((3,5),44),\n                 ((4,5),93)])\ng2 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((1,2),13),((1,3),11),((1,5),78),\n                 ((2,4),12),((2,5),32),\n                 ((3,4),14),((3,5),44),\n                 ((4,5),93)])\ng3 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),7),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\ng4 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),1),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\n\nArista = tuple[tuple[Vertice, Vertice], Peso]\n\n# Un nodo (Estado (p,t,r,aem)) est\u00e1 formado por el peso p de la \u00faltima\n# arista a\u00f1adida el \u00e1rbol de expansi\u00f3n m\u00ednimo (aem), la lista t\n# de nodos del grafo que est\u00e1n en el aem, la lista r de nodos del\n# grafo que no est\u00e1n en el aem y el aem.\nEstado = tuple[Peso, list[Vertice], list[Vertice], list[Arista]]\n\n# inicial(g) es el estado inicial correspondiente al grafo g.\ndef inicial(g: Grafo) -> Estado:\n    n, *ns = nodos(g)\n    return (0, [n], ns, [])\n\n# esFinal(e) se verifica si e es un estado final; es decir, si no\n# queda ning\u00fan elemento en la lista de nodos sin colocar en el \u00e1rbol de\n# expansi\u00f3n m\u00ednimo.\ndef esFinal(e: Estado) -> bool:\n    return e[2] == []\n\n# sucesores(g, e) es la lista de los sucesores del estado e en el\n# grafo g. Por ejemplo,\n#    \u03bb> sucesores(g1, (0,[1],[2,3,4,5],[]))\n#    [(12,[2,1],[3,4,5],[(1,2,12)]),\n#     (34,[3,1],[2,4,5],[(1,3,34)]),\n#     (78,[5,1],[2,3,4],[(1,5,78)])]\ndef sucesores(g: Grafo, e: Estado) -> list[Estado]:\n    (_,t,r,aem) = e\n    return [(peso(x, y, g),\n             [y] + t,\n             [x for x in r if x != y],\n             [((x,y),peso(x, y, g))] + aem)\n            for x in t for y in r if aristaEn(g, (x, y))]\n\ndef prim(g: Grafo) -> Optional[list[Arista]]:\n    r = buscaEscalada(lambda e: sucesores(g, e), esFinal, inicial(g))\n    if r is None:\n        return None\n    return r[3]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_prim() -> None:\n    assert prim(g1) == [((2,4),55),((1,3),34),((2,5),32),((1,2),12)]\n    assert prim(g2) == [((2,5),32),((2,4),12),((1,2),13),((1,3),11)]\n    assert prim(g3) == [((5,7),9),((2,3),7),((5,4),5),((6,5),3),((1,6),6),((1,2),5)]\n    assert prim(g4) == [((5,7),9),((5,4),5),((5,3),1),((6,5),3),((1,6),6),((1,2),5)]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_prim()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El algoritmo de Prim calcula un recubridor m\u00ednimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un \u00e1rbol, incluyen todos los v\u00e9rtices y donde el valor de la suma de todas las aristas del \u00e1rbol es el m\u00ednimo. El algoritmo de Prim funciona de la siguiente manera: Inicializar&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8262"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8262"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8262\/revisions"}],"predecessor-version":[{"id":8264,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8262\/revisions\/8264"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8262"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8262"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8262"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}