Atividades De Inteligência Artificial

1. Verdadeiro ou falso? Justifique a resposta. Considere um problema de busca em que o fator de ramificação é 2, a profundidade máxima da árvore é 5 e a profundidade da solução mais rasa é 2. Neste caso, entre a busca em largura e profundidade em termos de complexidade de tempo, é mais indicado usar a busca em largura.

R: Verdadeiro. Pois como a altura da árvore é 5, se fossemos aplicar a busca em profundidade, caso o estado final estivesse do lado mais direito da árvore por exemplo, o algoritmo iria checar todo o lado esquerdo primeiro, checando até o último nível possível de cada ramificação até chegar na solução. Já na busca em largura, o algoritmo iria buscando o estado final nível por nível, verificando todos os nós de cada nível. Como a solução mais rasa está em 2 de profundidade, o algoritmo levaria menos tempo para encontrá-la buscando de nível em nível. Em termos de complexidade de tempo, temos que a busca em profundidade é O(bm), neste caso O(25), enquanto que a busca em largura é O(bd), ou seja, O(22).

1. O algoritmo de caminho heurístico é uma busca pela melhor escolha na qual a função objetivo é f(n) = (2-w)*g(n) + w*h(n). Para qual valor de w esse algoritmo se transforma no algoritmo A*? Que espécie de busca ele executa quando w = 0?

R: O algoritmo se transforma no algoritmo A* quando w = 1, pois nesse caso: f(n) = g(n) + h(n), que equivale justamente a busca A*. Quando w = 0: f(n) = 2*g(n), o que equivale à busca de custo uniforme (a multiplicação por 2 não altera a ordem em que os nós são expandidos).

---

1. Considere o espaço de busca abaixo, onde S é o estado inicial e G é o único estado que satisfaz o teste de objetivo. Os rótulos nas arestas indicam o custo de percorrê-las e a tabela ao lado mostra o valor de três heurísticas h0, h1 e h2 para cada estado. Quais são os nós expandidos pela busca A* usando cada uma das heurísticas (h0, h1 e h2)? Qual é a solução (caminho) encontrado por cada uma delas?

[pic 1]

[pic 2]

h0: f(S) = 0 + 0 = 0; f(A) = 5 + 0 = 5; f(B) = 2 + 0 = 2, f(C) = 2 + 2 + 0 = 4;
f(D) = 2 + 1 + 0 = 3.

h1: f(S) = 0 + 5 = 5; f(A) = 5 + 3 = 8; f(B) = 2 + 4 = 6; f(C) = 2 + 2 + 2 = 6;
f(D) = 2 + 1 + 5 = 8.

h2: f(S) = 0 + 6 = 6; f(A) = 5 + 5 = 10; f(B) = 2 + 2 = 4; f(C) = 2 + 2 + 5 = 9;
f(D) = 2 + 1 + 3 = 6.

R: Usando h0, os nós expandidos serão: S, B, D, G, C e G (ordem de visitação). E o caminho encontrado será: S, B, C, G.

Usando h1, os nós expandidos serão: S, B, C e G (ordem de visitação). E o caminho encontrado será: S, B, C, G.

Usando h2, os nós expandidos serão: S, B, D e G (ordem de visitação). E o caminho encontrado será: S, B, D, G.

---

1. Considere o espaço de busca a seguir. Cada nó é rotulado por uma letra. Cada nó objetivo é representado por um círculo duplo. Existe uma heurística estimada para cada dado nó (indicada por um valor ao lado do nó). Arcos representam os operadores e seus custos associados. Para cada um dos algoritmos a seguir, liste os nós visitados na ordem em que eles são selecionados, começando pelo nó A. No caso de escolhas equivalentes entre diferentes nós, prefira o nodo mais próximo da raiz, seguido pelo nó mais à esquerda na árvore.

[pic 3]

1. Algoritmo de Busca em Largura

R: A, B, C, D, E, F, G, H, I.

b.        Algoritmo de Busca em Profundidade

R: A, B, D, E, H, I.

c.        Algoritmo A*

        R: A, B, C, E, G, K.

...