Inteligência Artificial

Conteúdos

• Conceitos
• Busca
  • Resumo
• Representação do Conhecimento
  • Raciocício
  • Ontologia
  • Web Semântica
• Agentes
  • Sistemas Multiagentes
  • Sistemas Multiagentes de Negociação
  • Sistemas Multiagentes de Cooperação

---

Busca

• Os métodos de busca são úteis para simplificar soluções.
• São representados por grafos [ nodos (estados) + arestas (ações)]
• O resultado de uma busca retorna um conjunto de ações (como montar e como percorrer)
• Devido a otimização de recursos sempre é feito a montagem e percorrimento simultaneamente.

Características

• Computável
  • solução encontrada em um tempo finito
• Otimizada
  • Sempre encontra a melhor solução
• Recursos limitados
  • Deve utilizar o mínimo de recursos necessários

Métodos de Busca

• Amplitude (Breadth-first)
  • queue
• Profundidade (Depth-first)
  • stack

Algoritmo de Resolução

Comece com

• 2 listas
• solução a ser encontrada
• vértices (nodos)

solucao = 'n'

estado_inicial = 'a'
estado_atual = None

lista_nodos_visitados = []
fila = [] # lista_nodos_abertos

1. Pegue o nodo estado_inicial

solucao = 'n'

estado_inicial = 'a'
estado_atual = 'a'

fila = ['a']

2. Verifique se é solução, se não for então remova da fila e adicione na lista_nodos_visitados

estado_atual = 'a'

lista_nodos_visitados = []
fila = ['a']


if estado_atual is solucao:
    return True
else:
    fila.pop(estado_atual)
    lista_nodos_visitados.append(estado_atual)

    # estado_atual = 'a'
    # lista_nodos_visitados = ['a']
    # fila = []

4. Verifique se o estado_atual tem filhos, se tiver adicione na fila

estado_atual = 'a'

lista_nodos_visitados = ['a']
fila = []


if len(node.estado_atual) > 0:
    fila.append('b')
    fila.append('c')

    # estado_atual = 'a'
    # lista_nodos_visitados = ['a']
    # fila = ['b', 'c']

5. Pegue um novo nodo

estado_atual = 'b'

NOTA: até aqui é tudo igual para os métodos de busca em largura e profundidade.

6. Verifique se é solução, se não for então remova da fila e adicione na lista_nodos_visitados

estado_atual = 'b'

lista_nodos_visitados = ['a']
fila = ['b', 'c']

if estado_atual is solucao:
    return True
else:
    fila.pop(estado_atual)
    lista_nodos_visitados.append(estado_atual)

7. Verifique se o estado_atual tem filhos, se tiver adicione na fila

estado_atual = 'b'

lista_nodos_visitados = ['a', 'b']
fila = []


if len(node.estado_atual) > 0:
    # largura FIFO
    fila.insert(index=-1, 'd')
    fila.insert(index=-1, 'e')
    # estado_atual = 'b'
    # lista_nodos_visitados = ['a', 'b']
    # fila = ['c', "d", "e"] 


    # profundidade LIFO
    pilha.insert(index=0, 'd')
    pilha.insert(index=0, 'e')
    # estado_atual = 'b'
    # lista_nodos_visitados = ['a', 'b']
    # pilha = ["d", "e", 'c'] 

Largura

Profundidade

---

Referências

• http://how2examples.com/artificial-intelligence/tree-search

---