Prof. Frederico Brito Fernandesasper@fredbf.com

1.1. DefiniçãoDefinição2.2. Estudos de CasoEstudos de Caso3.3. Busca em LarguraBusca em Largura4.4. Busca por Custo UniformeBusca por Custo Uniforme5.5. Busca em ProfundidadeBusca em Profundidade6.6. Busca com Profundidade Busca com Profundidade

LimitadaLimitada7.7. Busca com Profundidade Busca com Profundidade

InterativaInterativa8.8. Busca BidirecionalBusca Bidirecional9.9. ComparaçãoComparação

Busca sem Busca sem Informação ou Busca Informação ou Busca

CegaCega

Busca sem Busca sem Informação ou Busca Informação ou Busca

CegaCega

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 2/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

• Um problema de busca é:– Aquele que é resolvido através da busca do melhor estado (ou

caminho) em todo o espaço de estados. – Ex: chegar à Areia saindo de JP

JPJP120120CGCG

AreiaAreia

EsperançaEsperança

Baía da Baía da TraiçãoTraição

GuarabiraGuarabira

MamanguapeMamanguape

5050

2020

9090

5050

5050

60604040

FIM

INÍCIO

• Discutiremos sobre algoritmos de busca em árvore JPJP

CGCGMamanguapeMamanguape GuarabiraGuarabira

AreiaAreiaGuarabiraGuarabira EsperançaEsperança4040

EsperançaEsperança

Ex: Busca Ex: Busca em Larguraem Largura

• Um problema de busca sem informação é:– Aquele que não possui informação do melhor caminho para chegar na solução.

Ex: saindo de João Pessoa, não temos idéia de que direção está o objetivo (apesar de CG estar a 120km, é a melhor direção)

(1) Busca sem informação: definição

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 3/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

JPJP120120CGCG

AreiaAreia

EsperançaEsperança

Baía da Baía da TraiçãoTraição

GuarabiraGuarabira

MamanguapeMamanguape

5050

2020

9090

5050

5050

60604040

FIM

INÍCIO

4040

(1) Busca sem Informação : definição

• Um problema de busca com informação é:– Aquele que possui informação do melhor caminho para chegar na solução. Ex:

indo pra CG, gasto 120km de percurso + distância em linha reta até Areia (35km) = 155km

Origem Destino Dist. em Linha Reta (km)

JP Areia 134

BT Areia 155

Mamanguape Areia 130

Guarabira Areia 89

Esperança Areia 53

CG Areia 35

Areia Areia 0

• Um problema de busca é:– Aquele que é resolvido através da busca do melhor estado (ou caminho) em todo o

espaço de estados.

– Ex: chegar à Areia saindo de JP

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 4/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(1) Busca: critérios de análise

• Como determinar que um algoritmo é melhor do que outro?– Ex: para esse exemplo, é melhor usar Busca em Largura ou em

Profundidade?

JPJP120120CGCG

AreiaAreia

EsperançaEsperança

Baía da Baía da TraiçãoTraição

GuarabiraGuarabira

MamanguapeMamanguape

5050

2020

9090

5050

5050

60604040

FIM

INÍCIO

• Discutiremos sobre algoritmos de busca em árvore JPJP

CGCGMamanguapeMamanguape GuarabiraGuarabira

AreiaAreiaGuarabiraGuarabira EsperançaEsperança4040

EsperançaEsperança

Ex: Busca Ex: Busca em Larguraem Largura

• O algoritmo Busca em Largura...

a) É completo? (a) É completo? (ele sempre acha a solução, se existir?ele sempre acha a solução, se existir?))b) É ótimo? (b) É ótimo? (ele acha a melhor solução?ele acha a melhor solução?))c) Leva quanto tempo para achar a solução? (c) Leva quanto tempo para achar a solução? (tempotempo))d) Produz quantos nós? (d) Produz quantos nós? (memóriamemória))

Critérios de AnáliseCritérios de AnáliseCritérios de AnáliseCritérios de Análise

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 5/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(1) Busca: critérios de análise

Geração da Árvore: JPJP

MamanguapeMamanguape

MamanguapeMamanguape

GuarabiraGuarabira

AreiaAreia

JPJP120120CGCG

AreiaAreia

EsperançaEsperança

Baía da Baía da TraiçãoTraição

GuarabiraGuarabira

MamanguapeMamanguape

