programação dinâmica, os princípios básicos

Para selecionar a solução ótima ao executar as tarefas de programação às vezes são necessários para classificar grandes quantidades de combinações de dados que carrega a memória do computador pessoal. Tais métodos incluem, por exemplo, o método de programação de "dividir para reinar". Neste caso, o algoritmo fornece problema de separação em subtarefas menores separadas. Este método só é aplicável em casos em que as pequenas subtarefas são independentes entre si. Para evitar a execução de um trabalho desnecessário, se sub-tarefas interdependentes, usa o método de programação dinâmica proposta americana R.Bellmanom na década de 50.

o método

A programação dinâmica é determinar a melhor solução do problema n-dimensional, compartilhando seus n estágios separados. Cada um deles é uma sub-tarefa com relação a uma variável.

A principal vantagem dessa abordagem pode ser considerado que os desenvolvedores envolvidos no problema de otimização unidimensional subtarefas em vez de um problema n-dimensional, e nosso principal objectivo vai "bottom-up".

É aconselhável aplicar uma programação dinâmica nos casos em que as sub-tarefas estão inter-relacionados, ou seja, Eles têm módulos comuns. O algoritmo fornece a decisão de cada uma das sub-tarefas uma vez, e as respostas de poupança é realizada em uma mesa especial. Isso torna possível para não calcular uma resposta quando eles se encontraram novamente com a mesma sub-tarefa.

tarefa de programação dinâmica resolve o problema de otimização. O autor deste método foi formulado por princípio optimality R. Bellman: qualquer que seja o estado inicial de cada um dos passos e a solução definido neste passo, todas as seguintes características para escolher o melhor em relação ao estado, que recebe o sistema no final do passo.

O método melhora o desempenho das tarefas resolvidas por meio de variantes, ou de recorrência.

algoritmo tarefa edifício

algoritmo de programação dinâmica envolve a construção de tais tarefas que a tarefa assim é dividida em duas ou mais sub-tarefas para a sua solução é composta de uma solução ideal para todas as sub-tarefas, ele inclui. Além disso, é necessário escrever uma relação de recorrência, e calculando os valores dos parâmetros ideais para a tarefa como um todo.

Às vezes, no 3º passo é memorizar algumas informações adicionais de fundo sobre o progresso de cada tarefa. Isto é chamado o movimento de retorno.

método de aplicação

A programação dinâmica é aplicada quando existem duas características:

• óptima para subtarefas;
• presença no problema da sobreposição de sub-problemas.

Resolver o problema de otimização por programação dinâmica, primeiro você precisa para descrever a estrutura da solução. A tarefa tem que ser ideal se a solução é composta das melhores decisões de suas subtarefas. Neste caso, é aconselhável o uso de programação dinâmica.

A segunda propriedade do problema, essencial neste método, – um pequeno número de sub-tarefas. solução recursiva do problema utilizando os mesmos sub-problemas sobrepostas, cujo número depende do tamanho da informação inicial. A resposta é armazenada em uma mesa especial, o programa economiza tempo usando esses dados.

Especialmente eficaz é o uso de programação dinâmica quando a tarefa é essencialmente necessário para tomar decisões em etapas. Por exemplo, considere um exemplo simples do problema da substituição e reparação de equipamentos. Digamos que na fábrica de máquinas de fundição para a produção de pneus ao mesmo tempo fazer o pneu em duas formas diferentes. No caso em que uma das formas falhar, é necessário desmontar a máquina. É compreensível que, por vezes, mais rentável para substituir e uma segunda forma, a fim de desmontar a máquina em caso e esta forma será inviável na próxima fase. Especialmente desde que é mais fácil para substituir tanto a forma de trabalho antes de começar a falhar. método de programação dinâmica determina a melhor estratégia na questão da substituição dessas formas, tendo em conta todos os fatores: os benefícios de formulários contínuos de exploração, perda de tempo de máquina parada, o custo de pneus descartados e muito mais.