en otra ventana
Contents
1. Answer 2 Stable Model strategic budweiser Answer 3 Stable Model strategic panino Answer 4 Stable Model strategic budweiser strategic panino Answer 5 Stable Model strategic heineken Answer 6 Stable Model strategic heineken strategic panino Answer 7 Stable Model strategic budweiser strategic heineken Answer 8 Stable Model strategic budweiser strategic heineken strategic panino Answer 9 Stable Model strategic frutto Answer 10 Stable Model strategic budweiser strategic frutto DS MAS COMBINACIONES DE MODELOS Answer 63 Stable Model strategic saiwa strategic budweiser strategic heineken strategic frutto strategic panino Answer 64 Stable Model strategic saiwa strategic budweiser strategic heineken strategic frutto strategic barilla strategic panino False Para codificar este problema en Smodels cuyo planteamiento obliga a representarlo como disyuntivo se aplic la conversi n sugerida en su manual pero como se puede observar no gener los modelos correctos por lo que comprobamos la afirmaci n hecha por el equipo de DLV de que Smodels aun no soporta programaci n l gica disyuntiva 3 9 Otros problemas Existen en la literatura diversos problemas de optimizaci n que aunque no pudieron ser incluidos en el presente trabajo es importante mencionarlos En R3 5 se resuelven varios problemas que no son triviales como el encontrar una secuencia que minimice el tie2. Debe ser lo menor posible Escriba un programa gue calcule las posiciones de los k almacenes de forma gue la suma de la distancia total sea minimizada d posici n del almac n sirviendo al restaurante i i Este ejemplo fu implementado en A POL y DLV con la misma base de datos extensional Implementaci n en A POL R1 1 Enrique Corona focus location declare lt middle dom dom declare lt rest dom declare lt sumato dom dom dom declare lt cost dom dom declare lt best dom dom declare lt rdist dom dom restaurantDLV in n mero de restaurante y ubicaci n 15 2 6 3 12 4 19 5 20 6 27 dom 1 6 fill rest with examples fastfood restaurantDLV select location where best 3 6 middle X Y lt div add X Y 2 rdist I J lt abs rest I rest J cost I J lt sumato I J middle I J sumato I I K lt rdist I K sumato I J K lt add rdist I K sumato add I 1 J K 1td1 J best l DF 0 location I best 1 D lt cost 1 D middle 1 D M location M best I J lt add cost B J best sub I 1 sub B 1 middle B J M It I J le L B le B J dom B location M Salida gt apol examples fastfood fastfood pol location 2 location 4 location 6 El cambio en los datos para adecuarlos a los mismos que en DLV forz a modificar en A POL varios archivos Implementaci n en DLV R1 1 Enrique Corona maxint 27 res
3. Iparse d all bidders sm smodels 0 smodels version 2 27 Reading done Answer 1 Stable Model sel d not sel e not sel d not sel c not sel b not sel a min 56 False Duration 0 010 Aqu mostramos que usando diferentes opciones para lparse smodels muestra diferentes modelos resultantes Este comportamiento no es entendible ni aunque los dise adores explican que como el programa usa maximize sta sentencia provoca la alteraci n del orden de salida de los modelos pero el ltimo modelo siempre es el ptimo 3 6 M nimo rbol abarcador R3 4 Un rbol abarcador de un grafo es un subgrafo que contiene a todos los v rtices del grafo Un mismo grafo puede contener muchos rboles abarcadores Por ejemplo un grafo de 4 v rtices se ve as Q Q MI pd A 0 0 Este grafo tiene 16 rboles abarcadores algunos son 0 0 0 0 OF 0O 0 0 he ral ES A Ei dd 0 0 0 0 0 00 0 0 O o 0 O 0 0 o 0 Af K i A x x x XI fy ri fy XI oo 0 o 0 0 oF o El camino entre los v rtices del grafo tiene un valor puede llamarse peso o longitud El peso del rbol es la suma del peso de sus v rtices Para el caso anterior el peso total del arbol es 11 Obviamente diferentes rboles tienen diferentes longitudes El problema es encontrar el m nimo rbol abarcador esto es el rbol con menor longitud o peso y que cumpla con que todos los nodos son alcanzados bajo
4. Un licitador tiene permitido hacer una oferta por un conjunto de objetos que le interesen El subastador deber seleccionar un subconjunto de tales objetos de tal forma que obtenga el precio m ximo por ellos asegur ndose que no aceptar ofertas que contengan el mismo elemento ya que cada objeto puede venderse solamente una vez El n mero de objetos en total es 4 1 2 3 4 y las propuestas de los compradores son a b c d e donde a 1 2 3 24 esto significa que el comprador a esta interesado en los objetos 1 2 3 a un costo de 24 De la misma forma para el resto En resumen el problema es maximizar la ganancia total obtenida aceptando el mejor subconjunto de ofertas donde ninguna de ellas contengan el mismo objeto Implementaci n en DLV R3 3 PhD Chitta Baral http www baral us bookone Entrar en la liga code dlv auctions bid a in 1 a in 2 b in 3 c in 2 d in 1 e bid b bid c bid d bid e in 2 a inG a in 3 b in 4 0 in 3 d in 4 d in 4 e kReglas sel X v not_sel X bid X bid X bid Y sel X sel Y X Y in I X in L Y not sel a 24 1 not sel b 9 1 not sel c 8 1 not sel d 25 1 not sel e 15 1 Salida gt dlv nofacts bidders dl DLV build BEN May 16 2003 gcc 2 95 3 20010315 release Best model not sel a not_sel b not_sel c sel d not sel e Cost Weight Level lt 56 1 gt Se emplear
5. employee ld f Skill Salary in Id gt W Salida gt dlv nofacts teambuilding dl DLV build BEN Jun 26 2003 gcc 2 95 3 10 cygwin special out 10 in 20 in 30 out 40 in 50 out 60 3 8 Compa as estrat gicas Este problema es referenciado como complejo R2 9 y definido en R2 10 Se incluy porque como se menciona en el cap tulo 2 el equipo de DLV asegura que no se puede representar en Smodels Consiste en que existen ciertas compa as que controlan otras compa as cada una produce un conjunto de productos y cada uno de ellos puede ser producido a lo m s por dos compa as Nosotros tenemos que vender algunas compa as sin dejar de producir alg n producto por lo que se busca permanecer con el m nimo n mero de ellas A las compa as que pertenecen en al menos uno de tales conjuntos se les denomina estrat gicas Tambi n se le califica a una compa a como estrat gica si es controlada por otras compa as estrat gicas Por ejemplo ie V 77 Barilla N Pa Frutto Panino N N produced by controlled ie controlled by produced by Heineken Budweiser Implementaci n en DLV http www dbai tuwien ac at proj dlv produced by pasta barilla saiwa produced by tomatoes frutto barilla produced by wine barilla 0 produced by bread saiwa panino produced by beer heineken budweiser controlled by frutto barilla satwa 0 controlled by bu
6. 1 Enrique Corona focus take declare gt ks object tcost declare gt profit object declare gt sb object object select takel where ks 3 10 object 0 3 tcost 0 10 Base de datos extensional tama o o peso del objeto cost 0 0 cost 1 2 cost 2 7 cost 3 5 ganancia profit 0 gt 0 profit 1 gt 4 profit 2 gt 3 profit 3 gt 2 kReglas ks 0 K gt 0 cuando no se escoje un objeto en particular ks N K gt ks sub N 1 K le 1 N taxe1 N R cuando si se escoge un objeto en particular ks N K gt add profit N ks sub N 1 sub K X cost N X le X K le 1 N takel N K Recuperar que objetos se seleccionan take X1 Y takel X1 Y not take X2 Y X2 gt XI object X2 tcost Y cambios D M O sb N M gt sub N M object N object M take 1 Z takel 1 Z cost 1 R Z gt R take N X take1 N X sb N 1 M take1 M X1 tcost X tcost X1 object N object M XI lt X Salida gt apol examples knapsackConAset pol take 1 3 take 2 10 Este resultado nos muestra que los objetos que se llevan son el 1 y 2 sin sobrepasar la capacidad de la mochila que es de 10 Implementaci n en Smodels R3 3 Ch Baral http www baral us bookone Index of bookone code smodels temp knapsack2 sm 20 Mar 2003 item 1 3 ganancia weight val 1 4 weight val 2 3 weight val 3 2 tama o del objeto
7. las siguientes condiciones La ra z del rbol no debe tener ning n arco de entrada Cada nodo en el rbol debe tener solo un arco de entrada Implementaci n en DLV R1 6 http www dbai tuwien ac at proj dlv man MIN SPANNING TREE Usando weak constraints root a node a node b node c node d node e edge a b 4 edge a c 3 edge c b 2 edge c d 3 edge b e 4 edge d e 5 in tree X Y C v out tree X Y edge X Y C reached X La ra z del rbol no debe tener ning n arco de entrada root X in tree GO Cada nodo en el rbol debe tener solamente un arco de entrada in tree X Y C in tree Z Y C X Z Cada nodo en el grafo debe ser alcanzado esto es que pertenezca al rbol abarcador reached X root X reached Y reached X in tree X Y C node X not reached X in tree X Y C C 1 Salida gt dlv nofacts min sp txt DLV build BEN May 16 2003 gcc 2 95 3 20010315 release Best model f reached a out_tree a b in tree a c 3 reached b reached c in_tree b e 4 in_tree c b 2 in_tree c d 3 reached e reached d out_tree d e Cost Weight Level lt 12 1 gt El mismo ejemplo se implementa de nuevo pero ahora usando funciones de agregaci n Seg n los autores es una forma mas elegante de resolverlo sin usar reglas auxiliares y mejora la lectura y el entendimiento del problema ya que las funciones de agregacion son mas claras al usuar
8. n de las clausulas disyuntivas y el uso de maximize en lugar de weak constraints el resto del c digo es muy semejante Silvia del Carmen Serrano Ramos 118602 Miguel Angel Meza Morales 118749 Juan Islas Aparicio 119100 16 de marzo del 2004 root a node a node b node c node d node e edge a b 4 edge a c 3 edge c b 2 edge c d 3 edge b e 4 edge d e 5 weight edgel a b 4 weight edgel a c 3 weight edgel c b 2 weight edgel c d 3 weight edgel b e 4 weight edgel d e 5 edgel X Y in_tree X Y C edge X Y C in treel X Y in tree X Y C edge X Y C in tree X Y C edge X Y C reached X not not in tree X Y C not in tree X Y C edge X Y C reached X not in tree X Y C root X in_tree W X C edge W X C in _tree X Y C in tree Z Y C X Z edge X Y C edge Z Y C reached X root X reached Y reached X in_tree X Y C edge X Y C node X not reached X minimize fedgel X Y in treel X Y t hide edge X Y C hide in tree X Y C hide not in tree X Y C hide reached X hide root X hide node X Salida gt lparse d none arbolabarcadorAlumnos sm smodels 0 smodels version 2 27 Reading 45 A non domain condition predicate edgel done Answer 1 Stable Model edgel b e edgel c d edgel c b edgel a c in treel b e in_treel c d in treel c b in treel a c 1 min 0 False Duration 0 000 3 7 Formaci n de equipos R1 6
9. trabaja apropiadamente generando modelos vacios 3 3 Camino mas corto entre dos nodos de un grafo Supongamos que un grafo esta definido por predicados del tipo edge X Y C o arco X Y C donde C es la distancia positiva entre X y Y el problema es calcular la distancia mas corta entre dos nodos dados Este problema tiene una variedad de aplicaciones por ejemplo en electr nica comunicaciones o transporte donde es importante encontrar la mejor ruta entre dos ciudades dadas Implementaci n en A POL R1 1 Enrique Corona dominio que define a la funci n sh declare lt sh node node indica que testigo se recupera y muestra el camino m s corto desde a hasta c select way where sh X Y lt start X end Y base de datos extensional node a node b node c node d edge a b 1 edge b c 2 edge a d 4 edge d c 1 start a end c Vola siguiente cl usula de orden parcial obtiene la distancia por un camino directo sh X Y lt C edge X Y C way X Y obtiene la distancia por caminos alternativos pasando por otros nodos entre X y Y sh X Y lt add sh X Z sh Z Y edge X Z C Salida gt apol examples short2 pol sh a b 1 sh a c 3 sh a d 4 sh b c 2 sh d c 1 way a b way b c La salida nos muestra el peso del camino m s corto como sh a c 3 y tambi n observamos la caracter stica de A POL llamada recuperaci n de testigo que nos muestra la secuencia de los nodos
10. weight cost 1 2 weight cost 2 7 weight cost 3 5 in_sack X item X not not_in_sack X not in sack X item X not in_sack X val X item X in_sack X cost X item X in_sack X condl cost X item X 10 not cond1 maximize val X item X hide item X hide not in _sack X Salida gt lparse knapsackConAs sm smodels 0 smodels version 2 27 Reading done Answer 1 Stable Model in_sack 1 in_sack 2 condi min 2 False Duration 0 000 Number of choice points 2 Number of wrong choices 2 Number of atoms 19 Number of rules 20 Number of picked atoms 14 Number of forced atoms 0 Number of truth assignments 86 Size of searchspace removed 6 0 El modelo resultante es Stable Model in_sack 1 in_sack 2 que incluye a los objetos 1 y 2 cuya ganancia maxima es 7 El resto de la salida es informacion estadistica de la ejecuci n interna de smodels tal como False que indica al usuario que no hay mas modelos a ser calculados La implementaci n original en R3 3 ten a un error dificil de detectar la sentencia maximize estaba implementada como maximize val X item X y lo correcto es maximize val X item X La primera sentencia genera un resultado incorrecto porque usando llaves maximiza el numero total de items y usando corchetes maximiza la ganancia val de los objetos siendo esto ultimo lo que se busca en el ejemplo
11. Capitulo 3 Ejemplos En este cap tulo se presentar n diversos ejemplos implementados en los sistemas que abarcan el presente estudio Los tipos de problemas fueron seleccionados para mostrar las t cnicas de optimizaci n soportadas y las funciones de agregaci n incluidas Cuando decimos que soporten funciones de agregaci n nos referimos a aquellas operaciones aplicadas a conjuntos de elementos adici n conteo etc Para nosotros es importante que el problema sea resuelto m s como un problema de optimizaci n que de decisi n Un problema de optimizaci n contesta la pregunta cu l es la mejor soluci n Mientras que un problema de decisi n responde existe una soluci n con una cierta caracter stica R3 1 Por ejemplo para el caso del problema de la mochila binaria R3 2 se tiene el siguiente planteamiento Considera una mochila de capacidad C donde C es un entero positivo Sea n el n mero de objetos de tama o positivo 2 cada uno con una ganancia de p p Pn El problema de optimizaci n consiste en encontrar la ganancia m xima de cualquier subconjunto de objetos que llenen la mochila sin sobrepasar su capacidad El problema de decisi n es dado un n mero k hay un subconjunto de objetos que llenen la mochila y cuya ganancia total sea al menos k O de otra forma puede un valor de al menos V ser alcanzado sin exceder el costo C Por otra parte las versiones de los sistemas que fueron utilizadas p
12. Implementaci n en DLV R3 3 Uriel Alejandro Mtz Huitle declaraci n de los objetos y de sus caracter sticas nombre val costo obj a 4 2 obj b 3 7 obj c 2 5 definir la capacidad de mochila capacidad 10 formaci n de los posibles conjuntos de objetos para introducir en la Vomochila in sack X V C obj X V C not not in sach X V C not in sack X V C obj X V C not in_sack X V C midiendo que el valor total no sobre pase la capacidad de la mochila sl capacidad K sum C in_sack X V C lt K not sl maximizar el n mero de elementos dentro de la mochila o minimizar el n mero de elementos que no est n dentro de la mochila ie not in _sack X V C V 1 Salida gt dlv nofacts knapsackConAset dl DLV build BEN Jun 26 2003 gcc 2 95 3 10 cygwin special Best model in_sack a 4 2 in_sack b 3 7 not_in_sack c 2 5 s1 Cost Weight Level lt 2 1 gt Esta salida muestra la versi n de DLV usada el modelo resultante con los objetos 1 y 2 Observando los distintos c digos arriba mostrados intuitivamente se puede afirmar que la implementaci n en DLV es de las mas transparentes para entender incluso partiendo de que es casi una copia de la implementaci n en Smodels de hecho al programador se le dio como referencia el c digo en Smodels y la traducci n a DLV fue casi directa sin llegar a afirmar que sea la implementaci n ptima podemos decir que al menos es la que s
13. Un equipo de trabajo debe ser formado de un conjunto de empleados de acuerdo a las siguientes caracter sticas R1 El equipo constar solo de un n mero limite de empleados R2 Un equipo requerir de un m nimo de habilidades diferentes R3 La suma de los salarios de los miembros del equipo no excedera el presupuesto dado R4 El salario de cada empleado tiene un margen especificado RS El n mero de mujeres en el equipo tiene que alcanzar un n mero dado Este ejercicio ejemplifica el uso de funciones de agregaci n en DLV Se observa que stas funciones son usadas transparentemente y traducen directamente los requerimientos solicitados Implementaci n en DLV R1 6 employee 10 m 990 1000 employee 20 f 990 300 employee 30 m 980 400 employee 40 f 980 2000 employee 50 f 940 600 employee 60 m 940 600 the size of the team nEmp 3 the minimum number of different skills nSkill 3 maxSal 1500 minimum number of women minwomen 2 el presupuesto budget 2000 kReglas un empleado es incluido en el equipo o no in Id v out Id employee Id Sex Skill Salary ocubre las restricciones rl r5 nEmp N not count Id in Id N nSkill M not count Skill employee ld Sex Skill Salary in Id gt M budget B not sum Salary Id employee Id Sex Skill Salary in Id lt B maxSal M not fmax Salary employee Id Sex Skill Salary in Id lt M minwomen W not countild
14. ara realizar las pruebas de los ejemplos de ste cap tulo son e Smodels versi n 2 27 y Iparse versi n 1 0 13 e A POL versi n 1 0c y Java Runtime Environment JRE 1 4 2 e DLV versi n build BEN Jun 26 2003 gcc 2 95 3 10 cygwin special e Aset Solver versiones XSB 2 5 Okocim of March 11 2002 Setparse y aset versiones nicas construidas en 2001 Para m s informaci n consultar el Ap ndice A Finalmente para algunos de estos problemas se procedi a realizar un an lisis comparativo entre ellos 3 1 Mochila Binaria R1 1 La mochila binaria 0 1 knapsack es un problema t pico de programaci n din mica ste consiste en llenar una mochila con varios objetos cada objeto object tiene un peso weight y una ganancia profit or val el peso de los objetos escogidos no puede exceder la capacidad m xima de la mochila y la suma de sus ganancias debe ser ptima La formulaci n del problema es la siguiente 0 n 0U ks n k m x ks n 1 FE len profit n ks n 1 E weight n weight n lt ky1 lt nm Donde n es el n mero de objetos y amp es la capacidad de la mochila Con esta formulaci n no se recupera que objetos se seleccionan solo la ganancia ptima En A POL usando la caracter stica de recuperaci n de testigo es posible tambi n obtener los objetos Este ejemplo fue implementado en A POL Aset Solver Smodels y DLV con la misma base de datos extensional Implementaci n en A POL R1
15. are gt over1000 1d declare lt min none declare gt max none declare gt over1000aux dom declare gt over1000nr none declare gt salaryTotalAux dom declare gt salaryTotal none none void dom 0 10 Base de datos extensional id 1 id 2 id 3 id 4 id 5 name goofie name willy name woody name jerry name tom emp 1 goofie 1250 emp 2 willy 700 emp 3 woody 750 emp 4 jerry 900 emp 5 tom 1050 reglas Cual es el empleado que gana m s y cual gana menos over1000 1 gt S emp 1 E S ge S 1000 min void lt S emp 1 E S poor E S max void gt emp I E S rich E S select poor where min void select rich where max void over 1000aux I gt over1000aux sub I 1 over 1000aux I gt add over1000aux sub I 1 bool over1000 D over 1000nr void gt over1000aux 1 idl salaryTotalAux I gt salaryTotalAux sub I 1 salaryTotalAux I gt add salaryTotalAux sub I 1 S emp LE S salaryTotal void gt salaryTotalAux I id 1 Salida gt apol examples cartoon pol max void 1250 min void 700 over1000 1 1250 over 1000 5 1050 poor willy 700 rich goofie 1250 Implementaci n en DLV R1 6 emp 1 goofie 1250 emp 2 vvilly 700 emp 3 woody 750 emp 4 jerry 900 emp 5 tom 1050 Cuantos empleados de la compa a ganan mas de 1000 Aqui se usa count que regresa la cardinalidad de un conjunto al
16. como way a b way b c Implementaci n en DLV Pedro Alejandro Miranda V is117282 maxint 10 base extensional c a c b c c c d arco a b 1 arco b c 2 arco a d 4 arco d c 1 inicio a fin c base intensional minimo W min Z camino X Y Z VV inicio X fin Y camino X Y Z arco X Y Z camino X Y Z camino X W M camino W Y N X Y Z M N Salida gt dlv nofacts MasCorto dl DLV build BEN May 16 2003 gcc 2 95 3 20010315 release minimo 3 camino a b 1 camino a c 3 camino a c 5 camino a d 4 camino b c 2 camino d c 1 En este ejemplo tambi n nos muestra el camino desde a a c pero tambi n incluye otros caminos y para el caso que sean muchos nodos la salida mostrar a todos los caminos y muchas veces es dificil distinguir el que buscamos 3 4 La compa a Cartoon Co El siguiente ejemplo fue propuesto en el manual de usuario de DLV R1 6 y muestra el uso y sint xis de las funciones de agregaci n Los datos representan a los empleados de una compa a llamada Cartoons Co con su nombre n mero y salario Consiste en obtener Cuantos empleados de la compa a ganan mas de 1000 Cuanto gasta la compa a en salarios Cual es salario m nimo pagado Cual es salario m ximo pagado Cada empleado est representado por un hecho de la forma emp id name salary Implementaci n en A POL R1 1 Enrique Corona declare lt emp id name decl
17. cual se aplica over1000 LN emp I N S S gt 1000 over1000nr X count I over1000 I N X Avisar si un empleado gana mas de 1200 warnMeOver1200 count I emp I N S S gt 1200 gt 0 Se desea saber cuanto gasta la compa a en salarios Aqu se aplica sum salaryTotal X sum S emp I N S X Avisar si los gastos por salario exceden a 4500 warnSalUp sum S emp I N S gt 4500 Cual es el salario m nimo pagado entre todos los empleados Aqu se usa min que regresa el minimo valor de un conjunto lowest X min S emp I N S X Cual es el salario m ximo pagado max regresa el maximo valor de la variable dada en el conjunto de simbolos highest X max S emp I N S X Salida gt dlv nofacts cartoonco dl DLV build BEN Jun 26 2003 gcc 2 95 3 10 cygwin special over1000 1 goofie over 1000 5 tom over 1000nr 2 warnMeOver 1200 salaryTotal 4650 warnSalUp lowest 700 highest 1250 Por alguna raz n en la versi n mas reciente de A POL no muestra la salida completa aquella que incluya tanto el numero de empleados que ganan mas de 1000 y cuanto gasta la compa a en salarios No obstante el mismo c digo ejecutado en la versi n anterior del sistema apol 1 0b si genera el resultado correcto Podemos observar que el uso de las funciones de agregaci n en DLV es bastante intuitivo 3 5 Un problema de combinatoria subasta de objetos R3 3
18. dweiser heineken 0 0 controlled _by heineken saiwa 0 0 controlled by saiwa budweiser 0 0 As we want to produce X Y or Z must be strategic strategic Y v strategic Z produced by X Y Z VV is strategic if it is controlled by strategic companies X Y and Z strategic W controlled by VV X Y Z strategic X strategic Y strategic Z strategic 0 Salida gt dlv nofacts strategic05 dl DLV build BEN Jun 26 2003 gcc 2 95 3 10 cygwin special strategic barilla strategic panino strategic budweiser strategic barilla strategic saiwa strategic budweiser strategic barilla strategic panino strategic heineken strategic barilla strategic saiwa strategic heineken Implementaci n en Smodels produced by pasta barilla saiwa produced by tomatoes frutto barilla produced by vvine barilla 0 produced by bread saiwa panino produced by beer heineken budweiser controlled by frutto barilla saiwa 0 controlled by budweiser heineken 0 0 controlled _by heineken saiwa 0 0 controlled by saiwa budweiser 0 0 strategic Y strategic Z produced by X Y Z strategic W controlled by VV X Y Z strategic X strategic Y strategic Z strategic 0 hide produced by X Y Z hide controlled by VV X Y Z Salida gt Iparse d none strategic05 sm smodels 0 smodels version 2 27 Reading done Answer 1 Stable Model
19. e explica con mas claridad 3 2 FastFood Este problema de optimizaci n pertenece al archivo de problemas del International Collegiate Programming Contest de la ACM R1 1 y fue uno de los problemas del concurso regional del suroeste de Europa en 1998 El enunciado original es el siguiente traducido Una cadena de comida r pida tiene varios restaurantes a lo largo de una carretera y han decidido construir varios almacenes a lo largo de ella cada almac n puede ser ubicado en un restaurante y suministrar a varios restaurantes con los ingredientes necesarios Naturalmente estos almacenes deben ser colocados de tal forma que la distancia promedio entre un restaurante y su almac n designado se minimice Usted debe escribir un programa que calcule las posiciones ptimas y las asignaciones de los almacenes Para precisar esto el gerente de la cadena ha establecido las siguientes especificaciones Se le dar n las posiciones de n restaurantes a lo largo de la carretera donde d lt d2 lt lt dn estas son las distancias medidas desde las oficinas principales de la compa a que se encuentra en la misma carretera Tambi n se da un n mero k lt n como el n mero de almacenes a construir Los k almacenes se construir n en las ubicaciones de k diferentes restaurantes Cada restaurante sera asignado al almac n mas cercano del que sera abastecido Para minimizar los costos de envio la suma de la distancia total definida por 2 isl
20. io Implementaci n en DLV usando funciones de agregaci n R1 6 root a node a node b node c node d node e edge a b 4 edge a c 3 edge c b 2 edge c d 3 edge b e 4 edge d e 5 in tree X Y C v out_tree X Y edge X Y C La raiz del rbol no debe tener ningun arco de entrada root R not count X in_tree X R C 0 Cada nodo en el rbol debe tener solamente un arco de entrada esto esta mal porque contempla a todos los nodos por igual incluso la ra z edge _ Y C not count X in_tree X Y C 1 From Nicola Leone s mail should ensure that each non root node has precisely 1 incoming arc Cada nodo en el grafo debe ser alcanzado es decir asegurar que pertenece al rbol node Y not root Y not count X in_tree X Y C 1 in tree X Y C C 1 Salida gt dlv nofacts min spWITHAggregateFnc dl DLV build BEN May 16 2003 gcc 2 95 3 20010315 release Best model out_tree a b in_tree a c 3 in_tree b e 4 in_tree c b 2 in_tree c d 3 out tree d e Cost Veight Level lt 12 1 gt Este ejemplo fue tomado del tutorial de DLV pero en un primer intento no gener la salida correcta el error fue remitido a los dise adores del sistema quienes modificaron el c digo Implementaci n en Smodels La siguiente implementaci n fue realizada apoyandose en el c digo anterior de DLV como se puede observar los cambios solamente se refieren a la sustituci
21. mpo en el que un grupo de m sicos pertenecientes a una orquesta asistan a una sesi n de ensayo pero con espacios en donde no tocan sus instrumentos por lo que lo ideal ser a que llegaran en la primera pieza que intervienen y se vayan enseguida de tal forma que sus tiempos de espera sean los m nimos aqu se muestra como adaptar un problema con restricciones a un problema de optimizaci n otra variante es planear la filmaci n de una pel cula de tal forma que optimice los costos por mantener desocupado a los actores entre una escena y otra En R3 3 se pueden consultar varios ejercicios en DLV y Smodels que ejemplifican el uso de las funciones de agregaci n Entre estos se encuentra Computeagregation escrito en Smodels En general es posible que casi cualquier problema pueda ser convertido a su variante de optimizaci n por ejemplo el problema de Graph Colouring se plantea como el colorear el grafo con un m nimo n mero de colores mientras que la variante de decisi n es la m s com n decidir para un n mero particular de colores si es posible colorear el grafo ambos cumpliendo con la restricci n de que 2 nodos adyacentes no pueden tener el mismo color M s de estos pueden ser encontrados en R3 6 Para DLV otros problemas interesantes son Seating Problem y Traveling Sales Person disponibles en el manual de usuario 3 10 Observaciones generales Analizando los ejemplos anteriores podemos hacer algunas observaci
22. on weak constraints para obtener el valor ptimo Implementaci n en Smodels R3 3 Ch Baral page 402 http www baral us bookone Index of code smodels comb auc item 1 4 bid a b c d e in 1 a inG a in 3 a in 2 b in 3 b in 3 c in 4 c in 2 d in 3 d in 4 d in 1 e in d e weight sel a 24 vveight sel b 9 vveight sel c 8 weight sel d 25 weight sel e 15 sel X bid X not not sel X not sel X bid X not sel X two different bids with the same items can not be selected bid X bid Y sel OO sel Y not eq X Y item 1 in X in L Y Select the bids such that their total weight is maximized maximize sel X bid X hide bid X hide not_sel X hide item X hide in X Y Salida 1 gt lparse d none bidders sm smodels 0 smodels version 2 27 Reading done Answer 1 Stable Model sel e sel b not sel e not sel d not sel c not sel b not sel a min 57 Answer 2 Stable Model sel d not sel e not sel d not sel c not sel b not sel a min 56 False Duration 0 010 Salida 2 gt lparse bidders sm smodels 0 smodels version 2 27 Reading done Answer 1 Stable Model sel a not sel e not sel d not sel c not sel b not sel a min 57 Answer 2 Stable Model sel d not sel e not sel d not sel c not sel b not sel a min 56 False Duration 0 000 Salida 3 gt
23. ones generales A POL muestra ser un sistema que permite f cilmente representar un problema propuesto en principios matem ticos pero por otra parte requiere tener el suficiente conocimiento del lenguaje para hacer uso de esa expresividad Analizando los problemas 3 1 y 3 6 observamos que traducir un c digo de Smodels a DLV y viceversa es bastante intuitivo y no represent cambios complejos o dif ciles al programador por lo que se puede vislumbrar que el paso de un sistema a otro puede efectuarse sin mucha complejidad Para nuestra sorpresa todos los sistemas con excepci n de Aset Solver mostraron deficiencias incluso con ejemplos que en su mayor a ya hab an sido probados por los dise adores El caso de Aset Solver es separado porque no tiene ejemplos que cumplieran con nuestras expectativas por lo que no hubo suficiente informaci n para evaluarlo correctamente Resumen del cap tulo En este cap tulo se presentaron varios ejemplos probados en los diferentes sistemas para algunos de ellos tambi n se realizaron pruebas comparativas A continuaci n se explican los resultados y conclusiones de este trabajo
24. t 1 5 rest 2 6 rest 3 12 rest 4 19 rest 5 20 rest 6 27 ndepot 3 nrest 6 dom 1 6 reglas abs X Y R X R Y X gt Y int X int Y int R abs X Y R Y R X X lt Y int X int Y int R middle X X X int X middle X Y X abs X Y 1 middle X Y R middle R1 R2 R R1 X 1 Y R2 1 R1 lt R2 rdist LJ R abs R1 R2 R rest I R1 rest J R2 sumato I I K R rdist I K R sumato I J K R R R1 R2 rdist I K R1 sumato R3 J K R2 R3 1 Is cost I J R sumato I J K R middle L J K best1 1 L 0 dom D best1 1 1 R cost 1 L R bestl LJ R R R1 R2 cost B J R1 bestl R3 R4 R2 I R3 1 B R441 I lt J I lt B B lt J best2 I J R best1 L JR not rbest I J R rbest I J R best1 1 J M int R M lt R best I J R best2 1 J R ndepot D nrest J Salida gt dlv filter best fastfood dl DLV build BEN Jun 26 2003 gcc 2 95 3 10 cygwin special best 3 6 8 Las dos implementaciones de este problema lucen demasiado recargadas de llamadas a funciones La salida de A POL muestra donde se colocaran los dep sitos y DLV muestra el valor total de la distancia mas corta entre todos los restaurantes y sus dep sitos Se tiene este ejemplo implementado por Nicola Leone de DLV pero desafortunadamente usa una variante de la funci n de agregaci n min que aun es experimental en la version liberada del sistema por lo que no
Download Pdf Manuals
Related Search