Resolución del problema de la mochila en varias estrategias, algoritmos voraces

Resolución del problema de la mochila en varias estrategias, algoritmos voraces

En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo

Estrategias para resolverlo, llenar la mochila:
1) Con los elementos más costosos
2) Con los elementos menos pesados
3) Con los elementos que tenga mayor beneficio por unidad de peso ( coeficiente entre valor y peso)
4) Algoritmo Backtracking (o vuelta atrás):

     Es  un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede, o bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

A continuación, este problema resueldo aplicando las distintas estrategias, usando Gambas3
Estructura del Proyecto:

Clase Elemento:
-

Data hosted with ♥ by Pastebin.com - Download Raw - See Original

1. ' Gambas class file
2.  
3. Property nombre As String
4. Private hnombre As String
5.  
6. Property valor As Float
7. Private hvalor As Float
8.  
9. Property peso As Float
10. Private hpeso As Float
11.  
12. Property estrategia As String
13. Private hestrategia As String
14.  
15. Private Function estrategia_Read() As String
16.  
17.   Return hestrategia
18.  
19. End
20.  
21. Private Sub estrategia_Write(Value As String)
22.  
23.   hestrategia = Value
24.  
25. End
26.  
27. Private Function nombre_Read() As String
28.  
29.   Return hnombre
30.  
31. End
32.  
33. Private Sub nombre_Write(Value As String)
34.  
35.   hnombre = Value
36.  
37. End
38.  
39. Private Function valor_Read() As Float
40.  
41.   Return hvalor
42.  
43. End
44.  
45. Private Sub valor_Write(Value As Float)
46.  
47.   hvalor = Value
48.  
49. End
50.  
51. Private Function peso_Read() As Float
52.  
53.   Return hpeso
54.  
55. End
56.  
57. Private Sub peso_Write(Value As Float)
58.  
59.   hpeso = Value
60.  
61. End
62.  
63. Public Sub _new(n As String, v As Float, p As Float) '' n es nombre, v es valor, p es peso
64.  
65.   hnombre = n
66.   hvalor = v
67.   hpeso = p
68.  
69. End
70.  
71. Public Function toString() As String
72.  
73.   Return "Nombre: " & hnombre & " Valor:" & hvalor & " Peso:" & hpeso
74.  
75. End
76. '---------------------------------------------------------------------------------------
77. 'definicion del método de comparar (que propiedad compara, en este caso el valor)
78. '----------------------------------------------------------------------------------------
79.  
80. Public Function _compare(otro As Elemento) As Integer
81.   '--------------------------------------------------------
82.   'Estrategia el del mayor valor...
83.   '--------------------------------------------------------
84.  
85.   If hestrategia = "mayor_valor" Then
86.     If otro.valor > Me.valor Then
87.       Return 1
88.     Else
89.       Return 0
90.      
91.     Endif
92.   Endif
93.  
94.   '--------------------------------------------------------
95.   'Estrategia el del menos pesados valor...
96.   '--------------------------------------------------------
97.  
98.   If hestrategia = "menos_peso" Then
99.     If otro.peso < Me.peso Then
100.       Return 1
101.     Else
102.       Return 0
103.      
104.     Endif
105.   Endif
106.  
107.   '--------------------------------------------------------
108.   ' Estrategia: relacion entre valor/peso del elemento
109.   '--------------------------------------------------------
110.   If hestrategia = "coeficiente_valor/peso" Then
111.     If (otro.valor / otro.peso) > (Me.valor / Me.peso) Then
112.       Return 1
113.     Else
114.       Return 0
115.     Endif
116.   Endif
117.  
118. End

-


Clase ProblemaMochila:
-

Data hosted with ♥ by Pastebin.com - Download Raw - See Original