5050

2020

9090

5050

5050

60604040

FIM

INÍCIO

2020 5050

3030

XX EsperançaEsperança

CGCG

4040

5050

3030

• Dado o algoritmo:MissaoBregareia(){

cidade = JPfaça

cidadeAnterior = cidadecidade=proximaCidade(menorDistância,naoVisitada)cidade.visitada=true

se (cidade=jaVisitada ou cidade=FIM)cidade=cidadeAnterior

enquanto (cidade Areia)}

O algoritmo MissaoBregareia...O algoritmo MissaoBregareia...a) É completo? (a) É completo? (ele acha a solução, se existir?ele acha a solução, se existir?))b) É ótimo? (b) É ótimo? (ele acha a melhor solução?ele acha a melhor solução?))c) Leva quanto tempo?c) Leva quanto tempo?d) Produz quantos nós?d) Produz quantos nós?

5050

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 6/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

• Completude: A estratégia sempre encontra uma solução quando existe alguma?

• Custo do tempo: Quanto tempo gasta para encontrar uma solução? Normalmente medida em termos do número de nós gerados.

• Custo de memória: Quanta memória é necessária para realizar a busca? Normalmente medida pelo tamanho máximo que a lista de nós abertos assume durante a busca.

• Qualidade/otimalidade (optimality): A estratégia encontra a melhor solução quando existem soluções diferentes?

• menor custo de caminho

• As complexidades de tempo e espaço são medidas em termos de:– b : fator de ramificação máximo da árvore de busca.– d : profundidade do nó objetivo menos profundo.– m : profundidade máxima de qualquer caminho no espaço de estados.

(1) Busca: critérios de análise

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 7/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(1) Busca sem Informação: algoritmos

• Terminologia:

– Borda: é a coleção de nós que foram gerados mas não expandidos (nós abertos). Também conhecido como franja

– Nó Folha: qualquer elemento da borda (sem sucessores na árvore)

– Estratégia de Busca: função que seleciona o próximo nó a ser expandido da borda

• Algoritmos de Busca Desinformada:– Busca em Largura (ou extensão)

– Busca por Custo Uniforme

– Busca em Profundidade

– Busca em Profundidade Limitada

– Busca em Profundidade Interativa

– Busca Bidirecional

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 8/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(2) Estudo de Caso 1: Missão Bregareia

• Problema do menor caminho– Objetivo:

• Ir pro Bregareia, saindo de João Pessoa

– Ações:• Próxima cidade

– Usando Busca...• Em Largura

• Por Custo Uniforme

• Em Profundidade

• Em Profundidade Limitada

• Em Profundidade Interativa

• Bidirecional

JoãoJoãoPessoaPessoa120120CGCG

AreiaAreia

EsperançaEsperança

Baía da Baía da TraiçãoTraição

GuarabiraGuarabira

MamanguapeMamanguape

5050

2020

9090

5050

5050

60604040

FIM

INÍCIO

3030

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 9/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(2) Estudo de Caso 2: problema dos sapos

• Problema dos sapos:– Objetivo:

• Faça com que os machos fiquem na direita e as fêmeas na esquerda

– Ações:• Pular para frente, e duas

pedras no máximo

– Usando Busca...• Em Largura

• Por Custo Uniforme

• Em Profundidade

• Em Profundidade Limitada

• Em Profundidade Interativa

• BidirecionalM1M1 M2M2 M3M3 F3F3 F2F2 F1F1

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 10/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(2) Estudo de Caso 3: menor caminho

Início

objetivo

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 11/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 12/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)1

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 13/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)1

2

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 14/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)1

2 3

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 15/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)1

2 3 4

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 16/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)1

2 3 4

5

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 17/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)1

2 3 4

5 6

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 18/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura

• Expande os nós mais rasos ainda não expandidos

• Todos os nós de profundidade d são expandidos antes dos nós de profundidade d+1

• Borda organizada como uma fila (FIFO)1

2 3 4

5 6 7

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 19/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura: análise

• Completude: Sim. Encontra o mais raso, se o fator de ramificação b é finito

• Otimalidade: Sim, se o custo do caminho for uma função não decrescente da profundidade do nó (ou seja, quando todos os caminhos tiverem o mesmo custo)

• Custo de Tempo: 1 + b + b2 + b3 + ... + bd + (bd+1-b) = O(bd+1)

