Resolução de Problemas - olaria.ucpel.tche.brolaria.ucpel.tche.br/venecian/lib/exe/fetch.php?media=ec_ia_02.pdf · Exemplos de técnicas Busca em amplitude (breadth-first search)

Resolução de ProblemasUniversidade Católica de Pelotas

Engenharia da Computação

Disciplina: Inteligência Artificial

Resolução de Problemas

• Introdução

• Componentes

• Solução

• Busca de soluções

2


• Resolver problemas é importante para grande maioria das aplicações da Inteligência Artificial▫ Solução => o caminho mais curto (ou mais barato) para

atingir um objetivo (estado desejado)

• Consiste em analisar o espaço de possibilidades de resolução do problema, encontrar sequências de ações que levem a um objetivo desejado.

• Envolve...▫ Formulação de objetivos▫ Formulação do problema. Que ações e estados devem ser considerados

(levando em conta um objetivo e regras)

3

Resolução de ProblemasObjetivo: Ir de Arad para Bucharest

4

Que ações tomar????


5

Que ações tomar????Vária sequências são possíveis!!!!


6

Que ações tomar????Vária sequências são possíveis!!!!

O processo de identificar tal sequência é chamado

de busca


7


• Um algoritmo de busca recebe um problema como entrada e retorna uma solução

▫ Solução => sequência de ações

• Inicialmente é assumido que a solução é executada sem alterações no ambiente (pelo menos elas não são percebidas/são ignoradas)

▫ Ponte caiu!!!!

8

Componentes de um problema

• Estado inicial. Uma configuração inicial de um problema.

▫ Estado. Uma configuração de um problema.

Exemplo: Em(Arad)

Espaço de estados. Conjunto de estados que podem ser atingidos.

9


• Estado Inicial: Estado inicial do agente.

▫ Ex: Em(Arad)

• Estado Final: Estado buscado pelo agente.

▫ Ex: Em(Bucharest)

• Ações Possíveis: Conjunto de ações que o agente pode executar.

▫ Ex: Ir(Cidade, PróximaCidade)

• Espaço de Estados: Conjunto de estados que podem ser atingidos a partir do estado inicial.

▫ Ex: Mapa da Romênia.

• Custo: Custo numérico de cada caminho.

▫ Ex: Distância em KM entre as cidades.

10


• Descrição das ações possíveis.

▫ Função sucessor.

Dados um estado x, a função SUCESSOR(x)retorna um conjunto de pares ordenados <ação,sucessor>, onde:

ação é uma das ações válidas no estado x

sucessor é um estado que pode ser atingido a partir de x mediante execução da ação

11

Retorno da função sucessor...Objetivo: Ir de Arad para Bucharest

Estado inicial = Em(Arad)

12

Objetivo: Ir de Arad para Bucharest


{<Ir(Sibiu),Em(Sibiu)>, <Ir(Timisoara),Em(Timisoara)>, <Ir(Zerind),Em(Zerind)>}

13

Retorno da função sucessor...


• Teste de objetivo. ▫ Determina se um estado é um estado objetivo... Estado objetivo: Em(Romênia)

• Custo de caminho▫ Uma medida de desempenho▫ Um valor numérico▫ É a soma do custos dos passos (ações)

(de um estado para outro...) Exemplo: distância entre as cidades...

14

Solução para um problema

• Solução = caminho desde um estado inicial até um estado objetivo

• Solução ótima = menor custo de caminho

15

Exemplo: Aspirador de Pó• Espaço de Estados: 8 estados

possíveis (figura ao lado);

• Estado Inicial: Qualquer estado;

• Estado Final: Estado 7 ou 8 (ambos quadrados limpos);

• Ações Possíveis: Mover para direita, mover para esquerda e limpar;

• Custo: Cada passo tem o custo 1, assim o custo do caminho é definido pelo número de passos;

Exemplo: Aspirador de Pó

Exercícios

• Torre de Hanói?

• Canibais e Missionários?

Exercícios

• Torre de Hanói:

▫ Espaço de Estados: Todas as possíveis configurações de argolas em todos os pinos (27 possíveis estados).

