Algoritmos cegos: largura-primeiro; profundidade-primeiro; iterativos;
š Leituras
- (Russell & Norvig): SecƧƵes 3.1 a 3.4 (3ĀŖ e 4ĀŖ edição) | CapĆtulo 3 (2ĀŖ edição)
Bibliografia
┠Ação: O que é um agente de resolução de problemas?
š Ć um agente que procura uma sequĆŖncia de aƧƵes que o leve do estado inicial atĆ© um estado objetivo, utilizando um processo de procura.
ā” Ação: Em que tipo de ambientes os agentes de resolução de problemas operam neste capĆtulo?
š Em ambientes episódicos, determinĆsticos, totalmente observĆ”veis, estĆ”ticos, discretos e conhecidos.
┠Ação: O que é a formulação do objetivo?
š Ć o processo em que o agente define o que pretende alcanƧar, restringindo as aƧƵes relevantes.
┠Ação: O que é a formulação do problema?
š Ć a definição dos estados, aƧƵes, modelo de transição, estado inicial e estados objetivo.
┠Ação: Porque é que a formulação do problema é uma abstração?
š Porque ignora detalhes irrelevantes do mundo real, mantendo apenas o que Ć© necessĆ”rio para encontrar uma solução.
ā” Ação: O que significa um sistema ser āopenāloopā?
š Significa que o agente executa a sequĆŖncia de aƧƵes sem consultar novos perceptos, assumindo que o ambiente nĆ£o muda.
ā” Ação: Quando Ć© que um agente deve usar um sistema āclosedāloopā?
š Quando o ambiente Ć© incerto, parcialmente observĆ”vel ou pode mudar durante a execução.
┠Ação: O que é um estado objetivo?
š Um estado que satisfaz a condição definida pelo mĆ©todo ISāGOAL do problema.
┠Ação: O que é um caminho numa procura?
š Uma sequĆŖncia de aƧƵes que liga o estado inicial a um estado objetivo.
┠Ação: O que caracteriza uma solução ótima?
š Ć a solução com menor custo total entre todas as soluƧƵes possĆveis.
┠Ação: Porque é que a abstração é essencial na formulação de problemas?
š Porque reduz a complexidade, permitindo que o agente encontre soluƧƵes sem ser sobrecarregado por detalhes irrelevantes.
┠Ação: O que distingue problemas padronizados de problemas reais?
š Problemas padronizados tĆŖm formulaƧƵes simples e exatas; problemas reais tĆŖm formulaƧƵes complexas e dependem do domĆnio.
┠Ação: Quantos estados tem o mundo do aspirador com duas células?
š Oito estados, resultantes das combinaƧƵes de posição e sujidade.
ā” Ação: O que define o estado no 8āpuzzle?
š A posição de cada peƧa e do espaƧo vazio na grelha 3Ć3.
ā” Ação: Porque Ć© que metade dos estados do 8āpuzzle nĆ£o tĆŖm solução?
š Porque o espaƧo de estados estĆ” dividido em duas classes de paridade, e apenas uma Ć© alcanƧƔvel a partir de um dado estado inicial.
ā” Ação: O que caracteriza o problema de Knuth (4, ā, !)?
š Tem um espaƧo de estados infinito, porque a operação fatorial pode gerar nĆŗmeros arbitrariamente grandes.
ā” Ação: O que torna o Sokoban um problema difĆcil?
š O nĆŗmero enorme de estados e a necessidade de evitar posiƧƵes irrecuperĆ”veis ao empurrar caixas.
┠Ação: Porque é que problemas reais como viagens aéreas exigem estados mais complexos?
š Porque o custo e as aƧƵes dependem de fatores históricos, horĆ”rios, ligaƧƵes e restriƧƵes adicionais.
┠Ação: O que caracteriza um problema de touring como o TSP?
š O objetivo Ć© visitar um conjunto de locais, minimizando o custo total da viagem.
┠Ação: Porque é que a navegação de robÓs tem um espaço de estados muito grande?
š Porque envolve posiƧƵes contĆnuas e mĆŗltiplos graus de liberdade, como Ć¢ngulos de juntas.
┠Ação: O que é a Ôrvore de procura?
š Ć a estrutura construĆda pelo algoritmo, contendo caminhos possĆveis desde o estado inicial.
┠Ação: O que é a fronteira?
š O conjunto de nós gerados mas ainda nĆ£o expandidos.
ā” Ação: O que significa um estado ter sido āatingidoā?
š Que existe pelo menos um nó na Ć”rvore correspondente a esse estado.
┠Ação: Porque é que a Ôrvore de procura pode ter vÔrios nós para o mesmo estado?
š Porque diferentes sequĆŖncias de aƧƵes podem levar ao mesmo estado.
┠Ação: O que é o modelo de transição?
š A função RESULT(s,a) que indica o estado resultante de aplicar a ação a no estado s.
┠Ação: Porque é que ciclos são problemÔticos na procura?
š Porque podem gerar caminhos infinitos ou repetidos, desperdiƧando tempo e memória.
┠Ação: O que distingue procura em Ôrvore de procura em grafo?
š A procura em grafo evita gerar estados jĆ” atingidos, prevenindo repetiƧƵes.
┠Ação: Porque é que a procura em grafo é mais eficiente?
š Porque evita expandir estados repetidos, reduzindo o espaƧo de procura.
ā” Ação: Quando Ć© que a procura em Ć”rvore pode ser preferĆvel?
š Quando o espaƧo de estados Ć© pequeno ou quando nĆ£o Ć© possĆvel testar estados repetidos.
┠Ação: O que caracteriza um algoritmo de procura cego?
š NĆ£o utiliza qualquer informação adicional alĆ©m da definição do problema; nĆ£o sabe que aƧƵes sĆ£o melhores.
┠Ação: O que determina o comportamento de um algoritmo cego?
š A forma como escolhe o próximo nó da fronteira para expandir.
┠Ação: Porque é que a ordem de expansão é crucial?
š Porque determina que caminhos sĆ£o explorados primeiro e afeta tempo, memória e completude.
┠Ação: O que significa expandir um nó?
š Gerar todos os sucessores aplicando as aƧƵes possĆveis ao estado do nó.
┠Ação: Porque é que a procura cega pode explorar muitos estados desnecessÔrios?
š Porque nĆ£o tem forma de distinguir estados promissores de estados irrelevantes.
┠Ação: O que é a ramificação b?
š O nĆŗmero mĆ”ximo de sucessores que um nó pode ter.
┠Ação: O que é a profundidade da solução d?
š O nĆŗmero de aƧƵes no caminho mais curto atĆ© um estado objetivo.
┠Ação: O que é a profundidade mÔxima m?
š O comprimento do caminho mais longo possĆvel na Ć”rvore de procura.
┠Ação: Porque é que custos negativos são problemÔticos?
š Porque podem criar ciclos de custo total negativo, levando a soluƧƵes infinitas.
┠Ação: Porque é que a procura cega é importante apesar das limitações?
š Porque fornece a base conceptual para algoritmos informados e garante completude em muitos casos.
Nova pergunta: š²