Algoritmos de Busca: Busca Cega e Busca Informada
Os algoritmos de busca são amplamente utilizados para a solução de problemas em sistemas de inteligência artificial. Eles consistem na exploração de espaços de estados para encontrar uma solução a partir de um estado inicial até um estado objetivo. As abordagens de busca podem ser classificadas em dois tipos principais: busca cega (uninformed search) e busca informada (informed search). (BARROS, 2006)1. Agente de Solução de Problemas
Um agente que resolve problemas por meio de busca passa pelas seguintes etapas (NILSSON, 1980):- Formulação de objetivo: o agente define um ou mais objetivos a serem alcançados.
- Formulação de problema: o agente descreve os estados e ações necessárias para atingir o objetivo.
- Busca: antes de executar ações, o agente simula sequências de ações em um modelo de estados.
- Execução: as ações definidas na etapa de busca são realizadas para atingir o estado objetivo.
2. Busca Cega (Uninformed Search)
A busca cega, também chamada de busca não informada, é uma estratégia onde o agente não possui nenhuma informação adicional sobre a distância até o objetivo, exceto os estados e as ações possíveis a partir de cada estado. Ela explora o espaço de estados de forma sistemática, sem orientação específica (BARROS, 2010).- Busca em largura (Breadth-First Search – BFS): explora todos os nós de um nível antes de avançar para o próximo.
É completa e encontra a solução de menor custo, desde que todas as ações tenham custo uniforme. (NILSSON, 1980)
- Completude: sim
- Complexidade de tempo:O(b^d)
- Complexidade de espaço:O(b^d)
- Busca em profundidade (Depth-First Search – DFS): explora o caminho até o nível mais profundo antes de retroceder.
É mais eficiente em termos de memória, mas não é completa para espaços infinitos e pode não encontrar a solução de menor custo. (BARROS, 2010)
- Completude: não, em espaços infinitos
- Complexidade de tempo: O(b^m)
- Complexidade de espaço: O(bm)
3. Busca Informada (Informed Search)
A busca informada, ou heurística, utiliza informações adicionais sobre o problema para guiar a busca em direção ao objetivo de forma mais eficiente. Essa informação é fornecida por uma função heurística \( h(n) \), que estima o custo para atingir o objetivo a partir do estado atual (RUSSELL; NORVIG, 2010).
Principais algoritmos de busca informada
- Busca gulosa (Greedy Best-First Search): expande o nó que parece mais promissor de acordo com a função heurística.
Embora rápida, não é completa nem ótima em todos os casos. (BARROS, 2010)
- Completude: não, em todos os casos
- Otimização de custo: não garante a solução de menor custo
- Busca A*: combina a busca de custo uniforme e a busca gulosa, utilizando uma função de avaliação \( f(n) = g(n) + h(n) \),
onde \( g(n) \) é o custo do caminho até o nó \( n \) e \( h(n) \) é a estimativa heurística do custo restante.
A busca A* é completa e ótima se a heurística for admissível. (RUSSELL; NORVIG, 2010)
- Completude: sim
- Otimização de custo: sim, se \( h(n) \) for admissível
4. Comparação: Busca Cega vs. Busca Informada
| Critério | Busca Cega | Busca Informada |
|---|---|---|
| Uso de informação | Não utiliza informações adicionais | Utiliza funções heurísticas |
| Eficiência | Menor eficiência | Maior eficiência |
4.1 Mundo do Aspirador
O problema do mundo do aspirador é um exemplo clássico de problema de busca e planejamento, onde um agente (aspirador) deve limpar um conjunto de células em uma grade, movendo-se entre elas. O ambiente é geralmente representado por uma grade 2D, onde algumas células estão sujas e outras limpas. O agente tem a capacidade de se mover para direções específicas (como norte, sul, leste e oeste) e limpar a célula em que se encontra, enquanto tenta alcançar o objetivo de limpar todas as células do ambiente.
A solução para esse problema pode ser implementada com um algoritmo de busca como a busca em largura (breadth-first search) ou a busca em profundidade (depth-first search), dependendo da complexidade e dos requisitos de eficiência. Para um ambiente simples e pequeno, a busca em profundidade pode ser suficiente, onde o agente explora recursivamente suas opções, movendo-se até uma célula limpa e depois retornando se necessário.
Uma abordagem mais sofisticada seria a utilização de algoritmos de planejamento, que consideram as ações do aspirador como parte de uma sequência planejada de tarefas. O algoritmo de busca A* (A-star) pode ser utilizado aqui, já que ele é eficiente para encontrar o caminho mais curto considerando uma heurística que aproxima a distância do estado atual até o estado objetivo (todas as células limpas). Nesse caso, a função de custo pode ser baseada no número de células que o aspirador precisa limpar, enquanto a heurística pode estimar o número de células sujas restantes.
4.2 Problema do Caixeiro Viajante (TSP)
O problema do caixeiro viajante (TSP) é um clássico problema de otimização, no qual o objetivo é encontrar o caminho mais curto que permita a um vendedor visitar um conjunto de cidades e retornar à cidade de origem. O TSP é um problema NP-difícil, o que significa que sua solução exata leva um tempo exponencial em relação ao número de cidades, tornando-o impraticável para grandes conjuntos de cidades. Por esse motivo, soluções aproximadas e heurísticas são frequentemente usadas.
Uma das abordagens mais comuns para resolver o TSP é o algoritmo de força bruta, que gera todas as possíveis permutações das cidades e calcula o custo total de cada uma, selecionando a sequência que resulta no menor custo. Esse método é eficaz para um número pequeno de cidades, mas se torna extremamente lento à medida que o número de cidades cresce, já que o número de permutações possíveis é fatorial (n!).
Uma alternativa mais eficiente é o uso de algoritmos de busca local, como o algoritmo de troca 2-opt. Esse método começa com uma solução inicial (por exemplo, uma sequência aleatória de cidades) e tenta melhorar essa solução trocando pares de cidades em sua ordem. Se a troca resultar em um caminho de menor custo, ela é mantida, e o processo é repetido até que não haja mais melhorias possíveis.
Além disso, algoritmos como algoritmos genéticos, simulated annealing e algoritmos de colônia de formigas também são aplicados ao TSP. Esses métodos buscam encontrar boas soluções aproximadas em um tempo razoável. No caso do algoritmo genético, uma população de soluções potenciais é evoluída ao longo do tempo através de operações como cruzamento e mutação, sempre selecionando as soluções com menor custo para formar a próxima geração.
Por fim, para problemas de TSP com muitas cidades, as soluções exatas se tornam inviáveis, e, por isso, a abordagem mais comum é o uso de heurísticas e metaheurísticas, que garantem encontrar soluções boas em tempo razoável, embora não necessariamente ótimas.
Em ambos os problemas — o mundo do aspirador e o caixeiro viajante — os algoritmos de busca e otimização desempenham um papel fundamental. O mundo do aspirador utiliza algoritmos de busca como a busca em largura e A*, enquanto o TSP, por ser mais complexo, é abordado com técnicas como força bruta para problemas pequenos e algoritmos de otimização aproximada (como 2-opt e algoritmos genéticos) para cenários mais desafiadores e com muitas cidades. Ambos os problemas exemplificam como a inteligência artificial pode ser aplicada para resolver tarefas de planejamento e otimização em ambientes controlados e do mundo real.