Problema do Metrô de Paris

O problema do metrô de Paris é muito utilizado nas aulas de Inteligência Artificial para praticar heurísticas. No exemplo abaixo há poucos caminhos possíveis, mas se utilizar o mapa de Paris inteiro o tempo necessário para encontrar o caminho mais rápido cresce muito tornando impraticável a solução sem uma heurística apropriada.

O problema

O objetivo principal é desenvolver um algoritmo que a partir das distâncias entre as estações consiga em tempo viável encontrar o caminho mais rápido entre duas estações.

O problema é que além de informar a velocidade dos trens, é necessário contabilizar um determinado tempo para troca de linha. Cada cor determina uma linha diferente do metrô. Deve ser possível selecionar a estação de origem e destino e é obvio que é necessário traçar o caminho a ser percorrido e o tempo total de viagem para instruir o passageiro.

Você pode ver as tabelas com as distâncias em linha reta entre cada estação clicando nas abas da tabela abaixo.

A solução

Escolha a estação origem: E1E2E3E4E5E6E7E8E9E10E11E12E13E14 e a estação de destino: E1E2E3E4E5E6E7E8E9E10E11E12E13E14     

Velocidade média do trem: km/h e tempo de troca de linha: min

Mapa do metrô Tabela de distâncias em linha reta Tabela de minutos em linha reta

km	E1	E2	E3	E4	E5	E6	E7	E8	E9	E10	E11	E12	E13	E14
E1	0	11	20	27	40	43	39	28	18	10	18	30	30	32
E2	11	0	9	16	29	32	28	19	11	4	17	23	21	24
E3	20	9	0	7	20	22	19	15	10	11	21	21	13	18
E4	27	16	7	0	13	16	12	13	13	18	26	21	11	17
E5	40	29	20	13	0	3	2	21	25	31	38	27	16	20
E6	43	32	22	16	3	0	4	23	28	33	41	30	17	20
E7	39	28	19	12	2	4	0	22	25	29	38	28	13	17
E8	28	19	15	13	21	23	22	0	9	22	18	7	25	30
E9	18	11	10	13	25	28	25	9	0	13	12	12	23	28
E10	10	4	11	18	31	33	29	22	13	0	20	27	20	23
E11	18	17	21	26	38	41	38	18	12	20	0	15	35	39
E12	30	23	21	21	27	30	28	7	12	27	15	0	31	37
E13	30	21	13	11	16	17	13	25	23	20	35	31	0	5
E14	32	24	18	17	20	20	17	30	28	23	39	37	5	0

min	E1	E2	E3	E4	E5	E6	E7	E8	E9	E10	E11	E12	E13	E14
E1	0	22	40	54	80	86	78	56	36	20	36	60	60	64
E2	22	0	18	32	58	64	56	38	22	8	34	46	42	48
E3	40	18	0	14	40	44	38	30	20	22	42	42	26	36
E4	54	32	14	0	26	32	24	26	26	36	52	42	22	34
E5	80	58	40	26	0	6	4	42	50	62	76	54	32	40
E6	86	64	44	32	6	0	8	46	56	66	82	60	34	40
E7	78	56	38	24	4	8	0	44	50	58	76	56	26	34
E8	56	38	30	26	42	46	44	0	18	44	36	14	50	60
E9	36	22	20	26	50	56	50	18	0	26	24	24	46	56
E10	20	8	22	36	62	66	58	44	26	0	40	54	40	46
E11	36	34	42	52	76	82	76	36	24	40	0	30	70	78
E12	60	46	42	42	54	60	56	14	24	54	30	0	62	74
E13	60	42	26	22	32	34	26	50	46	40	70	62	0	10
E14	64	48	36	34	40	40	34	60	56	46	78	74	10	0

Este trabalho foi desenvolvido para a disciplina de Inteligência Artificial no curso de Ciência da Computação da Unisinos

Adicionar um comentário

e-mail:nome:

Links e parágrafos são identificados automaticamente
Negrito: **texto em negrito** = texto em negrito
Itálico: */texto em itálico*/ = texto em itálico
Trecho de código inline: ``<?php echo $var; ?>`` = <?php echo $var; ?>
Bloco de código:
```<?php
echo $var;
?>```

<?php
echo $var;
?>

Formatações disponíveisVeja o resultado da formatação

Repita os caracteres da imagem aqui:
Se não conseguir identificar a imagem clique sobre ela para recarregar

Enviar comentário

Gerson8/Mar, as 13:21

De mais sr Paulo Cazarotto! hehe

Responder