17.0 program. DINÂMICA

Como resolver problemas grandes e difíceis, usando o conceito de programação dinâmica, para obter uma solução ideal?

PROBLEMAS:

  1. Menor distância
  2. Caminho crítico de menor distância
  3. Encontrar caminhos curtos e mais baratos 

CONCEITO

A programação Dinâmica (DP) é uma abordagem criativa para a solução de problemas que envolve a decomposição de um problema grande e difícil em uma série de problemas menores e fáceis de resolver. Resolvendo essa série de problemas menores, podemos montar um resumo ideal para o grande problema inicial.

Uma discussão detalhada desse modelo pode ser encontrada no desenvolvimento de modelos mais avançados. Para encontrar a menor distância do caminho através da rede, usaremos a seguinte recursão de PD: F (i) = min [D (i, j) + F (j)] j 

onde 

    • F (i) é a distância mínima de deslocamento do ponto i ao ponto de destino final e 
    • D (i, j) é a distância do ponto i ao ponto j.

Em palavras, a distância mínima do nó i ao nó terminal é o mínimo em todos os pontos alcançáveis ​​em um único arco de i da soma da distância entre i e o nó adjacente mais a distância mínima entre o nó adjacente e o nó terminal.