Jump to content

Programação dinâmica - Memoization / Knapsack


Localhost
 Share

Recommended Posts

Boas, entrei finalmente no mundo da programação dinâmica e estou a achar terrivelmente dificil de percebê-la.

Estive a ver alguns problemas e o knapsack é o que estou agora.

A minha dúvida é como usar memoization para aumentar a velocidade (recursivamente) da resolução do problema? Por favor, tenham em atenção que me estou a tentar guiar por este problema: http://www.dcc.fc.up.pt/oni/problemas/2008/qualificacao/probC.html

Já agora, se tiverem algumas dicas sobre programação dinâmica em geral, estou aberto a opiniões.  👍

here since 2009

Link to comment
Share on other sites

Estou a tentar dificuldades em programação dinâmica na generalidade. Já entendi que para resolver um problema usando programação dinâmica tenho que resolver todos os sub-problemas e só depois basear a minha resposta para o problema original nesses sub-problemas. Não consigo é aplicar esta teoria a nenhum problema..

here since 2009

Link to comment
Share on other sites

Estive algum tempo a descansar de programar, e a aproveitar o Verão, mas agora voltei ao treino 🙂

Estou no mesmo problema que me deixou preso na USACO quando parei.

Antes, estava a tentar formular uma solução de programação dinâmica, sem me preocupar com solução recursiva, mas não estava a chegar a lado nenhum.

Agora, utilizando esta ideia da memoization, apliquei a solução recursiva, e passa bastante bem no tempo.

O problema é o seguinte: No último caso, dado o grande tamanho do input, o programa chega sempre a um ponto que dá segmentation fault, supostamente por não poder alocar mais memória para a função recursiva :/

O problema é o seguinte: Dado um conjunto de primitivos (conjuntos de caracteres) e uma string, calcular o maior prefixo que se consegue fazer para a string com o conjunto de primitivos dados (pode-se utilizar todos ou não).

Já tentei optimizar ao máximo (por exemplo, em vez de usar strncmp para ver se o primitivo "cabia" naquele local da string, utilizei um ciclo for, e funcionou, já que a função avançou mais em profundidade, mas continua a dar segmentation fault, apesar de estar muito perto do fim :/).

A função recursiva é a seguinte:

void dfsm(int p) {
  int i,j,k;
  max = p>max?p:max;
  if(p == sl || M[p])
    return;
  for(i = 0; i < cP; ++i) {
    //compare
    k = 1;
    for(j = 0; j < P[i].l; ++j) {
      if(P[i].p[j] != S[p+j]) {
        k = 0;
        break; } }
    if(k)
      dfsm(p+P[i].l); }
  M[p] = 1;
  return; }

P -- array de primitivos. Cada primitivo é uma estrutura com os seguintes elementos: p (a string do primitivo, com 11 caracteres) e l (o comprimento da string do primitivo).

M -- array de memoization. Dado que quando se processava a árvore a uma certa profundidade, esta seria sempre igual, independentemente dos anteriores, basta gravar quais as posições que já foram processadas (não posso processar caracter a caracter, pois os primitivos podem ter comprimentos variáveis -- foi o que tentei fazer com DP, e não deu).

Onde li acerca de memoization, dizia para primeiro guardar os resultados numa array, e depois transformar a solução recursiva em iterativa, de forma a conseguir uma solução em DP, mas neste caso não vejo como faço isso, devido aos comprimentos variáveis dos primitivos.

Alguma ajuda? (o problema é "The Longes Prefix" da secção 2.3 da USACO).

Link to comment
Share on other sites

Não consigo perceber o que estás a fazer, mas sei que tu não estás a usar memoization.

Teoricamente, a solução recursiva constroi a resposta para um valor grande em função de valores menores. Tu estás a fazer ao contrário, a começar por baixo. Tens uma mistura das duas coisas, DP e memoization.

Link to comment
Share on other sites

O que fiz foi o seguinte:

Em cada "nível" (profundidade), processo uma letra da string, e vejo se essa letra e as seguintes correspondem a algum dos primitivos. Se sim, salto x letras à frente (x = comprimento do primitivo), e testo se tem algum primitivo que possa preencher essa letra e as seguintes.

