O Exercício Teórico Busca Sem Informação

AULA 4: Exercício teórico Busca sem informação – parte 2

____________________________________________________________

1) (0,8) Considere um espaço de estados onde o estado inicial é o número 1 e cada estado k  tem dois sucessores: números 2k e 2k+1.

a. Represente a porção do espaço de estados para os estados de 1 a 15.

[pic 1]

b. Suponha que o estado objetivo seja 11. Liste a ordem em que os nós serão visitados pela  busca em largura, busca em profundidade limitada com o limite 3 e busca de aprofundamento  iterativo.

busca em largura: Irá buscar os nós de um nível k, depois k+1 e assim por diante. De acordo com o diagrama acima, o algoritmo de busca em largura irá visitar em sequência os nós:

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11

busca em profundidade limitada: Irá percorrer os nós, do começo até um nó de profundidade máxima e ao alcançá-la irá regressar aos antecessores e verificar algum nó que ainda não foi verificado (por haver diversos nós com um mesmo nível de profundidade, um algoritmo de busca em profundidade limitada poderia dar prioridade a nós de mesmo nível de diferentes formas para realizar a busca, nesse caso, iremos percorrer sempre o nó mais à esquerda possível):

1 → 2 → 4 → 8 → 9 → 5 → 10 → 11

busca de aprofundamento iterativo: Irá percorrer os nós, do começo até um nó de profundidade 1 e ao alcançá-la irá regressar aos antecessores e verificar algum nó que ainda não foi verificado, depois irá repetir o algoritmo para uma profundidade 3 e assim por diante:

1

1→ 2 → 3 →

1→ 2 → 4 → 5 →3→ 6 → 7

1 → 2 → 4 → 8 → 9 → 5 → 10 → 11

c. Como a busca bidirecional funcionaria nesse problema? Qual é o fator de ramificação em  cada direção?

A busca bidirecional irá percorrer os nós partindo de duas origens diferentes (estado inicial e objetivo). Para isso, podemos usar a BFS em ambas as direções, expandir os adjacentes de cada nó atual verificado e ver se os caminhos se encontram.

Expandir o nó 1 na primeira busca e expandir o nó 11 na outra, verificando seus adjacentes:

1→ 2 → 3  

11→ 5

nenhum nó em comum visitado, continuamos:

Expandir o nó 2 na primeira busca e expandir o nó 5 na outra, verificando seus adjacentes:

1→ 2 → 3→ 4→ 5

Ao expandir o nó 2 já encontramos um nó visitado em comum, o nó 5. Logo, atingimos o objetivo.

Ordem de visitação sequencial dos nós:

1→ 11→ 2 → 3 → 5 → 4→ 5

A busca a partir do estado inicial foi finalizada na profundidade 3 enquanto a busca na ordem inversa foi finalizada na profundidade, de cima para baixo, 2. O fator de ramificação da primeira busca foi 2 e o da segunda, 1.

d. Chame a ação que vai de k para 2k de Esquerda e a ação de k que vai para 2k + 1 de Direita. É possível encontrar um algoritmo que devolva a solução desse problema absolutamente  sem nenhuma busca?

Podemos começar do destino  e elaborar um algoritmo com base nessas funções para chegar até a origem e no meio do caminho ir salvando as direções as quais deveríamos seguir, se partíssemos da origem.

Função(n):

Se n==1:

        return caminho.Reverse(); //retornará o caminho na ordem direta

                //finalizamos o algoritmo, pois chegamos na origem

...