{"id":6711,"date":"2019-06-05T07:52:02","date_gmt":"2019-06-05T05:52:02","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6711"},"modified":"2019-06-09T07:52:36","modified_gmt":"2019-06-09T05:52:36","slug":"i1m2018-el-problema-del-calendario-mediante-busqueda-en-espacio-de-estado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-el-problema-del-calendario-mediante-busqueda-en-espacio-de-estado\/","title":{"rendered":"I1M2018: El problema del calendario mediante b\u00fasqueda en espacio de estado"},"content":{"rendered":"

En la tercera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han resuelto ejercicios de la relaci\u00f3n 47 sobre el problema del calendario mediante b\u00fasqueda en espacio de estado.<\/p>\n

Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n
\n<\/p>\n

\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El problema del calendario, para una competici\u00f3n deportiva en la que\n-- se enfrentan n participantes, consiste en elaborar un calendario de \n-- forma que: \n--    + el campeonato dure n-1 d\u00edas,\n--    + cada participante juegue exactamente un partido diario y\n--    + cada participante juegue exactamente una vez con cada adversario.\n-- Por ejemplo, con 8 participantes una posible soluci\u00f3n es\n--      | 1 2 3 4 5 6 7\n--    --+--------------\n--    1 | 2 3 4 5 6 7 8\n--    2 | 1 4 3 6 5 8 7\n--    3 | 4 1 2 7 8 5 6\n--    4 | 3 2 1 8 7 6 5\n--    5 | 6 7 8 1 2 3 4\n--    6 | 5 8 7 2 1 4 3\n--    7 | 8 5 6 3 4 1 2\n--    8 | 7 6 5 4 3 2 1\n-- donde las filas indican los jugadores y las columnas los d\u00edas; es\n-- decir, el elemento (i,j) indica el adversario del jugador i el d\u00eda j;\n-- por ejemplo, el adversario del jugador 2 el 4\u00aa d\u00eda es el jugador 6.\n-- \n-- El objetivo de esta relaci\u00f3n de ejercicios es resolver el problema\n-- del calendario mediante b\u00fasqueda en espacio de estados, utilizando las\n-- implementaciones estudiadas en el tema 23 que se pueden descargar desde \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/codigos\n--\n-- Las transparencias del tema 23 se encuentran en\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-23.pdf\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport I1M.BusquedaEnEspaciosDeEstados\nimport Data.Matrix\nimport Data.List\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir el tipo Calendario como una matriz de n\u00fameros\n-- enteros. \n-- ---------------------------------------------------------------------\n\ntype Calendario = Matrix Int\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n \n--    inicial :: Int -> Calendario\n-- tal que (inicial n) es el estado inicial para el problema del\n-- calendario con n participantes; es decir, una matriz de n fila y n-1\n-- columnas con todos sus elementos iguales a 0. Por ejemplo,\n--    ghci> inicial 4\n--    ( 0 0 0 )\n--    ( 0 0 0 )\n--    ( 0 0 0 )\n--    ( 0 0 0 )\n-- ---------------------------------------------------------------------\n\ninicial :: Int -> Calendario\ninicial n = zero n (n-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n \n--    sucesores :: Int -> Calendario -> [Calendario]\n-- tal que (sucesores n c) es la lista de calendarios, para el problema\n-- con n participantes, obtenidos poniendo en el lugar del primer\n-- elemento nulo de c uno de los posibles jugadores de forma que se\n-- cumplan las condiciones del problema. Por ejemplo,\n--    ghci> sucesores 4 (fromLists [[2,0,0],[0,0,0],[0,0,0]])\n--    [( 2 3 0 )\n--     ( 0 0 0 )\n--     ( 0 0 0 )\n--    ,( 2 4 0 )\n--     ( 0 0 0 )\n--     ( 0 0 0 )]\n--    ghci> sucesores 4 (fromLists [[2,3,0],[0,0,0],[0,0,0]])\n--    [( 2 3 4 )\n--     ( 0 0 0 )\n--     ( 0 0 0 )]\n--    ghci> sucesores 4 (fromLists [[2,3,4],[3,1,0],[0,0,0]])\n--    []\n-- ---------------------------------------------------------------------\n\nsucesores :: Int -> Calendario -> [Calendario]\nsucesores n c = \n    [setElem k (i,j) c |\n     k <- [1..n] \\\\ (i : [c!(k,j) | k <- [1..i-1]]\n                         ++ [c!(i,k) | k <- [1..j-1]])]\n    where (i,j) = head [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    esFinal :: Int -> Calendario -> Bool\n-- tal que (final n c) se verifica si c un estado final para el problema\n-- del calendario con n participantes; es decir, no queda en c ning\u00fan\n-- elemento igual a 0 (que es equivalente, por la manera de rellenar el\n-- calendario, a decir que el elemento de c en la posici\u00f3n (n,n-1) es\n-- distinto de 0). Por ejemplo, \n--    ghci> esFinal 4 (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,1]])\n--    True\n--    ghci> esFinal 4 (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,0]])\n--    False\n-- ---------------------------------------------------------------------\n\nesFinal :: Int -> Calendario -> Bool\nesFinal n c = c!(n,n-1) \/= 0\n            \n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    calendario :: Int -> [Calendario]\n-- tal que (calendario n) son las soluciones del problema del calendario,\n-- con n participantes, mediante el patr\u00f3n de b\u00fasqueda en espacio de\n-- estados. Por ejemplo, \n--    ghci> head (calendario 5)\n--    ( 2 3 4 5 )\n--    ( 1 4 5 3 )\n--    ( 4 5 1 2 )\n--    ( 5 2 3 1 )\n--    ( 3 1 2 4 )\n--    \n--    ghci> length (calendario 5)\n--    1344\n-- ---------------------------------------------------------------------\n\ncalendario :: Int -> [Calendario]\ncalendario n = buscaEE (sucesores n)\n                       (esFinal n)        \n                       (inicial n)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En la tercera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han resuelto ejercicios de la relaci\u00f3n 47 sobre el problema del calendario mediante b\u00fasqueda en espacio de estado. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[320],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6711"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=6711"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6711\/revisions"}],"predecessor-version":[{"id":6712,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6711\/revisions\/6712"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6711"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6711"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6711"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}