{"id":4879,"date":"2015-04-27T22:03:38","date_gmt":"2015-04-27T20:03:38","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4879"},"modified":"2015-05-15T12:37:47","modified_gmt":"2015-05-15T10:37:47","slug":"i1m2014-el-problema-del-calendario-mediante-busqueda-en-espacio-de-estado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-el-problema-del-calendario-mediante-busqueda-en-espacio-de-estado\/","title":{"rendered":"I1M2014: El problema del calendario mediante b\u00fasqueda en espacio de estado"},"content":{"rendered":"

En la primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 31 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 3. 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,3,0],[1,0,0],[0,1,0],[0,0,0]])\n--    [( 2 3 4 )\n--     ( 1 0 0 )\n--     ( 0 1 0 )\n--     ( 0 0 1 )]\n--    ghci> sucesores 4 (fromLists [[2,3,4],[1,0,0],[0,1,0],[0,0,1]])\n--    [( 2 3 4 )\n--     ( 1 4 0 )\n--     ( 0 1 0 )\n--     ( 0 2 1 )]\n-- ---------------------------------------------------------------------\n\nsucesores :: Int -> Calendario -> [Calendario]\nsucesores n c = \n    [setElem i (k,j) (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     c!(k,j) == 0]\n    where (i,j) = head [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. 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. 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 = null [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0]\n            \n-- ---------------------------------------------------------------------\n-- Ejercicio 5. 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 6)\n--    ( 2 3 4 5 6 )\n--    ( 1 4 5 6 3 )\n--    ( 5 1 6 4 2 )\n--    ( 6 2 1 3 5 )\n--    ( 3 6 2 1 4 )\n--    ( 4 5 3 2 1 )\n--    \n--    ghci> length (calendario 6)\n--    720\n--    ghci> length (calendario 5)\n--    0\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 primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 31 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":"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":[238],"tags":[244,270,305],"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\/4879"}],"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=4879"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4879\/revisions"}],"predecessor-version":[{"id":4895,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4879\/revisions\/4895"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4879"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4879"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4879"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}