Ir para o conteúdo
epolozero

Dynamic Programming

Mensagens Recomendadas

epolozero    14
epolozero

Boas, estou a começar a aprender o conceito de DP e gostava de saber se estou a aplicá-lo da maneira correta ou se existe uma maneira mais eficiente.

Aqui está um código que "devolve" a n-ésima (não sei se o termo está bem aplicado) posição da sequência de fibonacci, com o uso de DP,

def fib(n):
  if n == 0:
  return 0
  if n == 1:
  return 1
  else:
  if m[n - 2]  == 0:
	 m[n - 1] = fib(n - 1)
	 m[n - 2] = fib(n - 2)	  
  else:
	 if m[n - 1] == 0:
	    m[n - 1] = fib(n - 1)
  return m[n - 1] + m[n - 2]  

n = int(raw_input())
m = [0 for i in range(n)]
print fib(n-1)  

Links para a sequência de Fibonacci-> http://en.wikipedia.org/wiki/Fibonacci_number

Links para Dynamic Programing (DP)-> http://en.wikipedia.org/wiki/Dynamic_programming

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

O código parece-me correcto, tirando o facto de devolveres o valor para Fn-1 e não Fn :D

O código também poderia ser ligeiramente simplificado:

def fib(n):
  if n == 0:
	  return 0
  elif n == 1:
	  return 1
  else:
   if m[n] == 0:
	   m[n] = fib(n - 1) + fib(n - 2)
   return m[n]

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

antes de continuar com a minha resposta, dois pontos importantes:

- nunca toquei em python, por isso não vou comentar sobre a correcta sintaxe ou o uso das ferramentas disponibilizadas pela linguagem

- Dynamic programming é um assunto que pessoalmente abordei a título individual e muito, mas muito pela superfície.

pondo isto, e no meu ponto de vista limitado do assunto, è meu parecer que nenhuma das soluções apresentadas aqui está 100% correcta.

o ponto fundamental na programação dinâmica é a maximização da eficiência do código, sendo para tal usado o array/lista (ou o que é chamada em python) m no código apresentado no primeiro post. é da metodologia da programação dinâmica, quando se depara em problemas de recursividade e reutilização de valores, estes sejam guardados para futura utilização, prevenindo a necessidade de se efectuar o mesmo cálculo.

é por essa razão que considero que a resposta do @Rui Carlos se encontra errada, pois não implementa esta metodologia.

por outro lado, o próprio @Rui Carlos já referiu, estás a devolver o número errado da sequência.

voltando a referir que nunca peguei em python, pegando no código do primeiro post, a meinha resposta seria:

def fib(n):
 if n == 0:                           # caso n igual a 0
   m[0] = 0                           # guardar o valor de fib(0) no array m
   return m[0]                        # retornar o valor calculado
 if n == 1:                           # caso n igual a 1
   m[1] = 1                           # guardar o valor de fib(1) no array m
   return m[1]                        # retornar o valor calculado
 else:                                # caso n > 1
   if m[n] == 0:                      # caso o valor de fib(n) ainda não tiver sido calculado anteriormente
      m[n] = fib(n - 1) + fib(n - 2)  # calcular o valor de fib(n) pela recursividade
   return m[n]                        # retornar o valor de fib(n)

n = int(raw_input())                   # não faço ideia do que isto faz mas deduzo que seja ler um valor inteiro
m = [0 for i in range(n)]              # inicializar o array m com n elementos todos com o valor de zero
print fib(n)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

antes de continuar com a minha resposta, dois pontos importantes:

- nunca toquei em python, por isso não vou comentar sobre a correcta sintaxe ou o uso das ferramentas disponibilizadas pela linguagem

- Dynamic programming é um assunto que pessoalmente abordei a título individual e muito, mas muito pela superfície.

pondo isto, e no meu ponto de vista limitado do assunto, è meu parecer que nenhuma das soluções apresentadas aqui está 100% correcta.

o ponto fundamental na programação dinâmica é a maximização da eficiência do código, sendo para tal usado o array/lista (ou o que é chamada em python) m no código apresentado no primeiro post. é da metodologia da programação dinâmica, quando se depara em problemas de recursividade e reutilização de valores, estes sejam guardados para futura utilização, prevenindo a necessidade de se efectuar o mesmo cálculo.

é por essa razão que considero que a resposta do @Rui Carlos se encontra errada, pois não implementa esta metodologia.

por outro lado, o próprio @Rui Carlos já referiu, estás a devolver o número errado da sequência.

voltando a referir que nunca peguei em python, pegando no código do primeiro post, a meinha resposta seria:

