Busca heuristica

Disponível somente no TrabalhosFeitos
  • Páginas : 23 (5700 palavras )
  • Download(s) : 0
  • Publicado : 28 de novembro de 2011
Ler documento completo
Amostra do texto
Algoritmos de Busca Heurística (PARTE 1)

1

Universidade Federal do Paraná Departamento de Informática

Algoritmos de Busca Heurística

(Parte 1)
Alexandre I. Direne

E-mail: alexd@inf.ufpr.br Web: http://www.inf.ufpr.br/~alexd

Algoritmos de Busca Heurística (PARTE 1)

2

BIBLIOGRAFIA RECOMENDADA
1- Artificial Intelligence: A Modern Approach. Stuart Russell e Peter Norvig.Second Edition, Prentice Hall, 2003. 2- Programming in Prolog. William F. Clocksin and C.S. Mellish. Springer-Verlag, 1987. 3- Guilherme Bittencourt. Inteligência Artificial: Ferramentas e Teorias. Terceira Edição, Editora da UFSC, 2006 (ISBN: 85-328-0138-2). 4- Elaine Rich e Kevin Knight, Artificial Intelligence, Second Edition, McGraw Hill, 1993. 5- Patrick H. Winston, Artificial Intelligence,Second Edition, Addison-Wesley, 1993.

PÁGINAS RECOMENDADAS
http://www.cs.dartmouth.edu/~brd/Teaching/AI/Lectures/Summaries/search.html http://www.decom.ufop.br/prof/guarda/CIC250/index.htm http://aima.cs.berkeley.edu/ http://aima.cs.berkeley.edu/newchap05.pdf

SOFTWARE RECOMENDADOS
http://www.cs.bham.ac.uk/research/poplog/freepoplog.html http://www.swi-prolog.org

Algoritmos de BuscaHeurística (PARTE 1)

3

Algoritmos de Busca
Características: 1. Algoritmos de Busca são técnicas de Inteligência Artificial aplicadas a problemas de alta complexidade teórica que não são resolvidos com técnicas de programação convencionais, principalmente as de natureza puramente numérica; 2. A "complexidade" de um problema está diretamente relacionada ao tamanho do seu "Espaço de Busca"correspondente. Hipótese Simplificadoras (Redução de Problemas do Mundo Real): 1. O conhecimento do domínio específico pode ser representado em Estados de Busca, formalmente definíveis por meio de variáveis de memória; 2. O processo de solução de um problema pode ser reduzido a um Algoritmo de Busca Heurística, cujo Espaço de Busca é formado por transformações sucessivas de Estados em uma certa ordem degeração e percurso. Conseqüências: 1. Redução da explosão combinatória de possibilidades de Busca; 2. O trabalho humano se restringe à atuação empírica de identificar e formalizar: (a) representações de estados; (b) parâmetros Heurísticos; (c) operações de transformações atômica; (d) combinadores de transformações que atinjam a solução com tempos e tamanhos de memória aceitáveis.

Exemplos deSub-Problemas, Espaços e Problemas e Algoritmos de Busca
1. Definição precisa do sub-problema; 2. Análise do problema; 3. Isolamento e representação do conhecimento de um Estado de Busca; 4. Escolha das técnicas "apropriadas" de Busca Heurística. Exemplo: Um programa para o jogo de Xadrez entre humanos e maquinas. (a) (1) (2) (3) (4) (5) (6) (7) (8) o2 X2 o2 Y2 o2 Z2 o2 RE2 o2 RA2 o2 Z2 o2 Y2 o2 X2 X1o1 (b) Y1 o1 ? ? (c) Z1 o1 (d) RE1 o1 (e) RA1 o1 (f) Z1 o1 (g) Y1 o1 (h) X1 o1

Algoritmos de Busca Heurística (PARTE 1) Elementos Envolvidos no Jogo de Xadrez: 1. Estado Inicial: (X1,a,1) V (Y1,b,1)

4

V ... V (vazia,d,4) V ... V (X2,h,8)

2. Estado(s) Final(is) = Estado Meta = Estado Solução: Regras (operações) e/ou Fatos (variáveis) que definem todas as condições possíveis deSolução/Vitória. 3. Espaço de Busca (ou Espaço de Solução de Sub-Problema): Grafos que representam a plicação sucessiva e cumulativa de operações atômicas sobre o Estado Inicial, até incluir o Estado Final em seu conjunto de nodos. Por exemplo, se em um subproblema sempre são aplicáveis duas operações em 20 movimentos, temos:

220 = mais de 1 milhão. 120 Em Xadrez, existem aproximadamente 10 posiçõespossíveis no tabuleiro !!!
2x2x2x ... x2 = 4. Regras (Operações) lícitas de transformação atômica de um estado para outro. Exemplo de Regra ou Operação de transformação atômica: REGRA k: SE (Peao_Branco, b,2) & (vazia,b,3) (vazia,b,4) ENTÃO MOVER(Peao_Branco,b,4) FIM-REGRA 5. Função Heurística: de redução da Explosão Combinatória do Espaço de Busca: Um sub-Espaço de Busca "relevante" e...
tracking img