4) { while ($ads2 == $ads1) { $ads2 = rand(1, $slides); } } $ads3 = rand(1, $slides); if ($slides > 4) { while (($ads3 == $ads2) || ($ads3 == $ads1)) { $ads3 = rand(1, $slides); } } ?>
INF1771 - INTELIGÊNCIA ARTIFICIAL  
TRABALHO 1 BUSCA HEURÍSTICA  
Descrição:  
Um vírus que transforma pessoas em zumbis está se espalhando pelo mundo. Por  
sorte, a sua cidade ainda está segura e ninguém foi infectado. Mas isso pode mudar a  
qualquer momento, por isso é necessário se preparar para o pior. A melhor maneira de  
se preparar para esse apocalipse zumbi é estocando água, alimentos, armas e  
munição em casa. Na sua cidade existem lojas especializadas na venda destes itens,  
você deve ir até elas para comprar os itens do seu kit de sobrevivência zumbi. O tempo  
está passando e é necessário estocar estes itens o mais rápido possível, por isso você  
não pode perder tempo dando voltas pela cidade, você deve planejar todos os seus  
passos antes mesmo de sair de casa. Tome cuidado para não perder tempo no transito.  
Boa sorte!”  
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20  
1
2
3
4
5
6
7
8
9
A
F
1
0
1
2
3
4
5
6
7
8
9
0
1
1
1
1
1
1
1
1
1
2
W
G
Figura 1. Mapa da Cidade.  
O Trabalho 1 consiste em implementar um agente capaz de locomover-se por essa  
cidade e comprar os itens buscados de forma inteligente. Para isso, você deve utilizar o  
algoritmo de busca heurística A*.  
O agente deve ser capaz de calcular automaticamente a melhor rota para comprar  
água, alimentos, armas, munição e, por ultimo, voltar para casa (posição [3,3] no  
mapa).  
Infelizmente você não é o único que está tentando comprar suprimentos para sobreviver  
ao apocalipse zumbi. Todos os moradores da cidade estão fazendo o mesmo. Com isso,  
o transito da cidade está caótico. Por sorte, o boletim de transito continua sendo  
atualizado, o que permite ao agente planejar uma rota que evite perder muito tempo no  
transito.  
Existem 5 níveis de congestionamento:  
Nível 1 Tempo Gasto: +3 min  
Nível 2 Tempo Gasto: +8 min  
Nível 3 Tempo Gasto: +14 min  
Nível 4 Tempo Gasto: +20 min  
Nível 5 Tempo Gasto: +30 min  
A melhor rota é aquela na qual o agente leva menos tempo para comprar os itens do kit  
de sobrevivência zumbi.  
Informações Adicionais:  
A cidade deve ser representada por uma matriz 20 x 20 (igual à mostrada na  
Figura 1).  
O agente sempre inicia e termina a jornada na casa dele (posição [3, 3]).  
O agente não pode andar na diagonal, somente na vertical e na horizontal.  
A cidade deve possuir a estrutura de ruas ilustrada na Figura 1. As lojas são  
representadas pelas seguintes letras:  
o W Loja de Água  
o F Loja de Alimentos  
o G Loja de Armas  
o A Loja de Munição  
O mapa da cidade deve ser configurável, ou seja, deve ser possível modificar  
as ruas e a posição das lojas. O mapa pode ser lido de um arquivo de texto ou  
deve ser facilmente editável no código.  
Todas as ruas do mapa possuem um nível de congestionamento. Essa  
informação também deve ser configurável no mapa.  
Deve existir uma maneira de visualizar os movimentos do agente, mesmo que a  
interface seja bem simples. Podendo até mesmo ser uma matriz desenhada e  
atualizada no console.  
O algoritmo deve ser capaz de perceber quando não existe nenhum caminho  
para chegar ao destino. Exemplo: estar preso em uma rua sem saída.  
O programa também deve exibir o tempo gasto pelo agente enquanto ele se  
movimenta pela cidade.  
O trabalho pode ser feito individualmente ou em dupla.  
O programa pode ser implementado em qualquer linguagem.  
Programa Base (Projeto do Visual Studio 2010):  
https://edirlei.com/aulas/ia_2012_2/Trabalho1ProgramaBase_2012_2.rar  
Forma de Avaliação:  
Será avaliado se:  
(
(
(
1) O trabalho atendeu a todos os requisitos especificados anteriormente;  
2) Os algoritmos foram implementados e aplicados de forma correta;  
3) O código foi devidamente organizado;  
Bônus:  
(
1) A interface gráfica não é o objetivo desse trabalho, mas quem implementar uma  
boainterface gráfica (2D ou 3D) para representar o ambiente e o agente  
receberá 2 pontos extras na nota.  
(
2) Para encontrar a melhor ordem para pegar os itens do kit de sobrevivência zumbi  
é necessário resolver o problema do caixeiro viajante (travelling salesman).  
Quem resolver esse problema usando um algoritmo genético receberá 1 ponto  
extra na nota.  
Data de Entrega:  
9/09  
1
Forma de Entrega:  
O programa deve ser apresentado na aula do dia 19/09 (quarta) e enviando até o mesmo  
dia para o email edirlei.slima@gmail.com.