def fib(n):
 if n == 0:						   # caso n igual a 0
m[0] = 0						   # guardar o valor de fib(0) no array m
return m[0]						# retornar o valor calculado
 if n == 1:						   # caso n igual a 1
m[1] = 1						   # guardar o valor de fib(1) no array m
return m[1]						# retornar o valor calculado
 else:								# caso n > 1
if m[n] == 0:					  # caso o valor de fib(n) ainda não tiver sido calculado anteriormente
   m[n] = fib(n - 1) + fib(n - 2)  # calcular o valor de fib(n) pela recursividade
return m[n]						# retornar o valor de fib(n)

n = int(raw_input())				   # não faço ideia do que isto faz mas deduzo que seja ler um valor inteiro
m = [0 for i in range(n)]			  # inicializar o array m com n elementos todos com o valor de zero
print fib(n)

Os valores para 0 e 1 estão memo-ized no próprio código fonte. Não me parece que seja necessário colocá-los no m para que se possa dizer que se está a usar programação dinâmica.

Repara também que mesmo na tua solução estás constantemente a "recalcular" o fib(0) e o fib(1) (se também vais guardar o valor do 0 e do 1, então convém começar logo com o teste m[n] == 0).

(Na criação do m é necessário um array com n+1 elementos---penso que era por esta razão que o epolozero estava a devolver o valor para n-1.)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

Repara também que mesmo na tua solução estás constantemente a recalcular o fib(0) e o fib(1) (se também vais guardar o valor do 0 e do 1, então convém começar logo com o teste m[n] == 0).

não, estás enganado no que toca ao processo de cálculo.

nota que no meu código, na verificação se m[n] for diferente de zero, então não existe a chamada recursiva para calculo de fib(n), logo, quanto muito, fib(0) e fib(1) serão calculados 1 vez cada para fib(2) e nunca mais serão calculados (mesmo para valores superiores de 2, pois fib(2) já foi calculado e guardado)

ps : adicionalmente, fib(1) pode ser "recalculado" novamente para o caso de fib(3), mas além disso, tudo recairá nsobre valores já calculados e guardados em "m"

Editado por HappyHippyHippo

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

A implementação mais "normal" quando aplicamos memoization (ou seja, top-down) é colocar no inicio da chamada recursiva algo como o "if m[n] == 0" deste código, e nunca fazer essa verificação antes das chamadas recursivas. Isto porque alguns problemas de PD têm vários casos especiais e assim evitamos estar a fazer o teste sempre que é chamado um problema mais pequeno, e se neste caso é só 1 vez, noutros problemas podem ser 4 ou 5.

Já agora, uma implementação bottom-up usando programação dinâmica seria algo deste género:

def fib(n):
 m[0] = 0
 m[1] = 0
 for i in range(2, n):
m[i] = m[i-1] + m[i-2]
 return m[n]

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

não, estás enganado no que toca ao processo de cálculo.

nota que no meu código, na verificação se m[n] for diferente de zero, então não existe a chamada recursiva para calculo de fib(n), logo, quanto muito, fib(0) e fib(1) serão calculados 1 vez cada para fib(2) e nunca mais serão calculados (mesmo para valores superiores de 2, pois fib(2) já foi calculado e guardado)

ps : adicionalmente, fib(1) pode ser "recalculado" novamente para o caso de fib(3), mas além disso, tudo recairá nsobre valores já calculados e guardados em "m"

Sim, tens razão, a reutilização é reduzida. Mas isso também é mais um motivo para não perder tempo a guardar os valores. Estar a guardar valores, e depois não usar o valores guardados (nem na única vez em que são necessários) parece-me ainda menos útil.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

Sim, tens razão, a reutilização é reduzida. Mas isso também é mais um motivo para não perder tempo a guardar os valores. Estar a guardar valores, e depois não usar o valores guardados (nem na única vez em que são necessários) parece-me ainda menos útil.

nota que eu não percebo nada de python.

ao olhar para o código deduzi que "m" fica acessivel a um nível global, e ao aplicar o código que fiz, ticas com m correctamente preenchido com os números de fibonacci até n. algo que é útil para trabalhos extras ao cálculo de fib(n), como por exemplo, o desenho da espiral de fibonacci.

o que quer dizer é que apesar o cálculo de m só é relativo para um caso reduzido de casos (olha que i = 0 e/ou i = 1 são necessários para fib(2) e fib(3)) o trabalho de os os guardar é para manter coerente os valores contidos em "m".

Editado por HappyHippyHippo

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade