Algoritmos de Busca Heurística

  • View
    213

  • Download
    1

Embed Size (px)

Text of Algoritmos de Busca Heurística

  • Algoritmos de Busca Heurstica (PARTE 1) 1

    Universidade Federal doParan

    Departamento de Informtica

    Algoritmos deBusca Heurstica(Parte 1)

    Alexandre I. DireneE-mail: alexd@inf.ufpr.br

    Web: http://www.inf.ufpr.br/~alexd

  • Algoritmos de Busca Heurstica (PARTE 1) 2

    BIBLIOGRAFIARECOMENDADA1- 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. Inteligncia Artificial: Ferramentas e Teorias. TerceiraEdio, Editora da UFSC, 2006 (ISBN: 85-328-0138-2).

    4- Elaine Rich e Kevin Knight, Artificial Intelligence, Second Edition, McGrawHill, 1993.

    5- Patrick H. Winston, Artificial Intelligence, Second Edition, Addison-Wesley,1993.

    PGINASRECOMENDADAS

    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

    SOFTWARERECOMENDADOS

    http://www.cs.bham.ac.uk/research/poplog/freepoplog.html

    http://www.swi-prolog.org

    http://www.cs.dartmouth.edu/~brd/Teaching/AI/Lectures/Summaries/search.htmlhttp://www.cs.bham.ac.uk/research/poplog/freepoplog.htmlhttp://www.cs.bham.ac.uk/research/poplog/freepoplog.htmlhttp://aima.cs.berkeley.edu/newchap05.pdfhttp://aima.cs.berkeley.edu/http://www.decom.ufop.br/prof/guarda/CIC250/index.htm

  • Algoritmos de Busca Heurstica (PARTE 1) 3

    Algoritmos de Busca

    Caractersticas:

    1. Algoritmos de Busca so tcnicas de Inteligncia Artificial aplicadas a problemas de altacomplexidade terica que no so resolvidos com tcnicas de programaoconvencionais, principalmente as de natureza puramente numrica;

    2. A "complexidade" de um problema est diretamente relacionada ao tamanho do seu"Espao de Busca" correspondente.

    Hiptese Simplificadoras (Reduo de Problemas do Mundo Real):

    1. O conhecimento do domnio especfico pode ser representado em Estados de Busca,formalmente definveis por meio de variveis de memria;

    2. O processo de soluo de um problema pode ser reduzido a um Algoritmo de BuscaHeurstica, cujo Espao de Busca formado por transformaes sucessivas deEstados em uma certa ordem de gerao e percurso.

    Conseqncias:

    1. Reduo da exploso combinatria de possibilidades de Busca;

    2. O trabalho humano se restringe atuao emprica de identificar e formalizar: (a)representaes de estados; (b) parmetros Heursticos; (c) operaes detransformaes atmica; (d) combinadores de transformaes que atinjam a soluocom tempos e tamanhos de memria aceitveis.

    Exemplos de Sub-Problemas, Espaos e Problemas e Algoritmos de Busca

    1. Definio precisa do sub-problema;

    2. Anlise do problema;

    3. Isolamento e representao do conhecimento de um Estado de Busca;

    4. Escolha das tcnicas "apropriadas" de Busca Heurstica.

    Exemplo: Um programa para o jogo de Xadrez entre humanos e maquinas.

    (a) (b) ( c ) (d) (e) (f) (g) (h)

    (1) X1 Y1 Z1 RE1 RA1 Z1 Y1 X1

    (2) o1 o1 o1 o1 o1 o1 o1 o1

    (3) ?

    (4) ?

    (5)

    (6)

    (7) o2 o2 o2 o2 o2 o2 o2 o2

    (8) X2 Y2 Z2 RE2 RA2 Z2 Y2 X2

  • Algoritmos de Busca Heurstica (PARTE 1) 4

    Elementos Envolvidos no Jogo de Xadrez:

    1. Estado Inicial: (X1,a,1) V (Y1,b,1) V ... V (vazia,d,4) V ... V (X2,h,8)2. Estado(s) Final(is) = Estado Meta = Estado Soluo: Regras (operaes) e/ou Fatos

    (variveis) que definem todas as condies possveis de Soluo/Vitria.

    3. Espao de Busca (ou Espao de Soluo de Sub-Problema): Grafos que representam aplicao sucessiva e cumulativa de operaes atmicas sobre o Estado Inicial, atincluir o Estado Final em seu conjunto de nodos. Por exemplo, se em umsub-problema sempre so aplicveis duas operaes em 20 movimentos, temos:

    2 x 2 x 2 x . . . x 2 = 220 = mais de 1 milho. Em Xadrez, existem aproximadamente 10120 posies possveis no tabuleiro !!!

    4. Regras (Operaes) lcitas de transformao atmica de um estado para outro.

    Exemplo de Regra ou Operao de transformao atmica:

    REGRA k: SE (Peao_Branco, b,2) &(vazia,b,3) &(vazia,b,4)

    ENTO

    MOVER(Peao_Branco,b,4)

    FIM-REGRA

    5. Funo Heurstica: de reduo da Exploso Combinatria do Espao de Busca: Umsub-Espao de Busca "relevante" e "processvel" para a estado corrente.

    O Domnio dos Recipientes de gua

    So dados 2 Recipientes:

    Recipiente-1 (capacidade 4 litros);

    Recipiente-2 (capacidade 3 litros);

    Os recipientes no tem marcas de medidas.

    Problema: Colocar exatamente 2 litros no recipiente-1.

    Elementos formais envolvidos:

    1. Representao de um Estado de Busca qualquer: par ordenado de inteiros nonegativos.

    2. Estado de Final: (2 , QUALQUER);

    3. Espao de Busca: Espao Cartesiano composto pelo conjunto de pares ordenados deinteiros (x,y) tal que x pertence a {0, 1, 2, 3, 4} e y pertence a {0, 1, 2, 3};

    4. Estado Inicial: (0 , 0);

    Resumo dos passos de uma soluo do sub-problema em foco:

  • Algoritmos de Busca Heurstica (PARTE 1) 5

    Recip - 1

    (4 Litros)

    Recip - 2

    (3 Litros)

    Regra

    0 0 2

    0 3 9

    3 0 2

    3 3 7

    4 2 5

    0 2 9/11

    2 0 -

    Conjunto possvel de regras (operaes) de transformao atmica:

    Regra Estado Inicial Condicional deRegra

    Estado Final

    1 (x,y) x < 4 (4,y)

    2 (x,y) y < 3 (x,3)

    3 (x,y) x > 0 (x-d,y)

    4 (x,y) y > 0 (x,y-d)

    5 (x,y) x > 0 (0,y)

    6 (x,y) y > 0 (x,0)

    7 (x,y) x+y 4 & y > 0 (4,y-(4-x))

    8 (x,y) x+y 3 & x > 0 (x-(3-y),3))

    9 (x,y) x+y 4 & y > 0 (x+y,0)

    10 (x,y) x+y 3 & x > 0 (0,x+y)

    11 (0,2) (2,0)

    12 (2,y) (0,y)

    O Donnio do Jogo da Velha

    SOLUO 1 :

    1 2 3

    4 5 6 1 2 3 4 5 6 7 8 9

    7 8 9

    Estado de Busca = Espao de Busca: Todos os tabuleiros possveis = 39 = 19.683

    onde: 0 vazio1 x2 0

  • Algoritmos de Busca Heurstica (PARTE 1) 6

    1 2 19.683

    Algoritmo de Busca:

    1. Visualizar o tabuleiro corrente em BASE-3 (valores 0,1,2) e converter para BASE-10;

    2. Usar o nmero calculado como ndice de entrada no Espao de Busca;

    3. O tabuleiro selecionado representa a prxima jogada plausvel.

    Comentrios: muito eficiente, porm h vrias desvantagens:

    1. Muita memria para armazenar as combinaes de tabuleiros;

    2. Algum deve despender enormes esforos manuais para ORGANIZAR o espao de tabuleiros;

    3. Espao de tabuleiros pode conter ERROS de criao;

    4. Se ampliarmos as dimenses do tabuleiro, o algoritmo no funciona.

    SOLUO 2 :

    1 2 3

    4 5 6 1 2 3 4 5 6 7 8 9

    7 8 9

    Estado de Busca: Apenas 1 (um) tabuleiro !

    I = 1 2 3 4 5 6 7 8 9

    Algoritmo de Busca:

    1. Retorna o nmero do quadrado vencedor se o jogador atual tiver condies de ganhar. Casocontrrio, retorna o nmero do quadrado para o movimento vitorioso do oponente se essetiver a chance de ganhar no prximo movimento. Caso contrrio, retorna 5 se o quadradocentral estiver em branco. Caso contrrio, retorna qualquer quadrado em branco que noseja de canto;

    2. Efetua movimento no quadrado N (parmetro de retorno), ajustando posio para "x" (X) se ajogada for impar e para "o" (O) se a jogada for par.

    Comentrios: No to eficiente como o primeiro mas tem vantagens:

    onde: v vaziox Xo O

  • Algoritmos de Busca Heurstica (PARTE 1) 7

    1. Requer pouco espao;

    2. Fcil de entender a estratgia.

    Desvantagens:

    1. Parece apenas se defender pois no usa nenhuma ferramenta de nvel ttico para gerirmemria avanada;

    2. Tambm no generalizvel para 3 dimenses.

    SOLUO 3 :

    Estado de Busca:

    1. Apenas 1 (um)tabuleiro.

    1 2 3 4 5 6 7 8 9

    2. Nmero representando uma estimativa (heurstica) que o tabuleiro tem de levar vitoria.

    Algoritmo de Busca (MINIMAX):

    1. Verifique prximas jogadas diretamente atingveis a partir do tabuleiro corrente se a alturamxima de busca no tiver sido alcanada, caso contrrio, retorne o a estimativa(heurtica) do tabuleiro corrente;

    2. Caso uma se trate de posio de vitria, d a ela a mais alta estimativa possvel e retorneeste valor;

    3. Caso contrrio, considere todos os movimentos que o oponente possa fazer em seguida.Assuma que o oponente far a pior jogada contra a mquina. Ative recursivamente aexpanso de estados;

    4. A prxima jogada plausvel o do tabuleiro com a mais alta estimativa.

    ineficiente do ponto de vista de tempo de pesquisa pois cria sub-rvores de jogadas tambm para ooponente como forma de planejamento, mas tem vantagens:

    1. mais genrico que os outros;

    2. Pode ser usado at para outros jogos, o que no seria possvel com os outros dois algoritmosvistos.

    Principais Algoritmos de Busca Heurstica:

    Busca em Grafos OU (Gerar e Testar, Subida de Encosta, Melhor Escolha,S