• Custo de Memória: O(bd+1) – guarda todos os nós na memória

• Grande quantidade de espaço e tempo exigida. Pode facilmente gerar 1MB de nós que devem ser guardados.

b = número máximo de filhosb = número máximo de filhos (ou fator de ramificação)(ou fator de ramificação)

d = altura do nó ótimod = altura do nó ótimodd

1

2 3 4

5 6 7

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 20/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(3) Busca em Largura: análise

• Para um fator de ramificação b=10, e supondo que 1000 nós podem ser gerados por segundo, temos:

profundidade nós tempo memória2 1100 0,11 seg 1 MB

4 111.100 11 seg 106 MB

6 107 19 min 10 GB

8 109 31 horas 1 TeraB

10 1011 129 dias 101 TeraB

12 1013 35 anos 10 PentaB

14 1015 3.523 anos 1 exaB

• Requisitos de memória são problemas maiores do que o tempo de execução

• Problemas de busca de complexidade exponencial não podem ser resolvidos por métodos sem informação (exceto os menores)

1+b1+b11+b+b22+(b+(b33-b) = 1+10+100+(1000-10) = 1101-b) = 1+10+100+(1000-10) = 1101

Cada nó Cada nó tem 1KBtem 1KB

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 21/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(4) Busca por Custo Uniforme

1 10

S

A

C

B G

15 5

5 5

S

• Expande o nó de menor custo ainda não expandidos (pelo custo do caminho – g(n))

• Encontra a solução mais barata porque os nós mais baratos são expandidos primeiro

• Borda é organizada em ordem crescente pelo custo do caminho de cada nó

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 22/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(4) Busca por Custo Uniforme

1 10

S

A

C

B G

15 5

5 5

S

B CA

15

15

• Expande o nó de menor custo ainda não expandidos (pelo custo do caminho – g(n))

• Encontra a solução mais barata porque os nós mais baratos são expandidos primeiro

• Borda é organizada em ordem crescente pelo custo do caminho de cada nó

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 23/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(4) Busca por Custo Uniforme

1 10

S

A

C

B G

15 5

5 5

S

B C

G

A

15

15

11

• Expande o nó de menor custo ainda não expandidos (pelo custo do caminho – g(n))

• Encontra a solução mais barata porque os nós mais baratos são expandidos primeiro

• Borda é organizada em ordem crescente pelo custo do caminho de cada nó

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 24/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(4) Busca por Custo Uniforme

1 10

S

A

C

B G

15 5

5 5

S

B C

GG

A

15

15

1011

• Expande o nó de menor custo ainda não expandidos (pelo custo do caminho – g(n))

• Encontra a solução mais barata porque os nós mais baratos são expandidos primeiro

• Borda é organizada em ordem crescente pelo custo do caminho de cada nó

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 25/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(4) Busca por Custo Uniforme

1 10

S

A

C

B G

15 5

5 5

S

B C

GG

A

15

15

1011

• Expande o nó de menor custo ainda não expandidos (pelo custo do caminho – g(n))

• Encontra a solução mais barata porque os nós mais baratos são expandidos primeiro

• Borda é organizada em ordem crescente pelo custo do caminho de cada nó

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 26/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(4) Busca por Custo Uniforme

• Completude: Sim, se nenhum operador tiver custo negativo

• Custo Tempo: quantidade de nós com g <= custo da solução ótima (pode ser muito maior que O(bd))

• Custo Memória: quantidade de nós com g <= custo da solução ótima

• Otimalidade: Sim.

• Espaço e tempo continuam sendo um problema

S

B C

GG

A

15

15

1011 b = número máximo de filhosb = número máximo de filhos (ou fator de ramificação)(ou fator de ramificação)

g = custo do nó ótimog = custo do nó ótimo

1 10

S

A

C

B G

15 5

5 5

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 27/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 28/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 29/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 30/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2

3

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 31/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2

3

4

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 32/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2

3

54

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 33/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2

3 6

54

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 34/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2

3 6

5 74

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 35/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2

3 6

5 874

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 36/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2 9

3 6

5 874

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 37/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Expande o nó mais profundo ainda não expandido

• Quando encontra um nó que não pode ser expandido, volta para expandir os outros dos níveis mais rasos

• Borda organizada como uma pilha (LIFO)

1

2 9

3 6 10

5 874

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 38/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(5) Busca em profundidade

