Busca Cega Exercicios

SISTEMAS INTELIGENTES 1 PROF. TACLA/UTFPR/CPGEI-PPGCA

Fev/2014

BUSCA CEGA EXERCCIOS

1. Por que a estratgia de busca em largura s garante encontrar a soluo tima

quando o custo por ao uniforme?

2. Compare busca em largura (extenso) com custo uniforme para o seguinte espao de

estados em termos de: ns expandidos, ns na memria, otimalidade e completude.

Utilizar busca em grafo.

3. Explique e exemplifique a diferena de complexidade espacial da busca em largura

O(bd) e da busca em profundidade O(b.m). Exemplifique tomando por base o espao

de estados abaixo sendo G o estado objetivo e o custo das aes uniforme e igual a 1.

Utilizar busca em grafo.

4. No espao de estados acima, quantos ns devem ser gerados para se encontrar G na

estratgia de busca em profundidade. Compare o resultado obtido com a

complexidade espacial (quantos ns em memria).

5. Explique porque na busca em aprofundamento iterativo ainda se tem uma

complexidade espacial e temporal similar a da busca em profundidade sendo que a

busca reiniciada a cada incremento de l (nvel) a ser explorado.