Inteligência ArtificialVisão geral
Resolução de Problemas como Busca
Um problema de busca é a quíntupla (S, s₀, A, G, c): estados, origem, ações legais, teste de objetivo e custo de passo. g(n) soma os c do caminho até n.
Fronteira, heurística, recozimento e minimax deste tópico — e sistemas de produção no seguinte — partem dessa quíntupla.
As páginas se agrupam em cinco blocos. O primeiro formula o espaço: o que é estado, de onde se parte, quais ações são legais, quando se chegou e quanto o caminho custa.
O segundo escolhe quem sai da fronteira — só a estrutura do grafo, ou com h(n) — e decide completeza e otimalidade.
O terceiro maximiza f(x) na vizinhança: subida até máximo local e recozimento e^(−Δ/T).
O quarto avalia árvore de jogo: MAX e MIN, o valor sobe das folhas, poda alfa-beta com o mesmo v na raiz.
O quinto preenche a tríplice (X, D, C) até uma atribuição completa e consistente.
Formulação de Problemas de Busca escreve a quíntupla e g(n). Estratégias de Busca escolhe a fronteira: fila, pilha, menor g ou f = g+h.
f = g+h rumo a G está em Estratégias de Busca. f(x) e o vizinho de x estão em Busca Local e Maximização de Função.
Definir v(n) no xadrez, com um lance na raiz, está em Minimax como algoritmo principal para jogos de dois jogadores (xadrez). Cortar quando α ≥ β e o irmão deixa de ser visitado, esquerda→direita, está em Minimax e Alfa-Beta.
α (piso de MAX) e β (teto de MIN), com a janela que esvazia, estão em Busca Adversarial. O valor que sobe das quatro folhas e o mesmo v na raiz estão em Minimax e Alfa-Beta.
Páginas deste tópico
Formulação de Problemas de Busca
ProMédia incidência no POSCOMP10 min de leitura · 18ª mais cobrada em Inteligência Artificial
Quíntupla S, s0, A, GoalTest, c; g(n) é soma do caminho, não A*.
Estratégias de Busca
ProAlta incidência no POSCOMP21 min de leitura · 3ª mais cobrada em Inteligência Artificial
BFS/DFS/IDDFS/UCS e gulosa/A*; h admissível e consistente; sem busca local.
Busca Local e Maximização de Função
ProAlta incidência no POSCOMP13 min de leitura · 11ª mais cobrada em Inteligência Artificial
Maximizar f no espaço de candidatos; HC, platô/crista; SA com e^(−Δ/T).
Minimax como algoritmo principal para jogos de dois jogadores (xadrez)
ProBaixa incidência no POSCOMP12 min de leitura · 33ª mais cobrada em Inteligência Artificial
Minimax como algoritmo principal para jogos de dois jogadores (xadrez)
Busca Adversarial
ProBaixa incidência no POSCOMP13 min de leitura · 31ª mais cobrada em Inteligência Artificial
alfa-beta poda ramos de uma árvore de jogo de dois jogadores; o gabarito trata a frase do enunciado como falsa por misturar vocabulário de busca de agente
Satisfação de Restrições
ProBaixa incidência no POSCOMP16 min de leitura · 32ª mais cobrada em Inteligência Artificial
CSP como forma de resolver problemas em IA: variáveis, domínios e restrições.
Minimax e Alfa-Beta
ProMédia incidência no POSCOMP11 min de leitura · 14ª mais cobrada em Inteligência Artificial
Poda alfa-beta: mesmo valor na raiz; corta quando α ≥ β e o irmão deixa de ser visitado (esquerda→direita)