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  
LISTA DE EXERCÍCIOS 2  
Aluno:  
1
. Você precisa construir um sistema para auxiliar os usuários do metro de Paris a encontrar  
a melhor rota entre as diversas estações do metro.  
Considere que:  
O metro tem somente 4 linhas (Figura 1);  
A distância real entre duas estações é dada pela tabela 1 e a distância em linha  
reta é dada pela tabela 2;  
A velocidade média de um trem é de 40 km/h;  
O tempo gasto para trocar de linha dentro da mesma estação é de 5 minutos;  
Figura 1: Linhas do metro de Paris.  
Tabela 1: Distancias reais entre as estações do metro de Paris.  
Tabela 2: Distancias em linha reta entre as estações do metro de Paris.  
(a) Descreva o problema em termos de um problema de busca definindo o espaço de  
estados, o estado inicial, o estado final, os operadores de transição entre os estados  
(ações) e a função de avaliação utilizada pelo algoritmo de busca heurística A*.  
(
b) Realize uma busca utilizando o algoritmo A* para encontrar o melhor caminho para  
chegar a estação E7 partindo da estação E13. Construa a árvore de busca criada pela  
execução do algoritmo apresentando os valores de f(n), g(n) e h(n) para cada nó.  
2
. Utilize o algoritmo de busca local Hill Climbing na rede mostrada abaixo para chegar ao nó  
em formato de estrela (n0) partindo do nó n18. Mostre a sequencia de nós visitados  
durante a execução do algoritmo. Utilize a distancia em linha reta aproximada para  
calcular a função heurística. Caso o algoritmo fique preso em um mínimo local, utilize o a  
variação do Hill Climbing com reinicialização aleatória.  
2
3
23  
1
2
12  
8
5
5
5
1
0
10  
10  
10  
3
. O grafo abaixo mostra a localização de 6 itens em um mapa e as respectivas distâncias em  
quilômetros:  
Tem-se um problema onde é necessário coletar os 6 itens com o menor custo possível  
usando um algoritmo genético.  
a) Proponha uma maneira de codificar os cromossomos.  
b) Defina uma função de aptidão para avaliar a qualidade dos cromossomos.  
c) Defina como o método de seleção dos pais será utilizado.  
d) Defina os operadores genéticos de recombinação e mutação.  
e) Gere uma população inicial de 4 cromossomos e avalie a aptidão deles.  
f) Aplique os operadores de recombinação e mutação sobre essa população para gerar  
uma nova geração, em seguida avalie a aptidão da nova geração. Repita esse processo  
por 5 gerações ou até que a solução do problema seja encontrada.  
5
. Considere a seguinte equação:  
3 2  
x + y - w + z + x = 256  
8
a) Proponha uma maneira de codificar os cromossomos.  
b) Defina uma função de aptidão para avaliar a qualidade dos cromossomos.  
c) Defina como o método de seleção dos pais será utilizado.  
d) Defina os operadores genéticos de recombinação e mutação.  
e) Gere uma população inicial de 4 cromossomos e avalie a aptidão deles.  
f) Aplique os operadores de recombinação e mutação sobre essa população para gerar  
uma nova geração, em seguida avalie a aptidão da nova geração. Repita esse processo  
por 5 gerações ou até que a solução do problema seja encontrada.  
6
. Problema SAT  
Seja x = (x1, x2,..., xn) um vetor de n variáveis booleanas (i.e. cada variável xi assume um dos  
valores em {0,1}). Seja f(x) = [c1(x) c2(x) ,..., cm(x)] uma fórmula normal conjuntiva com  
m cláusulas, onde cada cláusula cj(x) é uma disjunção de literais, e um literal é uma das  
variáveis booleanas ou sua negação.  
Por exemplo, considere um vetor com três variáveis x = (x1, x2, x3). Um exemplo de fórmula  
normal conjuntiva seria:  
f(x) = [(x1) (¬x2)(x2 ¬x3) (x1 ¬x3)]  
Composta pelas seguintes cláusulas:  
c1(x) = (x1)  
c2(x) = (¬x2)  
c3(x) = (x2 ¬x3)  
c4(x) = (x1 ¬x3)  
Uma fórmula é dita satisfatível quando existe uma atribuição de valores para (x1, x2,..., xn)  
tal que todas as cláusulas da fórmula sejam satisfeitas, isto é, cj(x) = 1 para j=1,...,m. No  
exemplo acima, f(x) é satisfatível e x = (1, 0, 0) é uma possível atribuição de valores para as  
variáveis x1, x2 e x3 que tornam verdadeiras todas as quatro cláusulas da fórmula.  
O problema SAT consiste em: dada uma fórmula, responder se a fórmula é satisfatível ou  
não. Encontrar uma atribuição de valores que satisfaçam uma dada fórmula é uma tarefa  
que pode ser formulada como um problema de busca. Assim, para um conjunto qualquer  
de variáveis x = (x1, x2,..., xn) e uma dada fórmula f(x) = [c1(x) c2(x) ,..., cm(x)], proponha  
uma solução para o problema SAT como Algoritmos Genéticos.  
Para isso, use o seguinte caso base:  
(¬x ¬z y) (¬y z) (x ¬z) (y) (¬y ¬x ¬w z)  
a) Proponha uma maneira de codificar os cromossomos.  
b) Defina uma função de aptidão para avaliar a qualidade dos cromossomos.  
c) Defina como o método de seleção dos pais será utilizado.  
d) Defina os operadores genéticos de recombinação e mutação.  
e) Gere uma população inicial de 4 cromossomos e avalie a aptidão deles.  
f) Aplique os operadores de recombinação e mutação sobre essa população para gerar  
uma nova geração, em seguida avalie a aptidão da nova geração. Repita esse processo  
por 5 gerações ou até que a solução do problema seja encontrada.