Sempre que o nível em que estamos é maior que o comprimento do prefixo máximo registado, actualizamos esse máximo.

O que eu chamei de memoization foi o seguinte: como usei DFS, estaria sempre a recalcular os resultados a um determinado nível, portanto achei inútil fazer isso, e coloco numa array se esse nível já foi calculado ou não.

O problema disto é que não estou a ver como eliminar a recursividade que me está a dar problemas de memória, ou como evitar esses problemas. Alguma ideia?

Link to comment
Share on other sites

Tens razão nisso ... fazia a verificação antes, ao usar o strncmp, e continuava a dar-me o mesmo problema :S

E mesmo assim, o problema não é esse de certeza, pois ao usar o gdb, verifico que ele pára na chamada da função, da seguinte forma:

Program received signal SIGSEGV, Segmentation fault.
0x00000000004006fc in dfsm (p=Cannot access memory at address 0x7fffff7feffc
) at prefix.c:23
23	void dfsm(int p) {

Através da verificação do valor de max, sei que o p mais alto verificado foi 190578.

A solução oficial é diferente, e assumo que não tenha chegado lá devido a esse segmentation fault :/

EDIT: Agora lembrei-me que me lembrei desse pormenor quando fiz o código.

S[p+j] nunca rebenta a array, pois a posição mais alta é sempre 0, logo a comparação dá erro, fazendo break aí (não pode dar igual, pois nunca verifico o 0 do primitivo)

Link to comment
Share on other sites

No worst case precisas de 3.8 MB da stack, não percebo o motivo de crashar.

Muda isso para iterativo.

Também não percebo bem o motivo de crashar, e por isso queria passar para iterativo.

No entanto, não estou a ver como ultrapassar o pormenor do comprimento variável dos primitivos.

Alguma sugestão?

Link to comment
Share on other sites

Cinary, estamos falar deste problema: http://olympiads.win.tue.nl/ioi/ioi96/contest/ioi96p.html ?

Se sim, a observação chave é perceber que podes repetir os primitivos, ou seja, chegado à posição P... não importa o que está para trás! Só queres saber o melhor a partir daí...

Se precisares de mais ajuda diz.

Sim, é esse o problema.

A minha solução recursiva faz uso desse facto para poupar no tempo, e funciona, só que me dá segmentation fault no maior caso da USACO (supostamente devido a rebentar a stack, o que acho estranho :/).

O problema é que não se pode ser tão literal acerca de na posição P não interessar o que está para trás.

Por exemplo:

AAB BCA

e a string:

AABCA

O resultado é três, mas se eu percorrer a string um por um, tenho de fazer um check acerca do que está para trás, para saber se posso ou não colocar o primitivo BCA na string.

No entanto, também não posso saltar para o fim desse primitivo.

Por exemplo, com o conjunto:

A AAB BCA

O resultado seria 5, e não chegaria lá se saltasse para a frente no primitivo AAB (já que assim não iria chegar ao início do BCA).

Isto é que me está a dar mais dificuldade: como tratar destes casos especiais. Recursivamente é fácil, basta colocá-los em ramos diferentes. Iterativamente é que tenho de pensar mais acerca de como fazê-lo (se calhar o meu cérebro ainda está meio adormecido das férias, mas tem de começar a aquecer xD)

Link to comment
Share on other sites

Sim, é esse o problema.

A minha solução recursiva faz uso desse facto para poupar no tempo, e funciona, só que me dá segmentation fault no maior caso da USACO (supostamente devido a rebentar a stack, o que acho estranho :/).

Não tenho aqui os dados da minha conta na USACO. Que limites tem lá, já agora? Limites do tamanho do conjunto de primitivos, tamanho de cada um deles e tamanho da string "grande".

O problema é que não se pode ser tão literal acerca de na posição P não interessar o que está para trás.

Podes sim. Eu percebi o que estás a fazer, mas estás a complicar um problema "simples".

Seja best[p] o melhor prefixo que consegues fazer a partir da posição p e, como usas C++, seja 0 a posição inicial. Então, o problema que está a resolver é calcular best[0]. Agora, imagina uma solução que passa por todos os p possíveis uma única vez. Como calcular o melhor de best[p]? Se um determinado primitivo de tamanho T encaixa nessa posição (ou seja, a começar aí), então T+best[p+T] é candidato a ser o melhor possível best[p]. Nota que para calcular best[p+T], não importa o que está para trás. O que importa é perceber se chegarmos aí, qual o melhor possível.

Faço-me entender, ou queres que explica ainda com mais detalhe? 😞 Se quiseres fazer isto iterativo, qual a ordem que deves usar?

Já agora, coloquei um tutorial de PD aqui no P@P: http://www.portugal-a-programar.pt/index.php?showtopic=36896

Espreita e vê se te pode ajudar a perceber melhor os conceitos. E sim, de certeza que nas IOI'2010 vai sair algures PD! 🙂

Link to comment
Share on other sites

Bom, consegui pensar numa solução intermédia que parece que funciona xD

É o seguinte: o que me estava a dificultar as ideias era quando dois primitivos podiam ser colocados no mesmo local, e por isso usei recursividade. No entanto, a função chamava-se mesmo quando apenas um primitivo era colocado lá (esse caso resolve-se muito facilmente 😞). Então a minha solução foi a função apenas usar recursividade em casos onde seja necessário (quando mais do que um primitivo pode ser posto no mesmo local). Nos outros casos, avança recursivamente, evitando que assim a stack rebente.

Infelizmente, não consigo confirmar, pois a USACO parece estar com um problema no grader, já que me dá este erro:

  > Run 1: Execution error: Your program had this runtime error:
        Illegal file open (/dev/urandom). The program ran for 0.000 CPU
        seconds before the error. It used 1912 KB of memory. 

(o problema é no grader e não no programa pois submeti programas antigos que funcionavam perfeitamente, e já mandei um mail a avisar).

Mas para os interessados, resultou nisto:

void dfsm(int p) {
  int c = 1,n,i,j,k;
  while(c) {
    n = 0;
    c = 0;
    max = p>max?p:max;
    if(p == sl || M[p])
      return;
    for(i = 0; i < cP; ++i) {
      //compare
      k = 1;
      for(j = 0; j < P[i].l; ++j) {
        if(P[i].p[j] != S[p+j]) {
          k = 0;
          break; } }
      if(k) {
        if(n)
          dfsm(p+P[i].l);
        else
          c = n = P[i].l; } }
    M[p] = 1;
    p += n; }
  return; }

Quanto aos limites:

Entre 1 e 200 primitivos, cada um com comprimento entre 1 e 10.

A string pode ter um comprimento entre 1 e 200000.

Vou pensar no que disse sobre a solução em DP, e vou ler os materiais que colocou aqui acerca disso, a ver se percebo como é que estou a complicar algo que me dizem ser muito simples xD

Obrigado pelo vosso tempo.

EDIT: Percebi agora mesmo a sua solução ... tão simples xD Estava a fazer completamente ao contrário, de forma a evitar percorrer a string toda se não for necessário.

Vou agora fazer uma solução baseada na sua explicação, a ver se compreendi mesmo bem.

A sua solução baseia-se em encontrar o melhor prefixo para a posição p, com base nos primitivos, enquanto a minha baseia-se em encontrar o ponto onde é impossível colocar mais primitivos, a partir do início da string, daí eu estar a complicar o problema.

Link to comment
Share on other sites

EDIT: Percebi agora mesmo a sua solução ... tão simples xD Estava a fazer completamente ao contrário, de forma a evitar percorrer a string toda se não for necessário.

Vou agora fazer uma solução baseada na sua explicação, a ver se compreendi mesmo bem.

Também podes evitar percorrer a string toda se fizeres pela ordem "normal" com memoization, ou seja, só calcular as posições onde é possível chegar lá. Mas o essencial é perceberes como lidar com o que te estava a criar dificuldades (vários primitivos que encaixam no mesmo sítio).

Em todo o caso, se os testes estiverem bem feitos, haverá um caso onde realmente tens de percorrer a string "toda" 😞

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.