O interesse neste problema não reside apenas em sua solução, mas, também, em desenvolver um método que possa resolver outros problemas similares. Para tanto, será apresentada, a seguir, uma terminologia que será usada nestes problemas.

 

Estado: Um estado é uma configuração do sistema, e é identificado por um rótulo que indica suas propriedades. No problema apresentado na Figura 1, um estado é uma cidade.

 

Estágio: Programação Dinâmica diz respeito a sistemas que evoluem de um estado para outro. Um estágio é um passo singular, e corresponde à transição do sistema de um estado para o próximo adjacente. Na Figura 1, o movimento do viajante, de uma cidade para a próxima, corresponde ao estágio. Cada caminho cidade A para a cidade H tem três estágios.

 

Ação: Em cada estado existe um conjunto de ações viáveis, das quais uma deverá ser escolhida e executada. No exemplo da Figura 1, no estado (cidade C) existem três ações viáveis: ir para a cidade E; ir para a cidade F; ou ir para a cidade G. Resolver o problema de Programação Dinâmica significa, dado um objetivo, achar a melhor sequência de ações.

 

Plano: Um plano é um conjunto de ações, no qual para cada estado é especificado uma ação. Um plano ótimo é o melhor conjunto de ações considerando o objetivo fixado.

 

Retorno: O retorno é algo que o sistema gera, sobre um estágio ou processo. No problema da Figura 1, é a distância percorrida entre uma cidade e a próxima. O retorno é, usualmente, algo do tipo: lucro; custo; distância; consumo de recursos; e etc.

 

Valor do Estado: O valor do estado é uma função dos retornos gerados, quando o sistema evolui de um estado inicial para um estado final, através de um plano dado. No caso do problema da viagem, o valor do estado, para um determinado plano, corresponde á distância desta cidade até a cidade terminal. O valor de um estado sob um plano ótimo é o valor ótimo.

 

OBSERVAÇÃO: Diferentes problemas serão estudados, sendo, entretanto, comuns a todos a estrutura da Programação Dinâmica, que pode, para o exemplo apresentado ser assim descrita: