0votos

Edificio de 5 pisos en Other

por josejuan hace 5 días

Usando pseudo-boolean optimization directamente codificando las restricciones y usando un solver cualquiera.

Resolver esta especie de acertijo con programación.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
* El problema se puede codificar fácilmente como el OPB siguiente: 
+1 x5 +1 x6 +1 x11 +1 x15 +1 x16 +1 x17 x8 +1 x17 x9 +1 x17 x10 +1 x18 x9 +1 x18 x10 +1 x19 x10 +1 x11 x22 +1 x12 x21 +1 x12 x23 +1 x13 x22 +1 x13 x24 +1 x14 x23 +1 x14 x25 +1 x15 x24 +1 x11 x7 +1 x12 x6 +1 x12 x8 +1 x13 x7 +1 x13 x9 +1 x14 x8 +1 x14 x10 +1 x15 x9 = 0 ; 
+1 x1 +1 x6 +1 x11 +1 x16 +1 x21 = 1 ; 
+1 x2 +1 x7 +1 x12 +1 x17 +1 x22 = 1 ; 
+1 x3 +1 x8 +1 x13 +1 x18 +1 x23 = 1 ; 
+1 x4 +1 x9 +1 x14 +1 x19 +1 x24 = 1 ; 
+1 x5 +1 x10+1 x15 +1 x20 +1 x25 = 1 ; 
+1 x1 +1 x2 +1 x3 +1 x4 +1 x5 = 1 ; 
+1 x6 +1 x7 +1 x8 +1 x9 +1 x10 = 1 ; 
+1 x11 +1 x12 +1 x13 +1 x14 +1 x15 = 1 ; 
+1 x16 +1 x17 +1 x18 +1 x19 +1 x20 = 1 ; 
+1 x21 +1 x22 +1 x23 +1 x24 +1 x25 = 1 ; 
 
 
 
 
 
 
 
 
* Para ejecutarlo, basta con lanzar (sirve cualquier solver): 
*   $ toysolver --pb pisos.opb 
*   s OPTIMUM FOUND 
*   v -x1 -x2 x3 -x4 -x5 -x6 x7 -x8 -x9 -x10 
*   v -x11 -x12 -x13 x14 -x15 -x16 -x17 -x18 -x19 x20 
*   v x21 -x22 -x23 -x24 -x25 -x26 -x27 -x28 -x29 -x30 
*   v -x31 -x32 -x33 -x34 -x35 -x36 -x37 -x38 -x39 -x40 
*   v -x41 -x42 -x43 -x44 -x45 -x46 -x47 
* En que quedan a `true` las variables persona/piso válidas. 
 
 
 
 
 
 
 
 
* Una explicación detallada podría ser: 
* Sean las p € Personas siguientes 
*     1     2    3     4     5 
*   Adam, Bill, Cora, Dale, Erin 
* y los pisos i € Pisos siguientes 
*   1, 2, 3, 4, 5 
* entonces decimos que p vive en i si 
*   x{ 5 * (p - 1) + i } = true 
* Así, codificamos directamente las restricciones 
 
* - Adam no vive en el ultimo piso. 
+1 x5 = 0 ; 
 
* - Bill no vive en el primer piso. 
+1 x6 = 0 ; 
 
* - Cora no vive ni en el primer ni en el ultimo piso. 
+1 x11 +1 x15 = 0 ; 
 
* - Dale vive en un piso que esta más arriba que el de Bill. 
+1 x16 +1 x17 x8 +1 x17 x9 +1 x17 x10 +1 x18 x9 +1 x18 x10 +1 x19 x10 = 0 ; 
 
* - Erin no vive en un piso al lado del piso donde vive Cora. 
+1 x11 x22 +1 x12 x21 +1 x12 x23 +1 x13 x22 +1 x13 x24 +1 x14 x23 +1 x14 x25 +1 x15 x24 = 0 ; 
 
* - Cora no vive en un piso al lado del piso donde vive Bill. 
+1 x11 x7 +1 x12 x6 +1 x12 x8 +1 x13 x7 +1 x13 x9 +1 x14 x8 +1 x14 x10 +1 x15 x9 = 0 ; 
 
* - cada uno debe vivir en un piso diferente 
+1 x1 +1 x6 +1 x11 +1 x16 +1 x21 = 1 ; 
+1 x2 +1 x7 +1 x12 +1 x17 +1 x22 = 1 ; 
+1 x3 +1 x8 +1 x13 +1 x18 +1 x23 = 1 ; 
+1 x4 +1 x9 +1 x14 +1 x19 +1 x24 = 1 ; 
+1 x5 +1 x10+1 x15 +1 x20 +1 x25 = 1 ; 
 
* no pueden vivir en el mismo piso 
+1 x1  +1 x2  +1 x3  +1 x4  +1 x5  = 1 ; 
+1 x6  +1 x7  +1 x8  +1 x9  +1 x10 = 1 ; 
+1 x11 +1 x12 +1 x13 +1 x14 +1 x15 = 1 ; 
+1 x16 +1 x17 +1 x18 +1 x19 +1 x20 = 1 ; 
+1 x21 +1 x22 +1 x23 +1 x24 +1 x25 = 1 ; 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.