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

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

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

Mensagempor Bruno Oliveira em Quarta Fev 15, 2012 12:35 am

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)
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

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

Mensagempor ruifm em Quarta Fev 15, 2012 7:06 pm

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...
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

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

Mensagempor Bruno Oliveira em Quarta Fev 15, 2012 7:23 pm

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.
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

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

Mensagempor ruifm em Quarta Fev 15, 2012 7:35 pm

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.
"Everything is determined, the beginning as well as the end, by forces over which we have no control." - Albert Einstein
Avatar do utilizador
ruifm
down-Quark!
down-Quark!
 
Mensagens: 205
Registado: Segunda Jan 16, 2012 12:04 am
Localização: Lisboa - IST

Anterior

Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron