Leia a descrição dos problemas e responda as perguntas abaixo. Você pode precisar reler os capítulos 3 e 4 do livro (Russel&Norvig).

• Procure descobrir o que é o problema do caixeiro viajante.
  • Modele o problema de forma que seja possível usar um algoritmo de busca no espaço de estados.
  • Com se comportariam a busca em largura e a busca em profundidade neste problema, da maneira como você modelou?
  • Mostre uma heurística que possa ser usada com este problema, para que seja possível usar algoritmos de busca com informação como o A*.
  • Usando sua heurística, o algoritmo de busca gulosa leva à solução ótima? Por que?
  • Usando sua heurística, o algoritmo A* leva à solução ótima? Por que?
• Uma indústria produz artefatos aço. Grandes chapas de aço, de tamanho MxN, são cortadas para fazer diversas peças. Há três peças que podem ser produzidas, e cada uma precisa de um pedaço diferente da chapa de aço: uma peça precisa de um recorte de tamanho (a x b), outra de um recorte de tamanho (c x d) e outra de um recorte de tamanho (e x f).
  Como os três recortes três tem formato diferente, é importante determinar quantas peças de cada tipo devem ser produzidas com cada chapa de aço, além de determinar como os cortes devem ser feitos de maneira a minimizar as sobras de aço (que é muito caro). Ou seja, o que se quer é determinar como "retalhar" a chapa de aço em pedaços de três tipos, minimizando a sobra.
  
  • Mostre como modelar o problema acima de forma que seja possível usar um algoritmo de busca no espaço de estados. Pense cuidadosamente nas ações e nos estados.
  • Mostre uma heurística que possa ser usada com este problema, para que seja possível usar algoritmos de busca com informação como o A*.
  • Usando sua heurística, o algoritmo de busca gulosa leva à solução ótima? Por que?
  • Usando sua heurística, o algoritmo A* leva à solução ótima? Por que?