Resolução Problema do metrô de Paris ssando busca A

Prévia do material em texto

Resolução Problema do metrô de Paris sando busca A*
Estado inicial: Qualquer uma das estações
Espaço de estados : Todos os estados situados (todas as estações de trem)
Estado final: Qualquer uma das estações
Acções possiveis : Mover para outra estação
Custo: Tempo
Funcão heuristica = custo do caminho do nó inicial até o nó n + valor da heurística do nó n até um nó objetivo
f(n) = g(n)+ h(n)
Analisando o problema temos duas funções :
 Função heuristica quando existe troca de linha onde acrescemos um tempo de 4 min:
f(n)= 
Função heuristica quando não existe troca de linhas
f(n)= 
Descreva o funcionamento do algoritmo em linguagem corrente .
Função BuscaAEstrela(EstaçãoInicial, FunçãoHeuristica,ListaOrdenada,EstaçãoFinal )
 Inicio 
 fronteira ← FazListaOrdenda(EstaçãoInicial)
loop do
 se VaziaListaOrdenda(fronteira) então 
	 retorna falha
	 nó ← RemoveListaOrdenda(fronteira)
se nó(Estação) for igual a (EstaçãoFinal)
 então
	 retorna Solução(EstaçãoFinal)
senao 
	 fronteira ← InsereListaOrdenda
 calcular nó de menor custo 
 se existir troca linha
 f(n) = g(n) + h(n)+ tempo de troca
 se não f(n) = g(n) + h(n)
 Mover para estação vizinha de menor Custo
Fim de Se
 Fim de loop
Fim
Desenhe a árvore de busca desenvolvida pelo A* para o seguinte caso:
Ei = estação 6 linha azula , Ef = estação 13 linha vermelha
E8
E3
E13
E7
E88
E4
E555
E6