No post de hoje, vou falar sobre uma classe de algoritmos fundamental para Ciência da Computação e em especial para a Inteligência Artificial: os algoritmos de busca em espaço de estados (state space search). Inclusive, muitos dos materiais didáticos sobre Inteligência Artificial (Norvig e Russel, e Luger, por exemplo) iniciam justamente com esse tipo de algoritmo, por terem serem simples e intuitivos (depois que você pega o jeito da coisa) mas também por serem amplamente utilizados.
Busca em espaço de estados: alguns conceitos
Muitos problemas em computação podem ser reduzidos ao problema de sair de um “estado de coisas” e chegar a um outro estado que constitui nosso objetivo. Mas, para chegar nesse objetivo, geralmente precisamos percorrer outros estados intermediários. O conjunto de “estados de coisas” que podem surgir num certo sistema é denominado de espaço de estados, e a tarefa de encontrar um modo de atravessar o espaço de estados do ponto inicial até o nosso objetivo constitui a busca no espaço de estados.
Existem vários exemplos de problemas que podem ser resolvidos por um computador através de algoritmos de busca, como uma torre de Hanoi, o problema das oito damas, e, é claro, meu resolvedor de jogos de sudoku.
Conceitos básicos de grafos
Uma maneira natural de representar o espaço de estados é através de um grafo. Não vou dar uma definição formal de grafos aqui (mas vale a pena dar uma olhada numa definição mais formal na Wikipédia). Por enquanto, basta imaginar um grafo como um conjunto de elementos denominados nós ou vértices, que podem ser conectados entre si através de arestas.
Cada vértice do grafo, então, representa um estado possível do sistema, e as arestas que conectam um vértice a outro representam ações que podem ser tomadas num determinado estado para chegar a outro. O grafo em si representa o próprio espaço de estados.
Por esse motivo, os algoritmos de busca em espaço de estados também podem ser considerados algoritmos de busca em grafos.
Em um grafo não direcionado, ou não orientado, como o apresentado acima, uma aresta ligando um ponto A a um ponto B implica que é possível tanto alcançar o ponto B a partir do A quanto alcançar o ponto A a partir do B. Ou seja, cada aresta é uma “via de mão dupla”.
Já num grafo direcionado, ou orientado, as arestas tem “sentidos” (no sentido de tráfego de carros mesmo). Ou seja, uma aresta A -> B, que liga A a B não liga B a A. Para fazer essa ligação, seria necessária uma outra aresta. B -> A. Arestas em grafos direcionados costumam ser representadas por setas ligando o vértice “de origem” ao vértice “de destino”, como no exemplo abaixo.
Caso você já tenha alguma familiaridade com conceitos de algoritmos e estruturas de dados como árvores binárias, você deve ter notado uma certa semelhança entre grafos e árvores. De fato, uma árvore é um tipo especial de grafo não orientado em que não existem ciclos e existe exatamente um caminho ligando quaisquer dois vértices. Um ciclo, por sua vez, é um caminho que passa por pelo menos três vértices e que leva de um vértice a ele mesmo, sem passar duas vezes por nenhum outro vértice.
Perceba que caso não fossem necessários pelo menos três vértices para compor um ciclo, qualquer caminho entre dois vértices de um grafo não direcionado formaria um ciclo, já que, para quaisquer vértices A e B, poderia se chegar de A para A pelo caminho A -> B -> A.
O grafo não orientado apresentado anteriormente não é uma árvore, pois existe um loop entre os vértices 1, 3, 4 e 2. Mas poderíamos transformá-lo em uma árvore removendo a aresta que liga o vértice 4 ao 2, “cortando” assim o loop. Em uma árvore, é possível estabelecer o nó original, do qual todos os outros derivam. Esse nó é chamado de nó raiz.
A depender da situação, um espaço de estados pode ser um grafo orientado, não orientado ou uma árvore.
A árvore de busca
Para representar nossa busca no espaço de estados, usaremos uma árvore, denominada de árvore de busca. A raiz de nossa árvore de busca será o estado inicial do problema, e todos os nós abaixo, representarão os estados alcançados depois de executar determinada ação.
É preciso prestar atenção nessa diferença sutil entre espaço de estados e árvore de busca. Grosso modo, o espaço de estados corresponde ao domínio onde nosso problema se dá, e utilizamos um grafo como abstração do problema. Enquanto a árvore de busca representa o procedimento de busca, e essa árvore será efetivamente construída pelo nosso algoritmo.
Para deixar a definição mais clara, veja abaixo a representação do espaço de estados de um problema envolvendo o deslocamento entre cidades da região metropolitana de Salvador.
Agora veja o exemplo de uma árvore de busca nesse espaço de estados em que se tenta alcançar Lauro de Freitas a partir de Salvador.
Como funciona a busca em espaço de estados
Um exemplo familiar de problema que pode ser resolvido com algoritmos de busca em grafos é o problema do path finding, que consiste em encontrar trajetos entre um ponto e outro em um determinado mapa, muito utilizados em robótica e jogos eletrônicos. Nesse caso, o espaço de estados é o conjunto de pontos do mapa, e o objetivo é encontrar uma série de pontos intermediários que levem do estado inicial até o estado objetivo.
A lógica por trás desse tipo de algoritmo é bastante simples. Suponha que queremos encontrar um trajeto entre um jogador e um tesouro num jogo de tabuleiro qualquer. Podemos definir que a posição atual do jogador é o estado inicial do problema, e que o ponto em que ele quer chegar é o estado objetivo, ou estado alvo.
Entre o estado inicial e o objetivo, existem vários outros estados possíveis, que são as posições para onde o jogador pode se mover para sair do seu estado e chegar ao objetivo. O personagem pode então executar uma certa quantidade de ações sobre esse estado, que fazem com que ele passe de um estado a outro. Essas ações podem ser, por exemplo, “ande para cima”, “ande para baixo”, “ande para a direita” e “ande para a esquerda”.
Nosso problema de encontrar um trajeto do ponto A para o ponto B pode ser resumido então em um problema de encontrar uma sequência de ações que modifiquem o estado do nosso jogador até que ele finalmente alcance o estado objetivo. Esse problema é, basicamente, um problema de busca em um espaço de estados. E a sequência de ações que resolve esse problema é chamado de solução.
Perceba que o espaço de estados desse exemplo não é uma árvore, pois é possível que o nosso agente tome uma série de decisões que o levem para o mesmo lugar (o que poderia levá-lo a um loop infinito). Evitar que nosso algoritmo de busca fique preso em loops é uma questão importante de implementação, já que uma vez preso em um loop, é possível que nosso algoritmo nunca pare e o programa “empaque”.
No início da busca, nossa árvore tem apenas o nó raiz, correspondente ao estado inicial do problema. Devemos proceder então expandindo o nó raiz para obter os estados em que podemos chegar aplicando determinadas ações sobre o estado inicial. Os nós que ficam na “ponta” da árvore, ou seja, que ainda não levam a outros nós (não foram expandidos), são chamados de nós folha (continuando a analogia com árvores).
Enquanto o algoritmo de busca não encontra um nó que corresponda ao objetivo, ele deve eleger um nó dentre esses nós folha para expandi-lo (novamente: verificando em que estados podemos chegar a partir desse estado). Então, o nó expandido deixa de ser um nó folha, e mais nós folha são inseridos na árvore. O conjunto de nós folha é chamado de lista aberta, ou de fronteira, já que eles estão no “final” da árvore e representam o conjunto de estados disponíveis para aplicarmos ações para expandir ainda mais a árvore.
Quando o algoritmo finalmente encontra o vértice que corresponde ao seu objetivo, ele deve indicar o caminho que percorreu para chegar até lá. Para fazer isso, precisamos indicar em cada vértice qual foi o vértice que o gerou, ou seja, cada vértice precisa saber quem é seu pai. Desse modo, o vértice que corresponde ao estado objetivo aponta para o vértice que o gerou, e este, por sua vez, apontará para outro vértice, e por aí vai, até chegar ao vértice que apontará para o vértice inicial. Então poderemos percorrer o caminho encontrado pelo algorítimo de trás pra frente.
O critério utilizado no algoritmo para escolher qual dentre os nós folha será o próximo a ser expandido é basicamente o que vai determinar o tipo de algoritmo de busca. Neste texto vamos analisar um algoritmo genérico de busca em espaço de estados e entender como a partir dele podemos implementar o algoritmo de busca em largura (breadth-first search) e o de busca em profundidade (depth-first search). Boa parte dos algoritmos mais complexos de busca consiste em variações desses algoritmos mais simples.
Algoritmo genérico de busca em espaço de estados
Com o que você já entendeu sobre busca e grafos, podemos formular nosso primeiro algoritmo genérico de busca:
função busca_em_espaço_de_estados(estado_inicial, estado_alvo):
vertice_inicial = novo objeto do tipo Vertice
vertice_inicial.estado = estado_inicial
vertice_incial.pai = NULO
vertice_atual = NULO
fronteira = [vertice_inicial,]
visitados = []
enquanto houver elementos na lista fronteira:
remove um elemento da fronteira e armazena seu valor na variável vertice_atual
se vertice_atual.estado == estado_alvo:
retorna vertice_atual
caso contrário:
adiciona vertice_atual à lista visitados
novos_estados = [filhos do estado atual]
para cada novo_estado em novos_estados:
se nenhum elemento de fronteira possui estado igual a novo_estado:
se novo_estado não está na lista visitados:
novo_vertice = novo objeto do tipo Vertice
novo_vertice.estado = estado
novo_vertice.pai = vertice_atual
adiciona novo_vertice à lista fronteira
retorna Falso ;retorna falso apenas se
;o loop for encerrado sem retornar uma solução
Observe que supomos a existência de uma estrutura chamada Vertice, que possui dois atributos: pai, que armazena o vértice que gerou o vértice em questão, e estado, que armazena o estado correspondente a esse vértice. Em alguns casos, pode ser necessário armazenar também a ação que levou ao novo estado.
Também mantemos duas listas: uma é a fronteira, que contém os vértices que ainda não foram visitados, e a outra é a lista visitados, que contém os estados que já foram analisados pelo algoritmo. É essa lista que vai impedir que nosso algoritmo caia em loops infinitos, já que ele não tentará enveredar por um caminho que já foi explorado anteriormente.
Perceba que a lista fronteira armazena objetos do tipo Vertice, enquanto que a lista visitadosarmazena objetos do tipo estado. Como foi explicado anteriormente, os objetos do tipo Vertice possuem tanto as informações do estado quanto do vértice que o gerou, e servirão para que possamos obter a solução do problema (o caminho entre o estado inicial e o estado final) percorrendo o caminho do vértice que contém o estado alvo até o vértice que contém o estado inicial através dos atributos pai de cada vértice.
Por outro lado, para a lista de visitados, o parentesco dos estados não importa, já que essa lista é utilizada apenas para manter o registro dos estados que já foram visitados. Precisamos manter esse registro apenas para evitar que nosso algoritmo caia em loops infinitos.
Além disso, vértices são estruturas complexas que nós mesmos implementamos (em Python, poderíamos, por exemplo, usar uma classe, e em C poderíamos utilizar uma struct), enquanto os estados podem ser de tipos mais simples, como strings ou tuplas, dependendo do problema em questão.
Manter uma lista de estados para armazenar os estados gerados, ao invés de uma lista de vértices, facilita o processo de verificar se determinado estado já foi gerado (avaliar se uma string está inserida numa lista geralmente é mais fácil que avaliar se determinada string está contida no atributo estado de algum dos vértices de uma lista).
(No geral, não é bom misturar teoria com implementação, mas nesse caso, achei importante destacar essa questão, porque você eventualmente vai tentar por em prática o que leu aqui).
Observe também que na linha novos_estados = [filhos do estado atual], criamos uma lista com os estados gerados a partir da aplicação de uma certa ação ao estado atual. Em nível de implementação, precisamos de uma função que receba um estado como argumento e retorne uma lista com os estados resultantes.
Agora, basta descobrir o trajeto do estado objetivo até o inicial. Para isso, podemos implementar uma função simples como a seguinte:
função encontra_caminho(vertice, estado_inicial):
caminho = lista vazia
enquanto vertice.estado != estado_inicial :
insere vertice.estado em caminho
vertice = vertice.pai
caminho = sequência invertida dos elementos de caminho
retorna caminho
Busca em largura e busca em profundidade
Em nosso algoritmo, utilizamos os termos como “remove um vértice da fronteira” e “adiciona um vértice à fronteira”. Mas exatamente em que lugar da lista devemos inserir o novo vértice e de que lugar devemos tirá-los para avaliação? A resposta para essa pergunta é justamente o que vai definir se nosso algoritmo de busca terá um comportamento de busca em largura ou busca em profundidade.
Primeiro, vamos definir que os novos vértices são inseridos ao final da lista fronteira. Então, quando formos remover um vértice da fronteira, temos duas escolhas: removemos o vértice do início da lista, ou do final. Isso resume-se a escolher se o funcionamento da nossa fronteira é uma pilha ou uma fila.
Afinal, como estabelecemos que sempre adicionamos os novos elementos ao final da lista, se retiramos os elementos do começo, então temos uma fila: pois os vértices que foram adicionados primeiro são removidos primeiro. Se retiramos os elementos do final da lista, então temos um comportamento de pilha: os elementos inseridos por último são removidos primeiro.
Se implementarmos nosso algoritmo de modo que a fronteira se comporte como uma fila (vértices gerados primeiro são avaliados primeiro), então nosso algoritmo realiza uma busca em largura (breadth-first search). Pois os nós mais próximos do estado inicial são sempre avaliados antes dos nós mais distantes.
Analogamente, se definimos de antemão que os novos nós serão inseridos no início da lista, se escolhermos expandir sempre o primeiro nó da lista, teremos o comportamento de pilha, e se escolhermos expandir sempre o último, teremos um comportamento de fila.
(Caso você tenha curiosidade e algum conhecimento da linguagem C, pode dar uma olhada nos posts que eu fiz ensinando a implementar pilhas e filas).
Por outro lado, se nosso algoritmo consome os itens da fronteira como uma pilha, então realizamos uma busca em profundidade (depth-first search), porque o algoritmo sempre avalia o nó mais recentemente inserido na fronteira, e esse nó, por sua vez, gerará outros nós, que serão consumidos antes dos nós anteriores e por aí vai. Entãoa cada iteraçãodo nosso algoritmo, ele se aprofunda cada vez mais no espaço de estados se afastando do nó inicial.
Esses comportamentos diferentes têm muitas implicações práticas. Em especial, como a busca em largura analisa todos os estados mais próximos do estado inicial antes de partir para os estados mais distantes, ela garante encontrar sempre o caminho mais curto até a solução. A busca em profundidade, por outro lado, pode encontrar um caminho subótimo e, além disso, se o espaço de estados for infinito, ela pode nunca encontrar a solução (se começar indo na direção errada).
Pode parecer que a busca em profundidade não oferece muitas vantagens, e, de fato, essa implementação fica para trás quando comparada à busca em largura. Porém, se modificarmos o algoritmo de modo a armazenar apenas os nós da fronteira e os que se encontram no caminho do estado inicial ao estado atual (ao invés de armazenar todos os nós já visitados mais a fronteira) continuamos garantindo que o algoritmo não fique preso em loops, ao mesmo tempo que economizamos memória.
Para isso, basta verificar, a cada nó gerado, se seu estado correspondente já se encontra no caminho percorrido do estado inicial até o estado atual e descartá-lo em caso positivo. Isso não seria possível num algoritmo de busca em largura, já que enquanto a busca em profundidade foca em um possível caminho de cada vez, recuando caso esse caminho dê em um beco sem saída, a busca em largura segue expandindo os nós mais antigos na fronteira primeiro, armazenando, enquanto isso, os caminhos do estado inicial para cada nó da fronteira, até descobrir qual desses caminhos leva efetivamente ao estado objetivo.
Em espaços de estados com um elevado fator de ramificação (a quantidade máxima de novos nós gerados a partir da expansão de um nó) e em que o estado objetivo mais próximo do estado inicial se encontra numa profundidade considerável na árvore de busca, a economia em termos de memória obtida por essa modificação é muito significante, já que na implementação tradicional desses algoritmos, o número de nós armazenado na memória aumenta exponencialmente em função da profundidade da solução.
Por exemplo, se temos um problema em que cada nó expandido produz mais quatro nós filhos, então ao expandirmos o nó referente ao estado inicial, teremos 1 nó na lista de visitados e 4 na fronteira (profundidade = 1). Depois de expandirmos todos esses quatro filhos do nó inicial, teremos 1 + 4 nós visitados + 4 x 4 na fronteira (profundidade = 2). Depois de expandirmos os “netos” do filho inicial, teremos então 1 + 4 + 4 x 4 nós visitados + 4 x 4 x 4 na fronteira (profundidade = 3).
Daí se pode perceber que ao expandirmos as gerações de nós até uma certa profundidade n, o total de nós gerados será 41 + 42 + … 4n.
Enquanto isso, armazenando apenas os nós da fronteira e o caminho até do nó inicial até um nó na profundidade n, teremos apenas 4 x n em memória.
Além disso, existe uma variação recursiva do algoritmo de busca em profundidade muito mais poderosa, chamada de backtracking search, que estudaremos em outro post e que é utilizada, por exemplo, para implementar a avaliação de consultas em Prolog.
Busca uniforme
É importante notar que existem problemas em que os caminhos entre um estado e outro envolvem custos diferentes (no caso do espaço de estados da região metropolitana de Salvador, diferentes caminhos para uma mesma cidade envolveriam diferentes distâncias, por exemplo). Nesse caso, um algoritmo simples de busca em largura não seria suficiente para encontrar o melhor caminho. Para isso, precisaríamos modificar nosso algoritmo básico de modo a implementar um algoritmo de busca de custo uniforme.
Busca cega e heurística
Um último conceito importante: os dois algoritmos que estudamos nesse post são chamados de algoritmos de busca cega ou desinformada, ou ainda de algoritmos de força bruta, pois eles buscam alcançar um estado objetivo sem a menor ideia de onde ele possa estar, testando uma possibilidade por vez. Por outro lado, algoritmos informados, como melhor-primeiro (best-first-search) e A* (leia-se A star) utilizam técnicas específicas (chamadas de heurística) para eleger os melhores candidatos para expansão, o que costuma otimizar significativamente a busca por uma solução.
Pretendo abordar esses assuntos em posts futuros, por isso, não deixe de acompanhar o blog!
One thought on “Busca em espaço de estados: algoritmos de busca em largura e profundidade”