Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

  • View
    110

  • Download
    4

Embed Size (px)

Text of Busca informada (heurística) Parte 2 Sistemas Inteligentes junho/2005

  • Slide 1
  • Busca informada (heurstica) Parte 2 Sistemas Inteligentes junho/2005
  • Slide 2
  • A* com limite de memria (IDA*) Interative Deepening A* - IDA ou em portugus AIA* A busca em profundidade interativa modificada para usar um limite custo f(n) ao invs do limite de profundidade A cada interao todos os ns dentro do contorno do custo corrente so expandidos Prtico para problemas de passo unitrio Evita a sobrecarga de manter uma fila ordenada de ns Dois tipos de algoritmos: BRPM e LMA*
  • Slide 3
  • Busca Recursiva pelo melhor (BRPM) Tenta imitar a busca pela melhor escolha-padro Utiliza espao linear semelhante busca em profundidade recursiva, mas guarda o valor de f do melhor caminho alternativo Se o custo do n atual exceder f, a recurso retorna ao caminho alternativo Repe o valor de f de cada n ao longo do caminho com o melhor valor de f de seus filhos Podendo decidir se vale a pena voltar a expandir uma rvore esquecida
  • Slide 4
  • Slide 5
  • Slide 6
  • Slide 7
  • Busca Recursiva pelo melhor (BRPM) Ainda sofre da gerao excessiva de ns toda vez que o melhor caminho expandido, h uma boa chance que o valor de f aumente E ento um 2 melhor caminho deve ser seguido, reexpandindo os ns esquecidos timo se h(n) admissvel Complexidade de espao O(bd) Complexidade de tempo depende: Da exatido da funo heurstica Da freqncia com que o melhor caminho muda a medida que os ns so expandidos
  • Slide 8
  • A* limitado pela memria (LMA*) (simplificado) Executa o algoritmo A* porm este s explora um limite mximo de memria Define o nmero de ns que podem estar simultaneamente na memria Guarda informaes sobre as sub-rvores esquecidas completo: se existir memria suficiente para alcanar a soluo de menor profundidade timo: se existir memria suficiente para alcanar a soluo tima de menor profundidade Caso contrrio ele ir retornar a melhor soluo dentro dos limites de memria.
  • Slide 9
  • LMSA*
  • Slide 10
  • Em problemas muito complexos: O algoritmo ser forado a alternar continuamente entre um conjunto de caminhos de solues candidatas Somente um pequeno conjunto pode caber na memria Lembra problema de trashing em sistemas de paginao Problemas solveis com A* podem ser tornar intratveis com LMSA*
  • Slide 11
  • Exerccio: LMSA* com 4 ns Incio objetivo
  • Slide 12
  • Algoritmos de busca local e problemas de otimizao Em muitos problemas de otimizao o caminho at a soluo irrelevante O estado objetivo a soluo Exemplo: n-rainhas o que importa a configurao final e no a ordem em que as rainhas foram acrescentadas Outros exemplos: Projeto de CIs Layout de instalaes industriais Escalonamento de jornadas de trabalho Otimizao de redes de telecomunicaes Roteamento de veculos Outras aplicaes
  • Slide 13
  • Algoritmos de busca local e problemas de otimizao O espao de estados o conjunto completo de todas as configuraes Operam sobre um nico estado corrente, ao invs de vrios caminhos Em geral se movem apenas para os vizinhos desse estado Vantagens: Ocupam pouqussima memria (normalmente constante) Podem encontrar solues razoveis em grandes ou infinitos espaos de estados, para os quais os algoritmos sistemticos so inadequados
  • Slide 14
  • Algoritmos de busca local Algoritmos de busca local so teis para resolver problemas de otimizao puros Onde o objetivo encontrar o melhor estado de acordo com uma funo objetivo Normalmente o espao de estados considerado como tendo uma topologia onde existe: Uma posio definida pelo estado Uma elevao definida pelo valor da funo de custo da heurstica ou da funo objetivo
  • Slide 15
  • Algoritmos de busca local Elevao = custo -> objetivo = mnimo global Elevao = funo objetivo -> objetivo = mximo global completo se sempre encontra um objetivo timo se sempre encontra um mnimo/mximo global
  • Slide 16
  • Busca de subida de encosta (Hill-Climbing) function HILL-CLIMBING(problema) returns um estado que o mximo local inputs:problema, um problema local:atual, um nodo vizinho, um nodo atual