Upload
nauber-gois
View
173
Download
0
Embed Size (px)
Citation preview
1
Inteligência ArtificialProfessor: Francisco Nauber Bernardo Gois
Introdução a Inteligência Artificial
Problema determinístico vs não deterministico
Problemas intratáveis ou difíceis são comunsna natureza e nas áreas do conhecimento.• Problemas “fáceis”: resolvidos por algoritmospolinomiais.• Problemas “difíceis”: somente possuemalgoritmos exponenciais para resolvê-los.• A complexidade de tempo da maioria dosproblemas é polinomial ou exponencial.
P é um conjunto de problemas que podem ser resolvidos por uma máquina Turing determinística em tempo polinomial.
NP é um conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing não determinística em tempo polinomial. P é um subconjunto de NP (qualquer a que pode ser resolvido por máquina determinística em tempo polinomial também pode ser resolvido por máquina não-determinística em tempo polinomial).Informalmente, NP é um conjunto de problemas de decisão que podem ser resolvidos por um tempo polinomial através de um algoritmo "Lucky Algorithm", um algoritmo mágico que sempre faz um palpite certo entre o conjunto dado de escolhas.
Problemas NP-completos são os problemas mais difíceis no conjunto NP. Um problema de decisão L é NP-completo se:1) L está em NP (Qualquer solução dada para problemas NP-completos pode ser verificada rapidamente, mas não há solução eficiente conhecida).2) Todo problema em NP é redutível a L em tempo polinomial (Redução é definida abaixo).
Exemplo: Localização de rotas na Romênia, usando a Busca A*
Objetivo: Bucharest (Bucareste)
Um mapa rodoviário simplificado de parte da Romênia.
176
100
Ótimo local e Ótimo Global
Espaço de busca
A cidade é cortada pelo rio Pregel, criando ilhas na cidade.Existiam sete pontes conectando as ilhas e as margens opostas do rio.O problema consiste em determinar se é possível ou não fazer um passeio pela cidade come cando e terminando no mesmo lugar, cruzando cada ponte exatamente uma u nica vez.
http://blog.mayec.eu/2011/01/python-brute-force-solution-to-bridges.html
Grafos (cont.)História
Euler (1736) - pontes de Königsberg
Baseado na disposição das pontes, mostrou que era impossível percorrer por todas passando somente uma vez
http://www.sanfoundry.com/java-program-give-implementation-traditional-chinese-postman-problem/
http://www.harold.thimbleby.net/cpp/index.html
c
É possível conectar cada serviço a cada uma das três casas sem haver cruzamento de tubulações?
$ python>>> from sklearn import datasets>>> iris = datasets.load_iris()>>> digits = datasets.load_digits()
Chamando dataset de exemplo
Executando exemplos com optaplanner
O que é uma pontuação?
Cada solução inicializada tem uma pontuação. Essa pontuação é uma maneira objetiva de comparar duas soluções: a solução com maior pontuação é melhor. O Solver pretende encontrar a Solução com o maior Índice de todas as soluções possíveis. A melhor solução é a Solução com a pontuação mais alta que o Solver encontrou durante a resolução, que pode ser a solução ideal.
O Planner não pode automaticamente saber qual solução é a melhor para o seu negócio, então você precisa dizer-lhe como calcular a pontuação de uma determinada solução de acordo com as necessidades de sua empresa. Existem várias técnicas de pontuação que você pode usar e combinar:
Maximizar ou minimizar uma restrição: score constraint signum (positivo ou negativo)Coloque um custo / lucro sobre as restrições: pontuação restrição pesoPriorizar restrições: nível de pontuaçãoPontuação de Pareto
A maioria dos casos de uso tem apenas 2 níveis de pontuação: Hard e Soft. Ao comparar 2 pontuações, elas são comparadas lexicograficamente: o primeiro nível de pontuação é comparado primeiro. Se esses diferirem, os outros níveis de pontuação são ignorados.
Hard e Soft score level
2017-02-05 14:06:59,744 [main] INFO Solving ended: time spent (10000), best score (-3hard/-5460soft), score calculation speed (28039/sec),
Custo :4800 CpuPower :24 Memory :96 Network Bandwith :16
Custo :660 CpuPower :6 Memory :4 Network Bandwith :24
Required Memory :1Required Cpu Power :1Required Network :1
Required Memory :6Required Cpu Power :3Required Network :1
Required Memory :1Required Cpu Power :1Required Network :3
Required Memory :2Required Cpu Power :1Required Network :11
Required Memory :1Required Cpu Power :1Required Network :1
Required Memory :1Required Cpu Power :1Required Network :5
Required Memory :3Required Cpu Power :2Required Network :5
Required Memory :3Required Cpu Power :1Required Network :1
Required Memory :4Required Cpu Power :1Required Network :1
Required Memory :17Required Cpu Power :1Required Network :1
Required Memory :13Required Cpu Power :1Required Network :7
Required Memory :1Required Cpu Power :2Required Network :3
Processos
Solved cloudBalance with 400 computers and 1200 processes: Process 0 -> Computer 0 Process 1 -> Computer 0 Process 2 -> Computer 1 Process 3 -> Computer 1 Process 4 -> Computer 1 Process 5 -> Computer 1 Process 6 -> Computer 0 Process 7 -> Computer 0 Process 8 -> Computer 0 Process 9 -> Computer 0 Process 10 -> Computer 0 Process 11 -> Computer 1
https://github.com/droolsjbpm/optaplanner.git
SolverFactory<CloudBalance> solverFactory = SolverFactory.createFromXmlResource( "org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml"); Solver solver<CloudBalance> = solverFactory.buildSolver();
Cria resolvedor de problemas do Optaplanner
Heurística refere à arte do descobrimento. Ela estabelece várias ferramentas ou procedimentos para tornar possível uma descoberta.
O termo foi utilizado pela primeira vez por Albert Einstein em uma publicação chamada “Heurística da geração e conversão da luz”. Ela é basicamente uma disciplina focada na busca de soluções para diversos problemas.
Busca Heurística
p Heurística - Informação específica do domínio que pode ser usada para guiar o processo de busca.
p Em muitos casos uma heurística envolve a aplicação de uma função que avalia um nó particular e prediz a qualidade dos seus nós sucessores.
p Uma função heurística de avaliação no jogo-da-velha poderia ser o número de linhas, colunas e diagonais ainda disponíveis, quanto maior este número maior a chance de vitória.
Busca Heurística – Exemplo ...Porção do espaço de estados para o jogo-da-velha
N0 de caminhos = 9!
Busca Heurística – Exemplo ...Os primeiros três níveis do espaço de estados do jogo-da-velha
reduzidos por simetria.
3 movimentos iniciais: •Para o canto •Para o centro de um lado •Para o centro da grade •
A heurística do “maior número de vitórias” aplicada aos primeiros filhos
do jogo-da-velha.
Busca Heurística – Exemplo ...
Espaço de estados reduzido heuristicamente para o jogo-da-velha.
Busca Heurística – Exemplo
61
Suge
stão
62