Optimal substructure

Question

Eu estou tentando chegar a uma imagem mais completa do uso de ótima infra-estrutura da propriedade na programação dinâmica, mas eu fui cego, no qual temos de provar que qualquer solução ótima para o problema contém em si as soluções ideais para os sub-problemas.

Não seria o suficiente para mostrar que alguns solução ótima para o problema tem esta propriedade e, em seguida, usar isso para argumentar que, já que a solução construída pelo nosso algoritmo recursivo é pelo menos tão boa como a solução ideal, ele será o ideal?Em outras palavras, eu não o lugar onde na justeza do argumento para o nosso algoritmo precisamos que todas as soluções ótimas conter as soluções ideais para os sub-problemas.

Para esclarecer:

O CLRS definição de ótima infra-estrutura diz que "um problema apresenta ótima infra-estrutura se qualquer solução ótima para o problema contém em si as soluções ideais para subproblems".

Por que não teria ele não ser o suficiente para dizer que "um problema apresenta ótima infra-estrutura se alguns solução ótima para o problema contém em si as soluções ideais para subproblems"?

Answer 1

Eu fui incomodado um pouco por isso em minha pesquisa sobre algoritmos de aproximação, que envolve programas dinâmicos que encontram soluções aproximadamente ótimas. A maneira certa de pensar sobre a exatidão dos programas dinâmicos, acredito, é como uma redução (na teoria da complexidade) de um problema para um subproblema. Essa redução geralmente é aplicada recursivamente e com a memoização, mas esses são detalhes agora.

Deixe um problema e b ser o subproblema. Há apenas um subproblema porque podemos combinar vários subproblemas independentes em um através de um produto cartesiano generalizado. A redução consiste em duas funções: F, de uma instância a uma instância B e H, de uma solução B para uma solução A. A propriedade de correção que precisamos é que, para cada função g de cada B-instance para uma solução B ideal correspondente (o Oracle), a composição h. g. f é uma função de cada uma instância para uma solução APTIFICAÇÃO correspondente. (Se h precisar de acesso ao A-Instance, amplie B para que suas instâncias contenham uma instância de uma instância que devem ser copiadas na solução B correspondente.)

Para fazer o seu ponto, para uma determinada uma instância e uma solução ideal, não precisa existir um Oracle G, tal que o pipeline h. g. f produz essa solução da instância dada. (Em outras palavras, h não precisa ser superjetivo.) Por outro lado, h deve ser capaz de lidar com cada possível solução B possível de G para a instância B construída por f.

Uma estratégia comum para garantir que H está correto é encontrar uma função de "subestrutura" k de uma solução para soluções B e uma maneira de "splice" subestrutura, ou seja, uma prova que, dada uma solução de uma solução x e uma solução B não pior que k (x), existe uma solução a-solução 'não pior que x tal que k (x')= y. Então h pode otimizar sobre tudo na imagem inversa sob K de sua entrada. Não é necessário que a splicing se aplique a todas as soluções x, apenas uma ótima.

Answer 2

Em programação Dinâmica podemos dividir o problema para menores sub-problemas, fazer alguma manipulação e fornecer respostas para uma maior resposta muito semelhante à recursividade abordagem (e, por coincidência).

Agora, quando vamos para provar formalmente a exatidão de tal algoritmo, isto é feito por indução.Nós provamos que a nossa base de cláusula' está correto (geralmente muito fácil) e, em seguida, nós assumimos que qualquer problema menor do que o atual - também é o ideal.Em seguida, usamos esta hipótese para provar a exatidão de problema maior.

Se nós não sabíamos de todas as soluções ideais - que não seria capaz de provar que usando a um passo extra fomos capazes de modificar a solução ideal para o menor problema para a solução ótima para o problema maior - não seria apenas de não haver informações suficientes para provar essa afirmação.

Se soubéssemos que alguns dos subproblems são a solução ideal - não seria suficiente para assegurar que a utilização deste subproblem, que nós temos uma solução ideal para indeeds é o que precisamos para obter a solução ótima para o problema maior.

---

Dê uma olhada na mochila, por exemplo, e vamos ter um olhar em seu DP passo:

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

Se soubéssemos apenas um deles é ótima, não fomos capazes de provar que o algoritmo está correto, porque podemos ter o necessário outro caso, onde não temos solução ótima.

Se escolhemos f(x,i-1) no max() - poderia ter sido a escolha errada.Assegurando nós temos a solução ideal para todos os subproblems, temos certeza de que isso não pode acontecer.