Página 3 de 3

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

MensagemEnviado: Quarta Fev 15, 2012 12:35 am
por Bruno Oliveira
Não, estás a raciocinar bem, acontece que a característica de optimal substructure tem de ser verificada para alguns dos subproblemas e não todos (esqueci-me de referir isso no meu post atrás), e tu já conseguiste arranjar um contra-exemplo!! :hands:

No entanto, o tema da Programação Dinâmica e a existência/materialização destas duas características noutro problema mais complexo, é, regra geral, muito mais complicada de deduzir/apreender e só com a experiência se melhorará, que é algo que eu próprio estou a fazer! Isto foi apenas o que eu já sabia de Programação Dinâmica (que é muito pouco)

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

MensagemEnviado: Quarta Fev 15, 2012 7:06 pm
por ruifm
Tomei a liberdade de passar o teu algoritmo para python, mas com a cobertura de todos os elementos serem negativos:


Funciona!
Eu só não percebi como é que a programação dinamica me pode ajudar se não pode ser generalizada a todos os casos...

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

MensagemEnviado: Quarta Fev 15, 2012 7:23 pm
por Bruno Oliveira
Já considero bem sucedido o meu problema, se te entusiasmei o suficiente para teres programado a solução que viemos discutindo até aqui! Obrigado pelo teu empenho e entusiasmo! :)

Para responder à tua pergunta, de uma forma mais formal: um algoritmo de Programação Dinâmica é útil quando consegues obter soluções cuja complexidade é muito mais baixa do que uma solução que não use Programação Dinâmica.

Imagina, que corrias a solução por Brute Force num vector com 5000 elementos seudo-aleatórios.

Uma vez que estamos a listar todas as soluções, terias de obter todos os subvectores com 2,3,4,5,... N componentes, certo? :roll:

Isso implicaria manteres o registo na memória de imensos subvectores que não irias utilizar para nada.

A solução por DP (Dynamic Programming), além de ser muitissimo mais rápida (pois só percorres o vector uma vez), usa muito menos memória, visto que só tens de actualizar duas variáveis que guardam cada uma delas um número inteiro, ao invés de uma lista onde tens todas as somas dos vários subvectores.

Em relação ao caso particular que referiste (todos os elementos do vector serem negativos), não é necessário usar DP pois apenas tens de achar directamente um elemento do vector, que pode ser feito da forma mais eficaz possível usando built-in functions.

Assim, pode-se dizer que DP usa-se para obter um algoritmo mais eficaz para os casos que demorariam muito tempo a solucionar por outros métodos.

Re: Clássico: Encontrar o maior subvector cuja soma é maxima

MensagemEnviado: Quarta Fev 15, 2012 7:35 pm
por ruifm
Eu não me referia a esse caso (todos serem negativos).
Referia-me ao caso de o 2º requerimento da DP (overlaping subproblems), não se aplicar a qualquer vector.
Assim dado um pseudo-random vector com N elementos, não fazemos ideia se o subvector de n elementos com a maior soma, vai ser igual para n=1, n=2, n=3... etc.

Mas este método alternativo à brute force foi mesmo um leap para mim, juntamente com o atirar a recursão para o lixo. Programas que demoravam 12 horas, demoram agora 30 min.
A parte mais dificil agora da DP é ajustar a tal solução idilica a problemas totalmente diferentes. Eu demoraria ainda um pouco a chegar a esta se não desses um empurrao.