Concursos públicos

Uma forma de analisar e comparar o desempenho de algoritmos de busca heurística é utilizar um problema bem conhecido como referência. Um exemplo desse tipo de problema é o cálculo de rotas entre diferentes cidades. No grafo ilustrado acima, cada nó representa uma cidade distinta, e cada ramo, uma rodovia que interliga as cidades representadas pelos nós que ele une, cujo peso indica a distância, em km, entre essas cidades pela rodovia. Suponha que se deseje encontrar a melhor rota entre as cidades A e M, indicadas nesse grafo. Considere, ainda, os valores indicados na tabela abaixo como distância em linha reta, em km, de cada cidade para a cidade M.

A partir dessas informações, julgue os itens seguintes, relativos a algoritmos de busca.

I - Utilizando-se o algoritmo A*, a rota ente A e M encontrada no problema acima é ACDFLM e o custo do caminho é 56,18.

II - Utilizando-se a busca gulosa, a rota encontrada no problema acima é ACDFLM.

III - Para utilizar algoritmos de busca heurística, deve-se definir uma heurística que superestime o custo da solução.

IV - O A* é um algoritmo ótimo e completo quando heurísticas admissíveis são utilizadas.

V - No simulated annealing, é possível haver movimentos para um estado com avaliação pior do que a do estado corrente, dependendo da temperatura do processo e da probabilidade de escolha.

Estão certos apenas os itens