Para que serve IA
Resolução de problemas envolvendo:
- Auxílio a decisão
- Robótica
- Sistemas de auxílio à deficiente
- Sistemas de apoio à especialistas
- Logísticas
Modelagem de processos em Psicologia e Neurobiologia
Motivador de questões filosóficas
IA pode:
- Ajudar e aprender a resolver problemas analíticos
- Ajudar especialistas a projetar sistemas
Jogar xadrez, futebol, gamão, etc.
Qual o nome do teste que verifica se uma maquina é ou não inteligente? Teste de Turing
Defina Agente: Entidade que percebe e atua no mundo a sua volta. Exemplos: ser humano, robô, agente de software.
Quais são os tipos de Agente:
Reativo com estado interno:
Agentes que selecionam as ações levando em consideração a percepção instantânea e numa pequena representação interna dos estados em que o mesmo já esteve. Desvantagem: pouca autonomia e não tem objetivo, não encadeia regras
Baseados em objetivos:
Informação de objetivo que descreve situações desejáveis. Envolve busca e planejamento.
Vantagens e desvantagens: Mais complicado e ineficiente, porém mais flexível, autônomo e
Não trata objetivos conflitantes
Baseados em utilidades:
A função de utilidade mapeia estados em números reais que indicam o grau associado de desejabilidade de estados. Desvantagem: não tem adaptabilidade
Quais os métodos para comparação de estratégias de busca:
Comparação em problemas bechmark: Executo algoritmo a ser testado em um problema-padrão, e comparo seu desempenho com um algoritmo de referência. Problema: muito específico. Desempenho pode depender do compilador utilizado, ajuste fino de parâmetros, arquitetura da máquina usada, etc.
Analise de algoritmos: Analiso algoritmo em termos de parâmetros característicos, abstraídos de aspectos implementacionais. Evita especificidade.
Estratégias de Busca:
Completo: Para qualquer problema ele encontrará a solução?
Ótimo: Se tem a solução, ele encontra o melhor caminho
Complexidade de Tempo: Projeção de crescimento da quantos nós forem expandidos.
Complexidade de Espaço: Algum nó é retirado da memória durante a busca? Se não complexidade é igual a complexidade de tempo.
Busca em Largura (BFS)
Utiliza a estrutura de fila. Coloca em uma fila todos os nos visitados e também seus vizinhos, realizando assim uma busca nível a nível. É uma estratégia simples em que o nó raiz é o primeiro a ser expandido, logo em seguida todos os sucessores do nó raiz são expandidos etc. Em geral, todos os nós de uma mesma profundidade na árvore de busca são expandidos antes de qualquer nó da profundidade seguinte.
Características do Algoritmo:
Completo: Sim
Ótimo: Sse o custo entre os nos forem uniformes
Complexidade de Tempo: O(b^d);
Complexidade de Espaço: O(b^d).
Busca em Profundidade (DFS)
Nessa estratégia de busca um dos nós do nível mais profundo da árvore de busca sempre é expandido. Somente quando a busca atinge um nó cujos filhos possuem estados que já foram expandidos outrora é que a busca expandirá algum dos nós pertencentes aos níveis acima deste, processo este conhecido como backtrack.
Completo: não (Falha com caminhos infinitos ou loops)
Completa: sim, se L >= d! (Determinar uma profundidade máxima L, no qual a DFS deve parar.)
Ótimo: não
Busca em Aprofundamento Iterativo (IDS)
Faz repetidas buscas em profundidade, aumentando o limite a cada iteração.
Combina os benefícios da BFS e DFS
Completo: Sim
Ótimo: Sim
Não gasta muita memória. Repetição da expansão de estados.
Não é tão ruim, pois a maior parte dos estados está nos níveis mais baixos
Na verdade, gera menos estados que o BFS, pois não gera estados no nível d+1
Busca de Custo Uniforme (Busca Ordenada)
Expande o nó de menor custo da trajetória a cada visita.
Usa-se fila de prioridades (como visto em S.O. no 3º Período) : menor valor, maior prioridade.
Exemplo: vc ta no nivel 0, ae expande todos os filhos dele, no nivel 1 vc vai visitar só o nó q tem menor custo de trajetória (maior prioridade) e assim por diante nivel por nivel... se vc chegar ao nivel mais profundo e não atingir o resultado, ele faz o backtracking pro nivel anterior e expande o nó com 2º menor custo e assim por diante ate achar o nó desejado porém existe o risco de cair em loop.
Completo? Não
Ótimo? Sim, pois encontra a solução que possuir o menor valor (custo)
Complexidade de Tempo? Número de nós com custo <= d Complexidade de Espaço? Número de nós com custo <= d
Greedy Search (Algoritmo Guloso)
Trabalha partindo dos valores informados pela heurística (ou pelo conjunto de heurísticas), sem enxergar o problema como um todo, por isso, ele pode tomar decisões incorretas (como cair em um loop infinito). Também utiliza fila de prioridades: menor valor, maior prioridade.
A heurística guia a busca, mas não representa o custo real.
Exemplo: Como já foi dito, o guloso trabalha com uma heuristia, tipo distancia entre as cidades
portanto a cada nivel ele pega o nó de menor custo e expande e visita o filho de menor custo
e expande e visita o filho de menor custo e por aí vai da mesma forma que a busca ordenada, a unica diferença é que caso ele chegue no nó mais profundo e não encontre a solução ele finaliza o algoritmo.
Completo? Não
Ótimo? Não, mas pode ser dependendo da heurística utilizada
Complexidade de Tempo? O(b^m), mas pode variar de acordo com a heurística utilizada
Complexidade de Espaço? O(b^m)
Observação:
Profundidade -> Pilha
Largura -> Fila
Postagens
Nenhum comentário:
Postar um comentário