ABRAWEB
Abrawebem Google+


Mais colunistas

Envie seu texto para
COLUNISTAS ABRAWEB


Publicidade

Colunistas ABRAWEB

Algoritmos de programação dinâmica em Javascript

Procurar soluções de projeto de algoritmos que possam ser processados do lado client, principalmente para compilar grandes quantidade de dados de forma eficiente utilizando poucos recursos, hoje em dia é um desafio para os desenvolvedores. Existem muitos conceitos que podem ser aplicados, sendo um deles o conceito de programação dinâmica.

Esse conceito de projeto segue a ideia de pegar um problema “grande” e dividir ele em partes menores, muitas vezes podemos resolver ele com uma função recursiva, mas como grandes partes dos algoritmos recursivos, temos o problema de empilhar varias funções e sobrecarregar a memorias da maquina, no nosso caso dependendo do numero de funções recursivas abertas, o browser travaria.

Agora vamos imaginar que ao invés de encher a memoria com varias funções, usaremos apenas um vetor como apoio para poder processar e cachear os resultados de cada conjunto gerado para resolver o problema, sendo que o tempo e recursos estimados para o processamento esta sempre vinculado ao tamanho do vetor que vamos percorrer, lembrando que com isso temos a vantagem de poder dividir ainda mais o problemas em vetores menores e processar ele conforme as ações do usuários.

Existem um problema computacional bem conhecido que pode ser resolvido através dessa estrategia, o problema de “soma de subconjuntos” ou “exact subset-sum”. Vamos imaginar que todas vez que carregar uma lista, eu determino um valor para que seja possível carregar, a pergunta é, qual combinações possível de valores posso carregar?

Esse tipo de inteligencia pode ser aplicado em vários casos comuns, como saber em tempo real quais combinações possível para um grupo de pessoas em quartos, saber qual a melhor combinação de itens para se colocar em um carrinho de compras ou ate mesmo quais conjuntos possíveis se colocar na mochila de uma viajem. O computador pode calcular tudo isso pra gente :D .

Vamos ao código:

function calcularSubConjuntosPossiveis(vetorLista,n,soma){

// Se o valor de subListaVetor[sum+1][n+1] for true então existe pelo menos um subconjunto possível

subListaVetor[soma+1][n+1];
var 1 = 0;
var j = 0;

// Se a soma de todos os itens for 0, resposta true

for(i = 0; i <= n; i++){
subListaVetor[0][i] =true;
}

// Se a soma dos itens não for 0, devemos verificar quais conjuntos possíveis existem

for(i = 1; i <= soma; i++){
subListaVetor[i][0] = false;
}

// Gera a matriz com combinações possíveis de conjuntos

for(i = 1; i <= soma; i++){

// colocar todos os valores no topo

for(j = 1; j <= n; j++){
subListaVetor[i][j] = subListaVetor[i][j-1];

//verifica se o item cabe dentro do conjunto e atualiza a posição dele dentro da matriz
if(i >= vetorLista[j-1]){
subListaVetor[i][j] = subListaVetor[i][j] || subListaVetor[i - vetorLista[j-1]][j-1];
}

}

}

// Vamos imprimir agora a nossa matriz, falado quais combinações de conjuntos possíveis

for (i = 0; i <= soma; i++){

for (j = 0; j <= n; j++){
document.write(subListaVetor[i][j]+” | “);
}

document.write(‘
‘);
}

// retorna true ou false, avisando se foi possível fazer a combinação de itens com os valores

return subListaVetor[soma][n];

}
Como resultado final, vamos ter uma matriz, falando true ou false, falando quais combinação possíveis por linha.

Richard Brochini  desenvolvedor de sistemas
Richard Brochini, 27, trabalha a 8 anos com desenvolvimento de projetos para TI. Vencedor da categoria Jogos Mobile na SBGames 2008, ganhador do prêmio Porto Seguro como melhor jogo on-line, vencedor de melhor jogo feito para Tv Digital da TOTVz, dentre outras competições. Formado em Ciência Da Computação pela Universidade Anhembi Morumbi ,Certificado pela Impacta Tecnologia. Procura sempre aprender novas tecnologias, com esse diferencial, está sempre capacitado para atender os principais projetos da área. Hoje em dia está muito empolgado com a onda Smart Watch e já desenvolveu alguns protótipos.
Para entrar em contato: Richard@brochini.com


+ artigos

Richard Brochini



Segurança na web
Inscrição | Indique a Associação | Sobre a ABRAWEB | F.A.Q. | Contato