Inteligência Artificial

Codificação de problemas de procura em espaços de estados

- algoritmos de procura -

(em Java)

De modo a implementar os algoritmos de procura em espaços de estados de maneira independente do problema concreto que se pretende resolver é necessário esclarecer como deve ser feita a descrição dos problemas e como é que estes irão ser usados pelos algoritmos de procura.

A implementação em Java deve ser estruturada em pacotes que são disponibilizados (pode fazer aqui o download de todos os pacotes) e que deverão ser utilizados nas aulas práticas.

A interface genérica usada para a descrição dos problemas está definida no pacote searchproblem. Os diferentes algoritmos de procura estão implementados no pacote searchalgorithm. O pacote undirectedgraph permite a especificação de um grafo não-direcionado para a representação de problemas de cálculo de rotas em mapas de estradas.

De seguida apresenta-se uma breve descrição do conteúdo de cada um dos pacotes searchproblem, searchalgorithm e undirectedgraph.

1 - Descrição genérica dos problemas (pacote searchproblem)

Para definir um problema de procura em espaço de estados é necessário:

  • Especificar o estado inicial do problema
  • Especificar quais os estados que satisfazem o objectivo do problema
  • Especificar quais as transições possíveis entre estados
  • Especificar um custo para cada possível transição

Os conceitos básicos envolvidos são o estado que caracteriza o problema num determinado momento e o arco que representa uma ligação entre dois estados.

A estrutura de dados usada para a representação de cada arco é implementada pela classe Arc (Arc.java). Cada arco é caracterizado por um estado de origem, um estado de destino, e um valor que representa o custo da transição do estado de origem para o estado de destino.

A estrutura de dados genérica usada para a definição de cada estado é representada pela classe State (State.java). Na definição de um problema de cálculo de rotas em mapas de estradas um estado corresponde a um vértice do grafo (cidade) e um arco corresponde a uma ligação entre dois vértices (estrada) com o respectivo custo em quilómetros. O método successorState devolve um arco que representa uma ligação entre dois vértices. O método successorFunction devolve uma lista de arcos com todas as ligações entre o vértice do estado e outros vértices que lhe estejam ligados no grafo. Os métodos clone, hashCode e equals estão definidos de modo a que os algoritmos de procura funcionem adequadamente (por exemplo, para usar HashMap).

Um problema genérico de procura em espaços de estados é representado pela classe SearchProblem (SearchProblem.java). O problema é caracterizado pelo seu estado inicial e pelo conjunto de estados que satisfazem o objectivo. O método getInitial devolve o estado inicial. O método goalTest verifica se o estado passado por parâmetro satisfaz o objectivo do problema. Toda a informação sobre a transição de estados está implícita nos próprios estados.

Um problema de procura informada num espaço de estados é um problema de procura para o qual se define uma heurística. O método heuristic devolve uma estimativa (heurística) do custo desde o estado do nó passado por parâmetro a um estado que satisfaça o objectivo. A versão implementada devolve a menor distância em linha recta entre a cidade representada pelo nó e uma que satisfaça o objectivo.

2 – Algoritmos de procura (pacote searchalgorithm)

Um algoritmo de procura em espaços de estados lida com nós do espaço de procura. Cada nó contém uma descrição do estado e demais informação necessária para o funcionamento do algoritmo.

Cada nó do espaço de procura deve conter as seguintes informações:

  • Estado corrente
  • Nó antecessor
  • Custo do caminho desde o estado inicial até ao estado corrente
  • Valor da heurística no nó corrente

Na implementação fornecida, um nó do espaço de procura é representado pela classe Node (Node.java) onde, além da informação acima mencionada (excepto a heurística), é acrescentada informação acerca da profundidade a que se encontra o nó no espaço de procura. O método Expand devolve uma lista com todos os nós sucessores do nó. O método getPath devolve a sequência de estados (caminho) usada para chegar ao nó desde o nó inicial.

A classe SearchAlgorithm(SearchAlgorithm.java) é usada para representar um algoritmo genérico de procura e qualquer algoritmo em particular deverá ser implementado como uma sua subclasse que defina os métodos searchSolution e getMetrics. O método searchSolution desencadeia a procura e devolve um nó do espaço de procura com um estado corrente que satisfaça o objectivo do problema. O método getMetrics devolve dados estatísticos relativos à pesquisa efectuada pelo algoritmo.

