Neste post, apresento uma introdução à linguagem Lua (Lua 5.1) com uma abordagem prática baseada em técnicas de programação para a resolução do problema da mochila (0-1 knapsack problem).
O problema da mochila é um problema de otimização combinatória. Seu nome é derivado do problema maximização que consiste em encontrar a melhor escolha de itens para serem levados em uma viagem que caibam em uma mochila. Em outras palavras, dado um conjunto de itens, cada qual com um custo e um valor, determine quais itens incluir em uma coleção tal que o custo seja menor do que um dado limite e o valor total seja o maior possível. Problemas similares aparecem frequentemente em negócios (business), combinatória, teoria de complexidade, criptologia e matemática aplicada.
Um exemplo em Lua de uma instância do problema da mochila é apresentado abaixo:
– 0-1 Knapsack problem example instance
W = 10 — capacity
p = {4, 3, 2, 1, 5, 2, 1, 4, 3, 1} — item profit
w = {2, 3, 4, 5, 1, 5, 4, 2, 3, 7} — item weight
n = #p — the total of items
Em Lua, é comum representar cada comando em uma linha e os comandos podem ou não ser finalizados com ‘;’. Neste caso, não utilizamos o ‘;’. As variáveis tem seu tipo definido dinamicamente, e por isso não precisamos nos preocupar com isso. A variável W é um número inteiro de valor 10. As variáveis p e w são vetores e a variável n possui como valor o comprimento do vetor p, que é obtido com o operador ‘#’. Para acessar o elemento de um vetor utiliza-se a notação v[i].
– Describing the problem
print(“Find the most valuable subset of ” .. n .. ” items ” ..
“to put into a pack without exceding the capacity ” .. W .. “.”)
Para imprimir mensagens para o console utiliza-se a função print. O operador ‘..’ serve para concatenar strings, e quando o operador encontra uma variável com valor numérico, esse valor é convertido automaticamente em string.
Uma solução trivial para o problema da mochila é realizar uma enumeração de todas as combinações possíveis de itens na mochila. Para implementar uma solução assim em Lua, precisamos dos conceitos de funções (funções recursivas) e de controles condicionais (ifs).
Em Lua, funções são definidas da seguinte forma:
function nome ( [parameters,..] )
[statments...]
[return value]
end
Nota: o que aparece entre colchetes é opcional.
Controles condicionais são definidos como:
if ( condition ) then
[statments...]
[else
statments...]
end
Lua possui um modificador de escopo para as variáveis. A princípio uma variável é global, exceto se seu escopo for modificado para ‘local’. Já como uma boa prática de programação deve-se reduzir o escopo de todas as variáveis que não devem ser necessariamente globais.
A seguir apresentamos uma solução baseada nesta idéia:
– Naive solver
function naiveSolver(p, w, W)
local function recursiveSolver(i, p, w, W)
–print ( “trying ” .. i .. ” with W=” .. W )
if (i < #w) then
local p1 = 0
if ( W >= w[i] ) then — if we can put the item inside the knapck
p1 = p[i] + recursiveSolver(i+1, p, w, W-w[i]) — item inside knapsack
end
local p2 = recursiveSolver(i+1, p, w, W) — item inside knapsack
return (p1 > p2) and p1 or p2
end
if ( W >= w[i] ) then — if we can put the item inside the knapck
return p[i]
end
return 0
end
print “**********************”
print “Naive solver…”
local t = os.time()
local profit = recursiveSolver(1, p, w, W)
print(“runtime: ” .. os.difftime( os.time(), t ) .. “s”)
print(“best profit: ” .. profit)
end
Resolve o problema, mas seu poder é limitado a pequenas instâncias do problema. Técnicas mais sofisticadas podem obter o mesmo resultado consumindo menos recursos (tempo, memória). Abaixo apresentamos um algoritmo baseado na técnica de programação dinâmica:
– Dynamic programming
function dynamicProgrammingSolver(p,w,W)
print “**********************”
print “Dynamic programming solver…”
local t = os.time()
local T = {}
T[0] = {}
for c=0,W do
T[0][c] = 0
end
for i=1,n do
T[i] = {}
for c=0,W do
if c>=w[i] then
T[i][c] = max(T[i-1][c], T[i-1][c-w[i]] + p[i])
else
T[i][c] = T[i-1][c]
end
end
end
print(“runtime: ” .. os.difftime( os.time(), t ) .. “s”)
print(“best profit: ” .. T[n][W])
end
Em programação dinâmica não é utilizado o conceito de função recursiva para avaliar todas as combinações. As iterações são realizadas de forma explícita pelo iterador ‘for’ e as combinações são armazenadas em uma tabela, representada por um vetor de vetores.
Para se ter uma idéia da diferença entre as duas técnicas abaixo está uma saída da execução dos algoritmos para uma instância de apenas 100 itens.
Find the most valuable subset of 100 items to put into a pack without exceding the capacity 32001.
**********************
Naive solver…
runtime: 23s
best profit: 32121
**********************
Dynamic programming solver…
runtime: 1s
best profit: 32121
**********************
Quando você trabalha com instâncias muito grandes, ou seja, com muitos itens para serem avaliados, o método trivial não será mais viável por consumir muito tempo. O mesmo acontece para o algoritmo de programação dinâmica. Maiores detalhes do por que isso acontece podem ser encontrado na análise de complexidade de problema. Só a título de exemplo, a técnica de força bruta possui complexidade assintótica de O(2^n) e o de programação dinâmica O(n W), onde n é o número de itens que podem ser colocados na mochila e W o tamanho da mochila. Por ter uma solução com programação dinâmica aparentemente de complexidade polinomial, este problema é também conhecido como pseudo-polinomial, mas só digo isso para motivá-lo a estudar complexidade de problemas.
A partir da necessidade de resolver instâncias grandes, ou com restrições de recurso (tempo, memória), são propostas outras técnicas, algoritmos, baseadas em algum conhecimento sobre o problema. Essas técnicas são chamadas técnicas heurísticas.
Para o problema da mochila, temos a heurística clássica proposta por Dantzig em 1957. A idéia é ordenar os itens em relação a um critério de eficiência, definido como o benefício dividido pelo custo, ou seja, a razão valor / peso. A partir dessa ordenação, adicionam-se os itens mais eficientes à mochila, sempre respeitando a capacidade da mochila. Cada item é avaliado apenas uma vez, e a solução obtida pode não ser necessariamente a melhor possível. Contudo, a solução obtida geralmente é boa e esse método é muito mais rápido que os anteriores.
– Greedy method
function greedyMethod (p, w, W)
– objective function value calculation
function fo(W,x,p,w)
local weight = 0
local profit = 0
for i=1,#x do
if x[i] then
profit = profit + p[i]
weight = weight + w[i]
end
end
if weight > W then — is infeasible?
profit = -math.huge, weight
end
return profit, weight
end
function aggregate(T1, T2)
local T = {}
for i, v in ipairs(T1) do
T[i] = {T1[i]/T2[i], T1[i], T2[i], i}
end
return T
end
function disaggregate(T)
local T1 = {}
local T2 = {}
local T3 = {}
for i, v in ipairs(T) do
T1[i], T2[i], T3[i] = T[i][2], T[i][3], T[i][4]
end
return T1, T2, T3
end
print “**********************”
print “Greedy method…”
local t = os.time()
– sort objects in decreasing efficiency
local items = aggregate(p, w)
table.sort(items, function(a,b) return a[1]>b[1] end)
local vo, wo, index = disaggregate(items)
local x = {} — answer 0-1 array
local _w = 0 — weight
for i=1,#wo do
if wo[i] + _w <= W then
x[i] = true
_w = _w + wo[i]
else
x[i] = false
end
end
print(“runtime: ” .. os.difftime( os.time(), t ) .. “s”)
print(“Greedy method result”)
local profit, weight = fo(W, x, , vo, wo)
print(“Total profit ” .. profit .. ” weight ” .. weight )
end
A complexidade assintótica desta heurística é dominada pela função de ordenação, em que os melhores algoritmos conhecidos são O(n log n) (Quicksort, Mergesort). Note que aproveitamos a função de ordenação disponibilizada pela linguagem Lua, e fornecemos uma função para a comparação de dois itens. Funções em Lua são elementos de primeira ordem, e por isso podem ser passados como parâmetros.
Outro conceito interessante em Lua é o de múltiplas atribuições, o que possibilita também que funções retornem mais de um valor.
a, b, c = 1, 2, 3
print(a, b, c) –> 1 2 3
function f ()
return 1, 2, 3
end
a, b, c = f()
print(a, b, c) –> 1 2 3
O desempenho dos métodos pode ser percebido através dos resultados obtidos na resolução de uma instância de 100 e outra de 300 itens:
Find the most valuable subset of 100 items to put into a pack without exceding the capacity 32001.
**********************
Naive solver…
runtime: 23s
best profit: 32121
**********************
Dynamic programming solver…
runtime: 1s
best profit: 32121
**********************
Greedy method…
runtime: 0s
Greedy method result
Total profit 30562 weight 30442
Find the most valuable subset of 300 items to put into a pack without exceding the capacity 46437.
**********************
Naive solver…
runtime: + 30 minutes – I killed it by hand
best profit: x
**********************
Dynamic programming solver…
runtime: 6s
best profit: 46707
**********************
Greedy method…
runtime: 0s
Greedy method result
Total profit 44173 weight 43903
O código apresentado aqui está disponível para download.
Obs: As simulações foram executadas em um computador Pentium Core 2 Duo E4500 @ 2.20 GHz com 960 MB de DDR2 RAM rodando Windows XP Professional compartilhando processamento com outras aplicações leves. As instâncias de testes foram obtidas a partir do gerador de David Pisinger.
