{"id":1973,"date":"2021-05-22T21:37:06","date_gmt":"2021-05-22T21:37:06","guid":{"rendered":"https:\/\/staging.aquilessolutions.com\/introduccion-a-la-programacion-con-restricciones-o-constraint-programming\/"},"modified":"2021-05-22T21:37:06","modified_gmt":"2021-05-22T21:37:06","slug":"introduccion-a-la-programacion-con-restricciones-o-constraint-programming","status":"publish","type":"post","link":"https:\/\/aquilessolutions.com\/es\/introduccion-a-la-programacion-con-restricciones-o-constraint-programming\/","title":{"rendered":"Introducci\u00f3n a la Programaci\u00f3n con Restricciones o \u201cConstraint Programming\u201d"},"content":{"rendered":"

La programaci\u00f3n con restricciones o\u00a0Constraint Programming<\/em>\u00a0es una herramienta valiosa para resolver diferentes tipos de problemas de optimizaci\u00f3n (especialmente problemas de programaci\u00f3n industrial). As\u00ed que hoy introduciremos algunas definiciones b\u00e1sicas y el modelo conceptual que hay detr\u00e1s.<\/p>\n

<\/p>\n

La\u00a0optimizaci\u00f3n con restricciones<\/strong>, o la programaci\u00f3n de restricciones (CP), es el nombre que se le da a la identificaci\u00f3n de soluciones factibles a partir de un conjunto muy grande de candidatos, donde el problema se puede modelar en t\u00e9rminos de restricciones arbitrarias. CP se basa en la viabilidad en lugar de la optimizaci\u00f3n y se centra en las restricciones o dominios variables en lugar de la funci\u00f3n objetivo.<\/p>\n

Diseccionaremos la soluci\u00f3n del ejemplo \u201c4 Queens Problem\u201d, que consiste en colocar cuatro reinas en un tablero de ajedrez de 4 x 4 para que no se puedan capturar entre s\u00ed, para demostrar los conceptos detr\u00e1s de CP. Comenzamos por traducir el problema a un modelo matem\u00e1tico con variables y restricciones. Luego, el\u00a0solver<\/em>\u00a0utiliza Propagaci\u00f3n y Retroceso (o\u00a0Backtracking<\/em>) para llegar a la soluci\u00f3n.<\/p>\n

Las\u00a0variables<\/strong>\u00a0representan algunas decisiones. Pueden contener cualquier valor incluido en su rango o dominio. En nuestro problema creamos variables para cada cuadro del tablero. Cada variable toma el valor 1 si una reina est\u00e1 presente en el cuadro dado, de lo contrario es 0.<\/p>\n

Las\u00a0restricciones<\/strong>\u00a0impiden que las variables tomen valores arbitrarios. No se pueden colocar dos reinas en la misma fila, la misma columna o la misma diagonal.<\/p>\n

Propagaci\u00f3n<\/strong>: las variables pueden tener valores diferentes, pero el\u00a0solver<\/em>\u00a0debe eliminar algunos de esos valores para mantener todas las variables compatibles con el modelo.<\/p>\n

Backtracking<\/strong>: de vez en cuando, el\u00a0solver<\/em>\u00a0est\u00e1 bloqueado porque intenta asignar algunos valores a algunas variables que simplemente no son posibles (o deseables) porque no respetan las restricciones. Debe replantearse sus elecciones anteriores y probar otros valores. El retroceso tambi\u00e9n se produce cuando el\u00a0solver\u00a0<\/em>encuentra una soluci\u00f3n, pero interesa continuar la b\u00fasqueda para encontrar otras soluciones.<\/p>\n

Veamos ahora c\u00f3mo el\u00a0solver<\/em>\u00a0de CP llega a la soluci\u00f3n para nuestro problema:<\/p>\n

1. Podr\u00eda comenzar colocando a la Reina en la esquina superior izquierda, con lo que la variable correspondiente se asigna a 1. La propagaci\u00f3n de las restricciones har\u00eda que las dem\u00e1s variables de la fila superior, la columna izquierda y la diagonal principal se asignen a 0, porque ninguna otra Reina puede ocupar ya estas posiciones.<\/p>\n

<\/p>\n

2. Despu\u00e9s de algunos pasos, el solver<\/em>\u00a0puede encontrar la siguiente situaci\u00f3n:<\/span><\/p>\n

<\/p>\n

No es posible colocar a la Reina en la tercera columna sin violar las restricciones. Por lo tanto, debe retroceder y revisar su decisi\u00f3n anterior de colocar a la Reina en la tercera fila de la segunda columna. Eso es el\u00a0Backtracking<\/em>.<\/p>\n

3. Despu\u00e9s de varios ciclos de propagaci\u00f3n y resoluci\u00f3n, el\u00a0solver<\/em>\u00a0espera llegar a la soluci\u00f3n:<\/span><\/p>\n

Ahora veamos c\u00f3mo programar\u00edamos esta soluci\u00f3n usando\u00a0ConstraintSolver<\/strong>\u00a0de la biblioteca de\u00a0Google OR-Tools<\/strong>:<\/p>\n

var n\u00a0=\u00a04;\u00a0var solver\u00a0=\u00a0new Solver(\"N-Queens\");\u00a0\/\/ \/\/ Decision variables. q[i] row in i-th column where we place the queen \/\/ var q = solver.MakeIntVarArray(n, 0, n - 1, \"q\"); \/\/ \/\/ Constraints \/\/ solver.Add(q.AllDifferent()); var q1 = new IntVar[n]; var q2 = new IntVar[n]; \/\/The following sets the constraint that no two queens can be on the same diagonal. for (int i = 0; i &lt; n; i++) { q1[i] = (q[i] + i).Var(); q2[i] = (q[i] - i).Var(); } solver.Add(q1.AllDifferent()); solver.Add(q2.AllDifferent()); \/\/ \/\/ Search \/\/ var db = solver.MakePhase(q, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); solver.NewSearch(db); var s = 1; while (solver.NextSolution()) { Console.WriteLine($\"Solution {s++}: \"); for (int i = 0; i &lt; n; i++) { Console.Write(\"{0} \", q[i].Value()); } Console.WriteLine(string.Empty); } solver.EndSearch();<\/code><\/div>\n

En este ejemplo, se han utilizado 4 variables, una por fila, que pueden adoptar valores entre 0 y 3, indicando la columna d\u00f3nde se colocar\u00eda la Reina.<\/p>\n

Y el resultado es:<\/p>\n

Soluci\u00f3n 1<\/strong>: 1 3 0 2<\/p>\n

Soluci\u00f3n 2<\/strong>: 2 0 3 1<\/p>\n

B\u00e1sicamente, eso es todo. \u00a1Feliz programaci\u00f3n!<\/p>\n","protected":false},"excerpt":{"rendered":"

La programaci\u00f3n con restricciones o\u00a0Constraint Programming\u00a0es una herramienta valiosa para resolver diferentes tipos de problemas de optimizaci\u00f3n (especialmente problemas de programaci\u00f3n industrial). As\u00ed que hoy introduciremos algunas definiciones b\u00e1sicas y el modelo conceptual que hay detr\u00e1s. La\u00a0optimizaci\u00f3n con restricciones, o la programaci\u00f3n de restricciones (CP), es el nombre que se le da a la identificaci\u00f3n […]<\/p>\n","protected":false},"author":1,"featured_media":1757,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[92],"tags":[94,93,95,96],"class_list":["post-1973","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-articulo","tag-aquiles-es","tag-articulo","tag-noticias","tag-tecnologia","minute_read-53"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/posts\/1973","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/comments?post=1973"}],"version-history":[{"count":0,"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/posts\/1973\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/media\/1757"}],"wp:attachment":[{"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/media?parent=1973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/categories?post=1973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aquilessolutions.com\/es\/wp-json\/wp\/v2\/tags?post=1973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}