B17-01 Menor distância (DINAMB)

Objetivo

Ilustração de programação Dinâmica (ver Anderson, Sweeney & Williams, uma introdução à Mgr Science, 6ª Ed). Temos uma rede de 10 cidades. Queremos encontrar o comprimento da rota mais curta da cidade 1 para a cidade 10.

ETAPA 1:

Aqui está nosso conjunto primitivo de dez cidades, onde F (i) representa a distância mais curta da rota da cidade i até a última cidade: CITIES / 1..10/: F

ETAPA 2:

O conjunto derivado ROADS lista as estradas que existem entre as cidades (nota: nem todas as cidades.) Os pares são diretamente ligados por uma estrada e as estradas são assumidas de uma maneira.

ETAPA 3:

A seguir, é apresentada a programação de recursão dinâmica. Em outras palavras, a distância mais curta da cidade i à cidade 10 é a mínima em todas as cidades j alcançável a partir da soma da distância de i a j mais a distância mínima de j à cidade 10;

12345678910
1152
2131211
36104
41214
539
665
7810
85
92
10
DISTANCE MATRIX – ROUTES VS CITIES ( mi )


Solução (pt-br)

Modelo


Solution (en-us)

Model


Pagina 809
FONTE 6
LINGO the modeling Language and Optimizar
Lindo Systems Inc
Lindo Systems Inc, 2018

CATEGORIAS