1. ' Gambas class file
2.  
3. Private almacen As New Elemento[]
4. Private mochila As New Elemento[]
5. Private pesomaximo As Float
6. Private hestrategia As String
7.  
8. Private tmpMochila As New Elemento[] 'mochila temporal para método backtracking
9. Private valorMaximo As Float
10.  
11. Public Sub _new(pm As Float, estra As String) '' pm: peso maximo que soporta la mochila
12.  
13.   pesomaximo = pm
14.   hestrategia = estra
15.   cargaDatos()
16.  
17. End
18.  
19. Public Sub cargaDatos()
20.  
21.   Dim elementoTmp As Elemento
22.   elementoTmp = New Elemento("TV", 300, 15)
23.   elementoTmp.estrategia = hestrategia
24.   almacen.Add(elementoTmp)
25.  
26.   elementoTmp = New Elemento("PS3", 100, 3)
27.   elementoTmp.estrategia = hestrategia
28.   almacen.Add(elementoTmp)
29.  
30.   elementoTmp = New Elemento("Libro Java", 10, 1)
31.   elementoTmp.estrategia = hestrategia
32.   almacen.Add(elementoTmp)
33.  
34.   elementoTmp = New Elemento("DVD", 5, 0.5)
35.   elementoTmp.estrategia = hestrategia
36.   almacen.Add(elementoTmp)
37.  
38.   elementoTmp = New Elemento("Blu-Ray", 50, 0.5)
39.   elementoTmp.estrategia = hestrategia
40.   almacen.Add(elementoTmp)
41.  
42.   elementoTmp = New Elemento("Balon", 30, 0.5)
43.   elementoTmp.estrategia = hestrategia
44.   almacen.Add(elementoTmp)
45.  
46.   elementoTmp = New Elemento("ipod", 150, 1)
47.   elementoTmp.estrategia = hestrategia
48.   almacen.Add(elementoTmp)
49.  
50.   elementoTmp = New Elemento("Printer", 20, 4)
51.   elementoTmp.estrategia = hestrategia
52.   almacen.Add(elementoTmp)
53.  
54.   elementoTmp = New Elemento("VideoBeam", 200, 4)
55.   elementoTmp.estrategia = hestrategia
56.   almacen.Add(elementoTmp)
57.  
58.   elementoTmp = New Elemento("Laptop", 20, 3)
59.   elementoTmp.estrategia = hestrategia
60.   almacen.Add(elementoTmp)
61.  
62.   elementoTmp = New Elemento("ipad", 150, 2)
63.   elementoTmp.estrategia = hestrategia
64.   almacen.Add(elementoTmp)
65.  
66.   elementoTmp = New Elemento("PC", 100, 5)
67.   elementoTmp.estrategia = hestrategia
68.   almacen.Add(elementoTmp)
69.  
70.   elementoTmp = New Elemento("BlackBerry", 150, 0.5)
71.   elementoTmp.estrategia = hestrategia
72.   almacen.Add(elementoTmp)
73.  
74. End
75.  
76. Public Sub mostrarMochila()
77.  
78.   Dim pesomochila As Integer = 0
79.   Dim valorMochila As Float = 0
80.   Dim elementoTmp As Elemento
81.  
82.   For Each elementoTmp In mochila
83.     Print elementoTmp.toString()
84.     pesomochila += elementoTmp.peso
85.     valorMochila += elementoTmp.valor
86.    
87.   Next
88.   Print "-------------"
89.   Print "Peso: ", pesomochila
90.   Print "Valor: ", valorMochila
91.  
92. End
93. '-------------------------------------------------------------
94.  
95. '
96.  
97. Public Sub resolverProblema()
98.  
99.   Dim pesomochila As Float = 0
100.   Dim posicion As Integer = 0
101.   Dim tmp As Elemento
102.   'ordenar los elementos del almacen por el valor
103.   almacen.Sort()
104.  
105.   While ((pesomochila < pesomaximo) And (posicion < almacen.Count))
106.     tmp = almacen[posicion]
107.     If (pesomochila + tmp.peso <= pesomaximo) Then
108.       mochila.Add(tmp)
109.       pesomochila += tmp.peso
110.     Endif
111.     posicion += 1
112.    
113.   Wend
114.  
115. End
116.  
117. '-----------------------------
118. 'resolver por backtraking
119. '-----------------------------------
120. Public Sub resolverProblemaBT(posicion As Integer)
121.  
122.   Dim pesomochila As Float = getPeso(tmpMochila)
123.   Dim valorMochila As Float = getValor(tmpMochila)
124.   Dim e As Elemento
125.  
126.   If posicion >= almacen.count Then
127.     If valorMochila > valorMaximo Then
128.       valorMaximo = valorMochila
129.       mochila.Clear()
130.       Copia(tmpMochila, mochila)
131.     Endif
132.    
133.     Return
134.   Endif
135.  
136.   e = almacen[posicion]
137.  
138.   If ((pesomochila + e.peso) <= pesomaximo) Then
139.     tmpMochila.Add(e)
140.     resolverProblemaBT(posicion + 1)
141.     Try tmpMochila.remove(tmpMochila.Find(e))
142.   Endif
143.  
144.   resolverProblemaBT(posicion + 1)
145.  
146. End
147.  
148. Public Function getPeso(tmp As Elemento[]) As Float
149.  
150.   Dim respuesta As Float = 0
151.   Dim elementoTmp As Elemento
152.  
153.   For Each elementotmp In tmp
154.     respuesta += elementotmp.peso
155.   Next
156.  
157.   Return respuesta
158.  
159. End
160.  
161. Public Function getValor(tmp As Elemento[]) As Float
162.  
163.   Dim respuesta As Float = 0
164.   Dim elementoTmp As Elemento
165.  
166.   For Each elementotmp In tmp
167.     respuesta += elementoTmp.valor
168.   Next
169.  
170.   Return respuesta
171.  
172. End
173.  
174. Public Sub Copia(tmp As Elemento[], tmp2 As Elemento[])
175.  
176.   Dim elementoTmp As Elemento
177.  
178.   For Each elementotmp In tmp
179.     tmp2.Add(elementoTmp)
180.   Next
181.  
182.  
183. End

-

Programa Principal:
-

Data hosted with ♥ by Pastebin.com - Download Raw - See Original

1. ' Gambas module file
2.  
3. Public Sub main()
4.  
5.   Dim pm As New ProblemaMochila(20, "mayor_valor")
6.   Dim pm1 As New ProblemaMochila(20, "menos_peso")
7.   Dim pm2 As New ProblemaMochila(20, "coeficiente_valor/peso")
8.  
9.   Print "......................................."
10.   Print "Estrategia: " & "mayor_valor"
11.   pm.resolverProblema()
12.   pm.mostrarMochila()
13.   Print "......................................."
14.   Print "Estrategia: " & "menos_peso"
15.   pm1.resolverProblema()
16.   pm1.mostrarMochila()
17.   Print "......................................."
18.   Print "Estrategia: " & "coeficiente_valor/peso"
19.   pm2.resolverProblema()
20.   pm2.mostrarMochila()
21.   Print "......................................."
22.   Print "Algoritmo Backtracking"
23.   pm.resolverProblemaBT(0)
24.   pm.mostrarMochila()
25.  
26. End

-


Resultados:

.......................................
Estrategia: mayor_valor
Nombre: TV Valor:300 Peso:15
Nombre: VideoBeam Valor:200 Peso:4
Nombre: ipod Valor:150 Peso:1
-------------
Peso:   20
Valor:  650
.......................................
Estrategia: menos_peso
Nombre: DVD Valor:5 Peso:0.5
Nombre: Blu-Ray Valor:50 Peso:0.5
Nombre: Balon Valor:30 Peso:0.5
Nombre: BlackBerry Valor:150 Peso:0.5
Nombre: Libro Java Valor:10 Peso:1
Nombre: ipod Valor:150 Peso:1
Nombre: ipad Valor:150 Peso:2
Nombre: PS3 Valor:100 Peso:3
Nombre: Laptop Valor:20 Peso:3
Nombre: Printer Valor:20 Peso:4
Nombre: VideoBeam Valor:200 Peso:4
-------------
Peso:   18
Valor:  885
.......................................
Estrategia: coeficiente_valor/peso
Nombre: BlackBerry Valor:150 Peso:0.5
Nombre: ipod Valor:150 Peso:1
Nombre: Blu-Ray Valor:50 Peso:0.5
Nombre: ipad Valor:150 Peso:2
Nombre: Balon Valor:30 Peso:0.5
Nombre: VideoBeam Valor:200 Peso:4
Nombre: PS3 Valor:100 Peso:3
Nombre: PC Valor:100 Peso:5
Nombre: Libro Java Valor:10 Peso:1
Nombre: DVD Valor:5 Peso:0.5
-------------
Peso:   16
Valor:  945
.......................................
Algoritmo Backtracking
Nombre: VideoBeam Valor:200 Peso:4
Nombre: ipod Valor:150 Peso:1
Nombre: ipad Valor:150 Peso:2
Nombre: BlackBerry Valor:150 Peso:0.5
Nombre: PS3 Valor:100 Peso:3
Nombre: PC Valor:100 Peso:5
Nombre: Blu-Ray Valor:50 Peso:0.5
Nombre: Balon Valor:30 Peso:0.5
Nombre: Laptop Valor:20 Peso:3
Nombre: DVD Valor:5 Peso:0.5
-------------
Peso:   18
Valor:  955

Enlace de descarga del código fuente: enlace a box.com

Fuentes:

http://es.wikipedia.org/wiki/Problema_de_la_mochila
http://es.wikipedia.org/wiki/Vuelta_atr%C3%A1s
http://cala.unex.es/cala/epistemowikia/index.php?title=Backtracking
http://jorgep.blogspot.com.es/2010/11/problema-de-la-mochila.html
http://jorgep.blogspot.com.es/2010/11/problema-de-la-mochila-algoritmos.html
http://jorgep.blogspot.com.es/2010/11/problema-de-la-mochila-backtracking.html