▫ Ações Possíveis: Mover a primeira argola de qualquer pino para o pino da direita ou da esquerda.

▫ Custo: Cada movimento tem 1 de custo.

Exercícios

Exercícios

• Canibais e Missionários:

▫ Espaço de Estados: Todas as possíveis configurações validas de canibais e missionários em cada lado do rio (16 possíveis estados).

▫ Ações Possíveis: Mover 1 ou 2 personagens (canibais ou missionários) para o outro lado do rio. O número de canibais em um determinado lado do rio não pode ser maior do que o número de missionários.

▫ Custo: Cada movimento tem 1 de custo.

Exercícios

Busca de soluções

• A busca de soluções implica em uma busca em todo o espaço de estados

• Técnicas de busca que usam uma árvore de busca explícita

▫ Quando vários caminhos são possíveis é utilizado um grafo.... (complexidade é maior...)

Árvore de Busca Explícita

• Parte do estado inicial

• Usa a função sucessor


• Raiz = representa o estado inicial

• Cada ação sobre o nó gera um sucessor

• Este processo é repetido até que o nó que representa o estado objetivo seja gerado

• É adotada uma estratégia de busca na árvore



Estado objetivo= Em(Bucharest)



{<Ir(Sibiu),Em(Sibiu)>, <Ir(Timisoara),Em(Timisoara)>, <Ir(Zerind),Em(Zerind)>}




• Alguma delas é um estado objetivo?

• Qual dessas 3 possibilidades deve ser tentada (inicialmente)?

• Depende da estratégia de busca


• O processo segue até atingir estado objetivo• A escolha de qual estado expandir corresponde a uma estratégia

de busca• Obs.

• Espaço de estados não é a mesma coisa que a árvore de busca!!!!• Espaço de estados deste problema

(20 estados pq são 20 cidades)• Um nó não é um estado (vários nós representam mesmo estado)

• Exemplo: Arad

Estratégias de busca

• Sem informação (às cegas)▫ Não possuem nenhuma informação, além da

definição do problema Tudo que podem fazer é gerar sucessores e distinguir

um estado objetivo de um não objetivo (Não sabem se um estado é mais “promissor”)

▫ Exemplos de técnicas Busca em amplitude (breadth-first search)

(extensão) Busca em profundidade (depth-first search)

• Com informação ou heurística (best-first search)

Busca em amplitude (breadth-firstsearch) (extensão/largura)

D é o objetivo

• Sequência de Expansão: Todos os nós de um nível são visitados, antes dos nós do nível abaixo

Fontes Figuras: http://lia.ufc.br/~wladimir/ia/




Busca em profundidade (depth-first search)

M é o objetivo

• Sequência de Expansão: Explorar nós que estão mais distantes do raiz (não explora todos os nós de um mesmo nível como na busca em largura)













Métodos de busca sem informação

• Não são usados apenas em árvores...

▫ Grafos também (complexidade maior pela repetição de estados)

• Busca em largura requer muita memória em relação a busca em profundidade...

▫ Ver detalhes em (RUSSEL; NORVIG, 2004)

▫ Inclusive uma discussão sobre questões de complexidade...

Representação do problema

• Deve permitir

▫ Representar os estados

▫ Representar os estados inicial e objetivo

▫ Descrição dos operadores


Estado Inicial Estado objetivo

Estado inicial: [7,2,4,5,0,6,8,3,1]Estado objetivo: [1,2,3,4,5,6,7,8,0]


• Grafos...

▫ Nó representa um estado

▫ Aresta está relacionada a uma operação[7,2,4,5,0,6,8,3,1]

[7,2,4,5,3,6,8,0,1] 3

Atividade

• Apresente os percursos no grafo anterior para alcançar o estado objetivo nas seguintes ações:

▫ 4 operadores:

Branco para cima

Branco para baixo

Branco para direita

Branco para esquerda

• Quantos movimentos foi necessário para o estado objetivo.

54

Documents

Resolução de Problemas - olaria.ucpel.tche.brolaria.ucpel.tche.br/venecian/lib/exe/fetch.php?media=ec_ia_02.pdf · Exemplos de técnicas Busca em amplitude (breadth-first search)