Class2

✬

Sistemas Inteligentes, 10/11

✩
1

Busca de Solu¸ c˜ oes

• estrat´egia de busca
• ´arvore de busca
• n´ o de busca (estado inicial: raiz da ´arvore)
• expans˜ ao de n´os da a´rvore
• estruturas de dados para as ´arvores de busca
• cada n´o ´e uma estrutura com pelo menos 5 componentes/campos: – estado
– n´o pai
– jogada/regra aplicada para gerar o n´o
– n´ umero de n´ os no caminho para este n´o (profundidade do n´o na a´rvore)
– custo do caminho desde o n´o raiz
✫

✪

✩

✬

Sistemas Inteligentes, 10/11

2

Busca de Solu¸ c˜ oes
• datatype node components: STATE, PARENT NODE,
OPERATOR, DEPTH, PATH COST
• Necess´aria representa¸c˜ao para lista de n´os que ainda n˜ ao foram expandidos • Escolha: fila de n´os com as seguintes opera¸c˜oes:
– MAKE QUEUE(Elementos)
– EMPTY?(Queue)
– REMOVE FRONT(Queue) (fun¸c˜ao)
– QUEUEING FN(Elementos,Queue)
✫

✪

✩

✬

Sistemas Inteligentes, 10/11

3

Busca de Solu¸ c˜ oes function GENERAL_SEARCH(problem, QUEUEING_FN) retorna solucao ou falha nodes := MAKE_QUEUE(MAKE_NODE(INITIAL_STATE(problem))) loop if EMPTY?(nodes) then return falha node := REMOVE_FRONT(nodes) if STATE(node) = GOAL_TEST[problem] then return node new_nodes := EXPAND(node,OPERATORS(problem)) nodes := QUEUEING_FN(nodes,new_nodes) end avel!
Obs: QUEUEING FN ´e uma fun¸c˜ao vari´
✫

✪

✩

✬

Sistemas Inteligentes, 10/11

4

Busca de Solu¸ c˜ oes: Estrat´ egias • Avalia¸c˜ao:
– completude
– complexidade temporal
– complexidade espacial
– otimalidade

✫

✪

✬

Sistemas Inteligentes, 10/11

✩
5

M´ etodos n˜ ao informados de busca (busca cega)
• largura (BL)
• custo uniforme (BCU)
• profundidade (BP)
• limitada em profundidade (BLP)
• profundidade iterativa (BPI)
• bidirecional (BB)

✫

✪

✩

✬

Sistemas Inteligentes, 10/11

6

Busca em Largura (BL)
• todos os n´ os e n´ıvel d na ´arvore de busca s˜ ao expandidos antes dos n´ os de n´ıvel d+1
• fun¸c˜ao QUEUEING FN: fifo function BREADTH_FIRST_SEARCH(problem) retorna solucao ou falha
return