Os algoritmos implementados estão enumerados em Algorithms (Algorithms.java):

Todos os algoritmos (excepto o de pesquisa em profundidade) usam a classe GraphSearch (GraphSearch.java) que implementa um algoritmo genérico de procura em grafos. A lista dos nós por explorar é representada com o tipo Queue<Node> e a lista dos nós já explorados com o tipo HashMap<Node, Node>. A ideia do algoritmo genérico de procura em grafos é poder ser utilizado com diferentes tipos de heurística e diferentes estratégias de prioridades (para escolher o próximo nó a explorar) de modo a implementar diferentes algoritmos de procura, nomeadamente, procura em largura, procura de custo uniforme, procura sôfrega e procura A*.

3 – Problema do cálculo de rotas (pacote undirectedgraph)

Os algoritmos de procura irão ser utilizados para a resolução de diversos problemas de cálculo de rotas em mapas de estradas. O mapa das estradas, que serve de base a estes problemas é representado por um grafo não-direcionado definido por um conjunto de vértices e ligações entre eles.

Um vértice, implementado pela classe Vertex (Vertex.java), representa uma cidade no mapa. Cada vértice é unicamente identificado pelo nome da cidade e tem associadas as suas coordenadas geográficas. O método getNeighbors permite obter todas as ligações a outros vértices do grafo. O método straightLineDistance permite calcular a distância em linha recta (em quilómetros) entre a cidade representada pelo vértice e qualquer outra cidade passada por parâmetro (o cálculo desta distância é baseado nas coordenadas geográficas de ambas as cidades).

Uma ligação, implementada pela classe Edge (Edge.java), representa uma estrada entre duas cidades. Cada ligação é unicamente identificada pelo par de cidades que liga, o que significa que não podem existir mais do que uma ligação entre as mesmas duas cidades. A cada ligação está associado um peso que representa os quilómetros a percorrer nesta estrada para chegar de uma cidade à outra. O método getNeighbor tem como argumento um vértice que representa uma cidade e, caso seja um dos vértices da ligação, devolve o outro vértice que representa a cidade ligada por esta estrada.

A classe VertexSet (VertexSet.java) permite agrupar conjuntos de vértices (cidades) para representar regiões (províncias) no mapa. Cada região é unicamente identificada por um nome.

O mapa com as cidades e a rede de estradas que servirá de base aos problemas de cálculo de rotas é representado pela classe Graph (Graph.java). Oferece métodos para: acrescentar uma cidade com as respectivas coordenadas geográficas (addVertice), acrescentar uma ligação entre duas cidades (addEdge) e, agrupar cidades em regiões (addVerticeSet e addVerticeToSet). De notar que para acrescentar uma nova ligação, o método addEdge pode ser evocado com três argumentos em que, além das cidades, se explicita também os quilómetros da ligação, ou apenas com dois, onde se assume que os quilómetros da ligação correspondem à distância em linha recta entre as cidades.

Por fim, a classe Romenia (Romenia.java) fornece um método defineGraph que permite a definição automática do mapa da Roménia, com as suas cidades mais importantes, estradas e regiões. Para facilitar assume-se que os quilómetros de cada ligação no mapa correspondem à distância em linha recta entre as cidades ligadas. Os métodos showLinks e showSets podem ser usados para mostrar respectivamente, as ligações com a distância (em quilómetros) entre cada uma das cidades e os agrupamentos de cidades em regiões. A figura seguinte ilustra o mapa definido:

 

Para calcular uma rota entre uma cidade de origem e uma cidade de destino deve ser usado o método searchSolution que permite a especificação do algoritmo de procura que será utilizado. Este método devolve um nó do espaço de procura com um estado corrente que corresponde à cidade destino. Adicionalmente o método acumula alguns dados estatísticos relativos à pesquisa efectuada pelo algoritmo. Uma chamada do método showSolution com este nó como argumento permite a visualização da solução e dos dados estatísticos da pesquisa.