• Completude: Sim, somente se o espaço de estados não tiver laços

• Custo Memória: Armazena somente um caminho simples da raiz até a folha.

– Para um fator de ramificação b e uma profundidade máxima de m armazena bm nós (busca em largura = bd)

• Custo Tempo: O(bm) no pior caso -> examinar todos os ramos

– Terrível se m é muito maior que d (m - profundidade máxima de qq nó)

• Otimalidade: Não

• Necessita de um espaço de busca finito e não cíclico

1

2 9

3 6 10

5 874

b = número máximo de filhosb = número máximo de filhos (ou fator de ramificação)(ou fator de ramificação)

m = altura máxima da árvorem = altura máxima da árvore

mm

Esteja certo de que entende que m Esteja certo de que entende que m d d

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 39/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(6) Busca com Profundidade Limitada

• Evita os problemas da busca em profundidade impondo um corte na profundidade de caminho

• Problema => escolher a profundidade correta

• Completude: Sim. Se a solução existente estiver em uma profundidade d<, ela é encontrada

• Otimalidade: Não. A solução ótima pode estar em outra subárvore

• Tempo: O(b), onde é o limite de profundidade

• Memória: O(b)

• Alguns problemas sugerem um valor de . (20 cidades => =19)

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 40/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

• Tenta todos os possíveis limites de profundidade, começando pelo 0.

• Combina os benefícios da busca em largura e em profundidade

• Ordem de expansão parecida com a busca em largura

– Alguns nós podem ser expandidos múltiplas vezes

(7) Busca com Profundidade Interativa

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 41/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(7) Busca com Profundidade Interativa

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 42/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(7) Busca com Profundidade Interativa

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 43/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(7) Busca com Profundidade Interativa

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 44/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(7) Busca com Profundidade Interativa

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 45/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

• Completude: Sim• Otimalidade: Sim (se o custo do caminho for uma função não decrescente da profundidade

do nó,ou seja, quando todos os caminhos tiverem o mesmo custo)• Tempo: O(bd) – alguns nós podem ser gerados várias vezes. Mas isso acontecerá nos níveis

superiores que normalmente têm poucos nós• Memória: O(bd)• Preferida quando o espaço de busca é muito grande e a profundidade da solução não é

conhecida• Tempo comparação com a busca em largura com b=10 e d=5

– Prof. Interativa = 123.450 nós gerados

– Largura = 1.111.100 nós gerados

• É o método de busca sem informação preferido quando existe um espaço de busca grande e a profundidade da solução não é conhecida

b = número máximo de filhosb = número máximo de filhos (ou fator de ramificação)(ou fator de ramificação)

d = altura do nó ótimod = altura do nó ótimo

(7) Busca com Profundidade Interativa

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 46/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

• Busca em duas direções:

– Para frente, a partir do nó inicial, e

– Para trás, a partir do nó final (objetivo)

• A busca pára quando os dois processos geram o mesmo nó

• Problema: verificar antes de cada expansão se o nó não pertence à borda da outra busca

• É possível utilizar estratégias diferentes em cada direção da busca

(8) Busca Bidirecional

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 47/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

(8) Busca Bidirecional

• A comparação de cada nó antes da expansão pode ser feita em tempo constante utilizando uma tabela hash

• Completude: Sim

• Otimalidade: Sim

• Tempo: O(bd/2)

• Memória: O(bd/2)

• Para b=10 e d=6 temos 22.200 nós gerados, contra os 11.111.100 da busca em largura

Professor: Frederico Brito FernandesProfessor: Frederico Brito Fernandes 48/48Disciplina: Inteligência ArtificialDisciplina: Inteligência Artificial

Sim1,2Sim1SimNãosim1,2sim1Completa?

Sim3,4sim3NãoNãoSimSim3Otima?

O(bd/2)O(bd)O(b)O(bm)>>bd>>bd Espaço

O(bd/2)O(bd)O(b)O(bm)O(bd + 1)O(bd + 1)Tempo

Bidirecional (se aplicável)

Profun-didade

Interativa

Profun-didade

limitada

Profun-didade

Custo Uniforme

Largura

1 – completa se b é finito2 – completa se o custo do passo é >= c, para c positivo3 – ótima se o custo dos passos são todos idênticos4 – se ambos os sentidos utilizam busca em largura

(9) Comparação das Estratégias de Busca