{"id":4255,"date":"2016-10-26T10:30:03","date_gmt":"2016-10-26T09:30:03","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=4255"},"modified":"2022-12-03T23:00:11","modified_gmt":"2022-12-03T22:00:11","slug":"programmation-par-contraintes-2","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones-2\/","title":{"rendered":"Programaci\u00f3n de restricciones"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"4255\" class=\"elementor elementor-4255\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1237a89 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1237a89\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-71e60e9\" data-id=\"71e60e9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-482af51 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"482af51\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Optimizaci\u00f3n combinatoria<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-10fe52f\" data-id=\"10fe52f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b1073ea elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b1073ea\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1353f05\" data-id=\"1353f05\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f08e62f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f08e62f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Programmation_par_contraintes\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2510f318 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2510f318\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-18b26da2\" data-id=\"18b26da2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-61f25901 elementor-widget elementor-widget-text-editor\" data-id=\"61f25901\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones-2\/#Programmation-par-contraintes\" >Programaci\u00f3n de restricciones<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones-2\/#Definition\" >Definici\u00f3n<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones-2\/#Resolution-naive-Generate-Test\" >Resoluci\u00f3n ingenua: generar y probar<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones-2\/#Resolution-par-backtrack\" >Resoluci\u00f3n de retroceso<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones-2\/#Resolution-par-propagation-de-contraintes\" >Resoluci\u00f3n por propagaci\u00f3n de tensiones<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Programmation-par-contraintes\"><\/span>Programaci\u00f3n de restricciones<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>los <a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones\/\">programaci\u00f3n de restricciones<\/a> resuelve problemas de toma de decisiones. Un problema de optimizaci\u00f3n se resuelve sucesivamente despu\u00e9s de varios problemas de decisi\u00f3n. Por ejemplo para determinar un <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">camino m\u00e1s corto<\/a>, buscaremos encontrar un camino de menos de 100 (posible), luego menos de 50 (imposible), luego menos de 75, etc. hasta encontrar la soluci\u00f3n \u00f3ptima. PPC tiene un campo de acci\u00f3n m\u00e1s amplio que los m\u00e9todos exactos o las metaheur\u00edsticas.<\/p>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Definition\"><\/span>Definici\u00f3n<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<p>PPC resuelve un problema de satisfacci\u00f3n de restricciones (CSP).<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Este \u00faltimo est\u00e1 definido por un triplete con X el conjunto de variables, D el conjunto de dominios y C el conjunto de restricciones. Domaine D<sub>I<\/sub> es el conjunto de valores posibles para la variable X<sub>I<\/sub>. Cada restricci\u00f3n C<sub>j<\/sub> se define por su aridad (el n\u00famero de variables con las que se relaciona), la lista de estas variables y el conjunto de tuplas que la satisfacen.<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p>Tomemos un ejemplo de triplete:<\/p>\n<ul style=\"text-align: justify;\">\n<li>variables: A, B, C, D<\/li>\n<li>\u00e1reas:\n<ul>\n<li>D<sub>PARA<\/sub> = {1,4,5,8}<\/li>\n<li>D<sub>B<\/sub> = {2,3,5,7,9}<\/li>\n<li>D<sub>VS<\/sub> = {4,8,9}<\/li>\n<li>D<sub>D<\/sub> = {1,4,5,7,9}<\/li>\n<\/ul>\n<\/li>\n<li>restricciones:\n<ul>\n<li>VS<sub>1<\/sub>(A, C): {(1,7); (1,9); (5,9); (8,9)}<\/li>\n<li>VS<sub>2<\/sub>(A, D): (1.1); (1.5); (5.5); (5.9); (8.9)}<\/li>\n<li>VS<sub>3<\/sub>(C, D): {(4.1); (8.1); (9.7)}<\/li>\n<li>VS<sub>4<\/sub>(B, D): {(2,7); (2,9); (5,8); (7,9); (9,9)}<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n\n<p>Es posible codificar las restricciones en extensi\u00f3n, por un conjunto de tuplas, o en intenci\u00f3n, utilizando operadores cuya sem\u00e1ntica es conocida. Una instanciaci\u00f3n es una asignaci\u00f3n completa de valores a variables, por ejemplo {<a> ,<b> , , }. La instanciaci\u00f3n es una soluci\u00f3n v\u00e1lida si se verifican los valores dados a las variables de las cuales, como todas las restricciones.<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Hablamos de instanciaci\u00f3n parcial o total (tome todas las variables o no), e inconsistente o consistente (valide las restricciones o no). Por tanto, una soluci\u00f3n v\u00e1lida es una instanciaci\u00f3n total y coherente.<\/div>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resolution-naive-Generate-Test\"><\/span>Resoluci\u00f3n ingenua: generar y probar<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">Generamos todas las asignaciones posibles. Luego verificamos si son consistentes, tan pronto como una asignaci\u00f3n sea consistente, tenemos una soluci\u00f3n v\u00e1lida.<\/div>\n\n<p>Si tenemos un problema con n variables, cada una solo puede tomar dos valores, el procesador hace 1,000,000,000 de c\u00e1lculos por segundo. Para 30 variables, la resoluci\u00f3n toma como m\u00e1ximo 1s, para 50 variables, pasamos a 11 d\u00edas; para 70 variables es necesario esperar 317 siglos.<\/p>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resolution-par-backtrack\"><\/span>Resoluci\u00f3n de retroceso<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">Generamos el \u00e1rbol de asignaciones y luego <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/recorrido-de-grafos\/\">viaje en profundidad<\/a>. Si una asignaci\u00f3n parcial (durante el recorrido) es incoherente, se corta el sub\u00e1rbol correspondiente.<\/div>\n\n<p>Es similar a Branch &amp; Cut.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-5084 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc1.png\" alt=\"programaci\u00f3n de restricciones de retroceso\" width=\"682\" height=\"435\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc1.png 682w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc1-300x191.png 300w\" sizes=\"(max-width: 682px) 100vw, 682px\" \/><\/figure>\n<\/div>\n\n<p>Este m\u00e9todo no genera todo el \u00e1rbol de posibilidades a diferencia del m\u00e9todo ingenuo. Por otro lado, todas las restricciones se prueban en cada asignaci\u00f3n parcial y el tiempo de convergencia tambi\u00e9n depende del orden de las variables.<\/p>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resolution-par-propagation-de-contraintes\"><\/span>Resoluci\u00f3n por propagaci\u00f3n de tensiones<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">Este m\u00e9todo consiste en propagar las restricciones en el dominio de las variables.<\/div>\n\n<p>Por ejemplo, tomemos x entre 0 y 10 e y entre 3 y 9; luego con la restricci\u00f3n x&gt; y podemos restringir el dominio de X entre 4 y 10.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"aligncenter wp-image-5093 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc2.png\" alt=\"propagaci\u00f3n de programaci\u00f3n de restricciones\" width=\"490\" height=\"326\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc2.png 490w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc2-300x200.png 300w\" sizes=\"(max-width: 490px) 100vw, 490px\" \/><\/figure>\n<\/div>\n\n<p>Hay tres casos en los que se propaga la informaci\u00f3n:<\/p>\n\n<ul class=\"wp-block-list\">\n<li>cuando se reduce un dominio<\/li>\n<li>cuando se cambia uno de los terminales de dominio<\/li>\n<li>cuando un dominio es un singleton.<\/li>\n<\/ul>\n\n<p>Entonces es posible propagar la informaci\u00f3n una vez (consistencia de nodo), dos veces (consistencia de arco) o m\u00e1s.<\/p>\n\n<p>En la consistencia de nodos, para cada variable X<sub>I<\/sub> no afectado en A, restamos de D<sub>Xi<\/sub> cualquier valor v tal que la asignaci\u00f3n A \u222a {(X<sub>I<\/sub>, v)} es inconsistente. Los valores autorizados se propagan en profundidad.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"aligncenter wp-image-5104 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc3.png\" alt=\"propagaci\u00f3n de programaci\u00f3n de restricciones\" width=\"502\" height=\"327\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc3.png 502w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc3-300x195.png 300w\" sizes=\"(max-width: 502px) 100vw, 502px\" \/><\/figure>\n<\/div>\n\n<p>En el arco-consistencia, para cada variable X<sub>I<\/sub> no afectado en A, restamos de D<sub>Xi<\/sub> cualquier valor v tal que haya una variable X<sub>j<\/sub> no asignado para el cual, para cualquier valor w de D<sub>Xj<\/sub>, la asignaci\u00f3n A \u222a {(X<sub>I<\/sub>, v); (X<sub>j<\/sub>, w)} es inconsistente. Los valores autorizados se propagan en profundidad.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-5112 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc4-300x142.png\" alt=\"propagaci\u00f3n de programaci\u00f3n de restricciones\" width=\"300\" height=\"142\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc4-300x142.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc4.png 760w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/figure>\n<\/div>\n\n<p>Cuanto mayor sea la tupla de comparaci\u00f3n, mayor ser\u00e1 el tiempo de c\u00e1lculo para definir el dominio v\u00e1lido de las variables. La consistencia del arco es menos eficiente que la consistencia del nudo si los dominios son grandes.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Optimizaci\u00f3n combinatoria P\u00e1gina de inicio de Wiki Programaci\u00f3n con restricciones La programaci\u00f3n con restricciones se utiliza para resolver problemas de toma de decisiones. Un problema de optimizaci\u00f3n se resuelve sucesivamente despu\u00e9s de... <\/p>","protected":false},"author":1,"featured_media":0,"parent":1770,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4255","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4255","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=4255"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4255\/revisions"}],"predecessor-version":[{"id":16644,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4255\/revisions\/16644"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1770"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=4255"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}