A Vida Secreta dos Grafos
Este capítulo focará em um conceito abstrato matemático muito útil chamado grafo. Você usará
muitos grafos na IA de jogos. Na verdade você já os viu: Os diagramas de transição de estado do Capítulo
2 são um tipo de grafo. Os grafos e suas irmãs caçulas, as árvores, são usadas pelos programadores de IA
para jogos o tempo todo. Eles podem ser usados para uma grande variedade de coisas – de permitir que
agentes de jogo viajem entre dois pontos eficientemente, decidir o que construir a seguir em jogos de
estratégia e resolver puzzles.
A primeira parte deste capítulo será gasta introduzindo você aos diferentes tipos de grafos e a
terminologia associada com eles. Você aprenderá o que os grafos realmente são, como eles podem ser
usados e como codificá-los eficientemente. O resto do capítulo descreverá com muitos detalhes, várias
das técnicas de algoritmos de procura disponíveis para fazer bom uso de todo o poder dos grafos.
1. Grafos
Quando desenvolvendo IA para jogos, um dos usos dos grafos mais comum é para representar
redes de caminhos que um agente pode usar para navegar pelo ambiente. Quando eu aprendi isto, eu
fiquei confuso, pois em toda minha vida em sabia que um grafo parecia como que eu desenhava na escola
– algo como a forma familiar mostrada na Figura 5.1, por exemplo.
Figura 5.1: Um típico grafo
Eu sempre achava que grafos eram úteis para visualizar as subidas e descidas de alguma
propriedade, como a temperatura mostrada pelos repórteres meteorológicos na TV ou representações de
vendas, coisas como isso, e assim eu fiquei maravilhado com como este tipo de grafo pode ser usado para
representar caminhos ao redor de muros e obstáculos em um ambiente de jogo. Se você nunca estudou a
teoria dos grafos, então esta possivelmente pode ser a maneira como você os vê também. Eu achava que
eles eram úteis apenas para uma coisa. Entretanto, deixe-me mostrar a você algo interessante. Veja a
figura 5.2.
Figura 5.2
Este é o mesmo grafo, mas eu mudei as marcas dos eixos para representar as coordenadas x e y de
um espaço Cartesiano, adicionando alguns embelezamentos cosméticos para que agora ele represente um
caminho próximo a um rio. De fato, muitas pessoas na rua chamariam ele de mapa. Certamente, a
imagem inteira é um mapa, mas a série de pontos e o percurso os conectando é representado por um grafo
muito simples. Eu acho que alguns de vocês devem estar pensando que isto não é uma grande coisa, mas
eu acredito que para muitos esta mudança súbita de perspectiva possa ser reveladora. Ela certamente foi
para mim. Na terminologia dos grafos, os pontos são chamados de nodos (ou algumas vezes vetores) e os
percursos conectando-os são chamados de arestas (ou algumas vezes arcos).
A Figura 5.3 mostra alguns exemplos de grafos. Como você pode ver, eles podem assumir uma
grande variedade de configurações.
Figura 5.3: Exemplos de grafos
Em um contexto mais amplo, um grafo é uma representação simbólica de uma rede, e algumas
vezes as arestas podem representar um relacionamento espacial, como no exemplo discutido antes, mas
nem sempre isto é o caso. Os grafos são usados para representar redes de qualquer espécie, redes de
telefones, a World Wide Web, circuitos eletrônicos e redes neurais artificiais.
Nota Os grafos podem ser conectados ou desconectados. Um grafo é considerado conectado quando é
possível de se traçar um percurso de cada nodo a todos os outros.
Os grafos A, B, D e E na Figura 5.3 são exemplos de grafos conectados. Os grafos C e F são
exemplos de grafos desconectados.
1.1 Uma descrição mais formal
Um grafo G, pode ser formalmente como um conjunto de nodos ou vértices N, conectados por um
conjunto de arestas E. Você verá frequêntemente isto escrito como:
(5.1)
Se cada nodo em um grafo é etiquetado com um inteiro de 0 até (N-1), uma aresta pode agora ser
referenciada pelos nodos que conecta, por exemplo, 3-5 ou 19-7.
Muitos grafos possuem arestas com pesos – elas contêm informação sobre o custo de se mover de
um nodo ao outro. Por exemplo, no grafo mostrado na Figura 5.2, o custo de se atravessar uma aresta é a
distância entre os dois nodos que ela conecta. Em um gráfico que representa uma árvore de tecnologias
em jogos RTS como Warcraft, as arestas podem indicar os recursos necessários para se melhorar cada
unidade.
Nota Embora um grafo possa ter múltiplas conexões entre dois nodos ou conexões em laço em um único
nodo, essas funções são raramente necessárias em IA para jogos e não serão consideradas nas
próximas páginas.
1.2 Árvores
A maioria dos programadores são conhecedores da estrutura de dados em árvore. As árvores são
profundamente utilizadas por todas as disciplinas de programação. Entretanto, você pode não entender
que as árvores são um subconjunto dos grafos compreendendo todos os grafos acíclicos (os que não
contém nenhum caminho cíclico). O grafo E na Figura 5.3 é uma árvore, e provavelmente é a forma com
que você está familiarizado, mas o grafo D também é uma árvore. O grafo F é uma floresta de árvores.
1.3 Densidade dos grafos
A relação de arestas para nodos em um grafo é esparsa ou densa. Grafos esparsos possuem poucas
conexões por nodo e os grafos densos possuem muitas. A Figura 5.4 mostra um exemplo de ambos os
tipos. Em ordem de reduzir a complexidade e manter os usos de CPU e memória no mínimo, você deve
preferir gráficos esparsos sempre que possível, por exemplo, quando projetar um grafo para usar no
planejamento de percurso (veja o Capítulo 8).
Figura 5.4: Exemplos de grafos denso e esparso
Saber quando um grafo é denso ou esparso é útil quando se seleciona uma estrutura de dados
apropriada para codificar a estrutura do grafo, já que uma implementação que é eficiente para grafos
densos, provavelmente não será eficiente para um que é esparso.
1.4 Digrafos
Em geral quando assumimos que é possível viajar do nodo A para o nodo B, então também é
possível se fazer o inverso. Mas isso nem sempre será o caso. Algumas vezes você precisará implementar
grafos onde as conexões são direcionais. Por exemplo, seu jogo pode ter um “tobogã” posicionado entre
as margens de um rio. Um agente pode ser capaz de atravessar ele só de uma maneira – de cima para
baixo – então você terá que encontrar uma maneira de representar este tipo de conexão.
Alternativamente, pode ser possível se viajar entre dois nodos em ambas as direção, mas o custo
de cada percurso pode ser diferente. Um bom exemplo disso é se você deseja que seus agentes levem em
consideração as inclinações do terreno. Afinal, é fácil para um veículo viajar eficientemente e
rapidamente ladeira abaixo, mas ele gasta muito mais combustível para subir a ladeira, além de sua
velocidade máxima ficar muito mais lenta. Nós podemos refletir esta informação usando um gráfico
chamado digrafo, ou DAG para abreviar.
Um digrafo possui arestas que são direcionadas, ou caminhos. Os nodos que definem uma aresta
direcionada são conhecidos como um par ordenado e especificam a direção da aresta. Por exemplo, o par
ordenado 16-6 indica que é possível se viajar do nodo 16 para o nodo 6, mas não do nodo 6 para o 16.
Neste exemplo, o nodo 16 é conhecido como o nodo fonte e o nodo 6 o nodo destino.
A Figura 5.5 mostra um pequeno digrafo. As arestas são desenhadas usando setas para indicar
suas direções.
Figura 5.5: Um simples digrafo. Note que no mundo dos digrafos, grafos não-direcionados são mais frequêntes que os
direcionados.
Quando projetar uma estrutura de dados para grafos é frequêntemente útil pensar em grafos nãodirecionados como digrafos com duas arestas conectando cada par conectado de nodos. Isto é
conveniente, pois ambos os tipos de grafos (direcionados e não-direcionados) podem ser representados
pela mesma estrutura de dados. Por exemplo, o grafo não-direcionado esparso mostrado na Figura 5.4
pode ser representado pelo digrafo mostrado na Figura 5.6.
Figura 5.6: Representação de um grafo não-direcionado como um dígrafo
1.5 Grafos em IA de Jogos
Antes de vermos a implementação do código para um grafo, vamos dar uma olhada nas coisas que
você pode usar grafos no desenvolvimento da IA de um jogo, começando com o uso mais popular: a
navegação ou pathfinding.
1.5.1 Grafos de Navegação
Um grafo de navegação ou navgraph, é uma abstração de todas as localizações em um ambiente
de jogo que os agentes do jogo podem visitar e de todas as conexões entre estes pontos.
Consequentemente, um navgraph bem-projetado é uma estrutura de dados que incorpora todos os
percursos possíveis através do ambiente do jogo e é, portanto, extremamente útil para ajudar os seus
agentes de jogo a decidirem como ir de A até B.
Cada nodo em um navgraph usualmente representa a posição de uma área chave ou objeto dentro
do ambiente e cada aresta representa as conexões entre esses pontos. Além disso, cada aresta terá a ela
associado um custo, que no caso mais simples representa a distância entre os nodos que ela conecta. Este
tipo de grafo é conhecido pelos matemáticos como grafo Euclidiano. A Figura 5.7 mostra um grafo de
navegação criado para um pequeno ambiente com paredes e um caminho realçado através desse grafo.
Figura 5.7: Um grafo de navegação simples. A coleção de todas as arestas e nodos constitui o grafo. As arestas realçadas
representam um caminho possível através do grafo.
Eu gostaria de deixar claro que um agente de jogo não é restringido a se mover apenas nas arestas
do grafo, como um trem viajando ao longo dos trilhos. Um agente pode se mover para qualquer posição
desobstruída dentro do ambiente do jogo, mas ele usa o grafo de navegação para negociar seu ambiente para planejar os caminhos entre dois ou mais pontos e para atravessar eles. Por exemplo, se um agente
posicionado em ponto A acha necessário se mover para a posição B, ele pode usar o navgraph para
calcular a melhor rota entre os nodos mais próximos para estes pontos.
A Figura 5.7 é um típico grafo de navegação criado para um jogo de tiro em primeira pessoa.
Outros tipos de jogos podem achar uma configuração de nodos diferente mais efetiva. Os jogos do tipo
RTS/RPG, por exemplo, são frequentemente baseados sobre uma grade de tiles ou células, onde cada tile
representa um tipo diferente de terreno, tal como grama, estrada, lama, etc. Portanto, é conveniente se
criar um grafo usando o ponto central de cada tile e designando custos de arestas baseados na distância
entre as células e o peso do tipo de terreno em que a aresta atravessará. Esta abordagem permite agentes
de jogo facilmente calcularem caminhos que evitem água, prefiram viajar em estradas invés de lama e
circularem montanhas. A Figura 5.8 mostra a espécie de configuração de células que você pode ver em
um RTS/RPG.
Figura 5.8: Um típico ambiente baseado em células. Embora não mostrados por claridade, os nodos do grafo são
posicionados nos centros das células, com as arestas conectando os nodos adjacentes. A demonstração PathFinder deste
capítulo usa este tipo de navgraph.
Por causa de alguns jogos de RTS/RPG poderem usar literalmente centenas de milhares de
células, a desvantagem desta abordagem é que os grafos podem ficar extremamente dispendiosos,
demorados de pesquisar e tomarem grandes quantias de memória. Felizmente para os desenvolvedores de
IA, alguns destes problemas podem ser evitados se usando técnicas que você aprenderá mais tarde neste
livro.
Dica Se você está criando um jogo "mantenha-se nas sombras", como Thief e Thief 2 da Looking Glass
Studios/Eidos Interactive, você pode usar um navgraph que tem suas arestas com pesos baseados
em quanto som um personagem pode fazer ao atravessá-la. As arestas que são silenciosas de serem
atravessadas como as ao longo de um tapete podem ter pesos baixos, e as arestas barulhentas podem
ter valores altos. Projetar seus grafos desta maneira permite que os personagens de seu jogo
encontrem o caminho mais silencioso entre duas salas.
1.5.2 Grafos de Dependências
Os grafos de dependência são utilizados em tipos de jogos de administração de recursos para
descrever as dependências entre as várias construções, materiais, unidades e tecnologias disponíveis para
um jogador. A Figura 5.9 mostra a parte de um grafo de dependência criado para um jogo desses. Esta
espécie de grafo torna fácil ver quais pré-requisitos são necessários para a criação de cada tipo de recurso.
Os grafos de dependência são inestimáveis quando se projeta uma IA para este tipo de gênero, pois a IA
pode usar eles para decidir estratégias, prever a condição futura de um adversário e administrar os
recursos efetivamente. Aqui estão alguns exemplos baseados no grafo mostrado na figura.
Figura 5.9: Um simples grafo de dependências
1. Se a IA está se preparando para uma batalha e conclui que arqueiros darão vantagem, ela pode
examinar o grafo de dependência para concluir que antes dela poder produzir arqueiros, ela deve
primeiro garantir que tem um quartel e a tecnologia de flechas. Com isso ela também sabe que
para produzir flechas ela deve ter uma serralheria produzindo madeira. Portanto, se a IA já tem
uma serralheria, ela pode administrar seus recursos para construir um quartel ou vice-versa. Se a
IA não tem nem o quartel, nem uma serralheria, ela pode inspecionar o grafo de tecnologia para
determinar se é vantajoso construir o quartel antes da serralheria. Por quê? Porque o quartel é um
pré-requisito para três espécies diferentes de unidade de batalha, ao passo que uma serralheria é
unicamente um pré-requisito para produzir madeira. A IA já determinou que uma batalha é
iminente, assim ele deve compreender (se você a projetou corretamente, é claro) que deve gastar
seus recursos na fabricação de unidades de batalha tão logo quanto possível, pois como todos nós
sabemos, cavaleiros e soldados são guerreiros melhores que pilhas de madeira!
2. Se um soldado inimigo carregando uma arma entra no território da IA, a IA pode trabalhar para
trás no grafo para concluir que:
• O inimigo já deve ter construído uma forja e uma serralheria;
• O inimigo já deve ter desenvolvido a tecnologia de pólvora;
• O inimigo já deve estar produzindo recursos de madeira e ferro.
Além disso, o exame do grafo pode indicar que o inimigo provavelmente já tem um ou outro
canhão ou está os construindo. Droga!
A IA pode usar esta informação para decidir o melhor plano de ataque. Por exemplo, a IA pode
saber que para prevenir quaisquer inimigos carregadores de armas de alcançar seu território, ela
deve focar a forja e a serralheria do inimigo. Ela também pode enviar um assassino para matar o
ferreiro do inimigo, e assim o enfraquecer consideravelmente, e talvez dedique seus recursos para
criar um assassino para este propósito.
3. Frequentemente, uma tecnologia ou unidade específica é a chave para a vitória da equipe em um
jogo. Se os custos de construção de cada recurso são designados pelas arestas do grafo de
dependências, então a IA pode usar esta informação para calcular a rota mais eficiente para
produzir esse recurso.
1.5.3 Grafos de Estados
Um grafo de estados é uma representação de todos os estado possíveis que um sistema pode ter e
as transições entre esses estados. Esta coleção de estados em potencial de um sistema é conhecida como o
espaço dos estados. Um grafo deste tipo pode ser pesquisado para ver se um estado em particular é
possível ou para encontrar a rota mais eficiente para um estado específico.
Vamos ver um simples exemplo usando o puzzle "Torres de Hanoi".
Figura 5.10: O Torres de Hanoi
Nesta versão simples do puzzle há três pinos - A, B e C - e três argolas de tamanhos diferentes que
se encaixam em cima dos pinos. As argolas começam posicionadas em ordem de tamanho em cima do
pino A. O objetivo do puzzle é mover as argolas até que todas elas fiquem posicionadas no pino C,
também em ordem de tamanho. Apenas uma argola pode ser movida de cada vez. Uma argola pode ser
colocada tanto em outro pino vazio ou em cima de outra argola que é maior que a mesma.
Nós podemos representar o espaço dos estados deste puzzle usando um grafo onde cada nodo
representa um dos estados possíveis que o puzzle pode ocupar. As arestas do grafo representam as
transições entre os estados: Se é possível se mover diretamente de um estado para outro, então haverá
uma aresta conectando os dois estados; se não, não haverá nenhuma conexão. O grafo é construído
primeiro pela criação de um nodo que contém o estado inicial do puzzle. Este é conhecido como o nodo
raiz. O nodo raiz é então expandido pela adição de todos os estados obteníveis a partir dele no grafo, logo
então, cada um desses estados é expandido, e assim em diante, até que todos os estados e transições
possíveis tenham sido adicionados no grafo. Cada estado anterior a outro, é chamado de estado pai, o
novo estado é chamado de filho do estado pai.
A Figura 5.11 mostra este processo. Uma seta conectando dois estados significa que um estado
pode ser alcançado a partir do outro ao se mover as argolas. O grafo fica complicado rapidamente, assim
eu omiti muitos dos estados possíveis para tornar mais fácil de ver um dos caminhos que conduz para
uma solução.
Figura 5.11: Expansão dos estados para o puzzle das Torres de Hanoi. As caixas pontilhadas indicam os estados que não
foram expandidos.
Um grafo de estados pode ser facilmente pesquisado para se encontrar um estado final. Neste
exemplo, o estado final é um onde todas as peças estão posicionadas no pino C na ordem correta. Ao se
pesquisar o espaço dos estados é possível não apenas se encontrar uma única solução, mas se encontrar
todas as soluções possíveis ou a solução que requer menos movimentos (ou a que requer mais
movimentos se é o que você está procurando).
O número médio de nodos filhos irradiando de cada nodo pai é conhecido como fator de expansão
(branching factor) de um grafo. Para alguns problemas, tal como o exemplo de puzzle que discutimos
aqui, o fator de expansão é baixo - na ordem de um a três galhos por nodo – tornando possível de se
representar o espaço dos estados inteiro do grafo em uma memória de computador. Porém em outros
casos, o fator de expansão é muito mais alto e o número de estados em potencial cresce enormemente,
assim como a distância do nodo raiz (a profundidade do gráfico) aumenta. Com esses tipos de sistemas é
impossível se representar o espaço dos estados inteiramente, pois este rapidamente excederá as
capacidades de memória até mesmo do computador mais poderoso. Mesmo que o grafo possa ser
armazenado, este poderia tomar ainda eternidades para se fazer uma pesquisa. Consequentemente, esses
tipos de grafos são criados e pesquisados ao se expandir só alguns nodos de cada vez, tipicamente (mas
nem sempre) usando algoritmos que direcionam a pesquisa ao estado final.
2. Criação de uma Classe para Grafos
As duas estruturas de dados mais populares utilizadas para representar os grafos são as matrizes de
adjacência e as listas de adjacência. Os grafos de matriz de adjacência usam uma matriz bidimensional de
Booleanos ou floats para armazenar a informação da conectividade de um grafo. Os Booleanos são
utilizados se não há custo associado ao se atravessar uma aresta, já os floats são utilizadas quando há um
custo associado, tal como em um gráfico de navegação onde cada aresta representa a distância entre dois
nodos. A implementação exata, certamente, depende do projetista e das necessidades de seu problema. A
Figura 5.12 mostra o que parece a matriz de adjacência do dígrafo na Figura 5.6.
Figura 5.12: Uma matriz de adjacência
Cada "1" representa uma conexão entre dois nodos, cada "0" representa a falta de uma conexão.
Pela leitura dos valores diretamente da matriz da Figura 5.12, nós sabemos que não há conexão do nodo 2
com o 6, mas há uma aresta conectando 4 com 2.
As matrizes de adjacência são intuitivas, mas para grandes grafos esparsos este tipo de
representação é ineficiente, pois a maior parte da matriz é utilizada para armazenar valores desnecessários
zero. Uma estrutura de dados muito melhor para grafos esparsos (a mais utilizada em grafos de IA de
jogos) é a lista de adjacência.
Para cada nodo presente, um grafo de lista de adjacência armazena uma lista encadeada com todas
as arestas adjacentes. A Figura 5.13 mostra como isto funciona no exemplo prévio.
Figura 5.13: Uma lista de adjacência representando o digrafo da Figura 5.6
As listas de adjacência são eficientes para armazenar grafos esparsos, pois elas não desperdiçam
espaço armazenando conexões nulas. A quantia de espaço requerido para armazenar um grafo usando este
tipo de estrutura de dados é proporcional a N + A (número de nodos + número de arestas), ao passo que
para uma matriz de adjacência isto é proporcional a N2 (número de nodos ao quadrado).
Como a maioria dos grafos que você encontrará no desenvolvimento da IA de jogos são esparsos,
uma lista de adjacência frequentemente será a estrutura de dados da sua escolha. Com isto em mente,
vamos ver o código fonte necessário para implementar um grafo.
2.1 A Classe GraphNode
A GraphNode encapsula a informação mínima que um nodo requer para uma representação de
grafo com lista de adjacência: um único número de identificação ou índice.
Aqui está a declaração da classe dos nodos do grafo:
class GraphNode
{
protected:
//every node has an index. A valid index is >= 0
int
m_iIndex;
public:
GraphNode():m_iIndex(invalid_node_index){}
GraphNode(int idx):m_iIndex(idx){}
virtual ~GraphNode(){}
int Index()const;
void SetIndex(int NewIndex);
};
Como frequentemente você precisará que um nodo contenha informações adicionais, a
GraphNode será tipicamente utilizada como uma classe base da qual se derivarão nodos personalizados.
Por exemplo, os nodos de um grafo de navegação devem armazenar informação do espacial, já nodos de
um grafo de dependência devem conter informações sobre o que eles representam.
Uma classe de nodos projetada para ser usada dentro de um grafo de navegação pode parecer algo
como esta:
template < class extra_info = void*>
class NavGraphNode : public GraphNode
{
protected:
//the node's position
Vector2D
m_vPosition;
//often you will require a navgraph node to contain additional information.
//For example a node might represent a pickup such as armor in which
//case m_ExtraInfo could be an enumerated value denoting the pickup type,
//thereby enabling a search algorithm to search a graph for specific items.
//Going one step further, m_ExtraInfo could be a pointer to the instance of
//the item type the node is twinned with. This would allow a search algorithm
//info.
extra_info m_ExtraInfo;
public:
/*INTERFACE OMITTED */
};
Por favor, note que embora a classe de nodos aqui use um vetor 2D para representar a posição de
um nodo, um grafo pode existir em qualquer número de dimensões que você quiser. Se você está criando
um grafo de navegação para um jogo 3D, simplesmente use vetores 3D. Tudo funcionará do mesmo jeito.
2.2 A Classe GraphEdge
A classe GraphEdge encapsula a informação básica requerida para denotar uma conexão entre
dois nodos de um grafo. Aqui o código:
class GraphEdge
{
protected:
//An edge connects two nodes. Valid node indices are always positive.
int
m_iFrom;
int
m_iTo;
//the cost of traversing the edge
double
m_dCost;
public:
//Constructors
GraphEdge(int from, int to, double cost):m_dCost(cost),
m_iFrom(from),
m_iTo(to)
{}
GraphEdge(int from, int to):m_dCost(1.0),
m_iFrom(from),
m_iTo(to)
{}
GraphEdge():m_dCost(1.0),
m_iFrom(invalid_node_index),
m_iTo(invalid_node_index)
{}
Ocasionalmente é útil se poder criar um GraphEdge com ambos ou apenas um dos índices com
um valor "inválido" (negativo). O valor enumerado invalid_node_index encontrado no arquivo
NodeTypeEnumerations.h é utilizado aqui para iniciar os atributos From (nodo fonte) e To (nodo destino)
no construtor padrão.
virtual ~GraphEdge(){}
int
void
From()const;
SetFrom(int NewIndex);
int
void
To()const;
SetTo(int NewIndex);
double Cost()const;
void SetCost(double NewCost);
};
Se você está trabalhando em uma plataforma onde uso de memória é um muito mais importante
que a velocidade de pesquisa em um grafo, você pode obter bons resultados com grafos baseados em
células (ou grafos de igual ou maior densidade) ao não armazenar explicitamente o custo de cada aresta.
Ao invés disso, você pode economizar memória omitindo o campo de custo da classe GraphEdge e
calcular o custo "no vôo" usando uma função de atributos de seus dois nodos adjacentes. Por exemplo, se
o custo da aresta é igual à distância entre os dois nodos, a função poderia ser a distância Euclidiana. Algo
como:
//cost from A to B
cost = Distance(NodeA.Position, NodeB.Position)
Por causa de usualmente haver oito vezes mais arestas que nodos neste tipo de grafo, a economia
de memória pode ser considerável quando grandes números de nodos são envolvidos.
2.3 A Classe SparseGraph
Os nodos e as arestas de grafo são agrupados na classe SparseGraph. Esta é implementada como
uma classe template, habilitando este tipo de grafo de usar qualquer tipo de nodo e aresta apropriado. Os
algoritmos que operam em grafos devem ser capazes de acessar os dados dos nodos e das arestas
rapidamente. Com isto em mente, a classe SparseGraph é projetada de modo que se possa acessar
diretamente os números chave dos índices de cada nodo dentro um vetor de nodos do grafo (m_Nodes) e
um vetor de listas de adjacência de arestas (m_Edges), dando um tempo de pesquisa de O(1). Entretanto,
isto cria um problema quando um nodo é removido do grafo, já que este terá de ser removido do m_Nodes
também, e com isso todo o indexamento para qualquer nodo com índice mais alto pode ser invalidado.
Portanto, ao invés de apagar o nodo do vetor, seu índice é atribuído com o valor enumerado
invalid_node_index, e todo os métodos da SparseGraph tratam este valor como se não haja um nodo
presente.
Aqui está o código da declaração da SparseGraph.
template <class node_type, class edge_type>
class SparseGraph
{
public:
//enable easy client access to the edge and node types used in the graph
typedef edge_type
EdgeType;
typedef node_type
NodeType;
//a few
typedef
typedef
typedef
more useful typedefs
std::vector<node_type>
std::list<edge_type>
std::vector<EdgeList>
NodeVector;
EdgeList;
EdgeListVector;
private:
//the nodes that comprise this graph
NodeVector
m_Nodes;
//a vector of adjacency edge lists. (each node index keys into the
//list of edges associated with that node)
EdgeListVector m_Edges;
//is this a directed graph?
bool
m_bDigraph;
//the index of the next node to be added
int
m_iNextNodeIndex;
/* EXTRANEOUS DETAIL OMITTED */
public:
//Constructor
SparseGraph(bool digraph): m_iNextNodeIndex(0), m_bDigraph(digraph){}
//returns the node at the given index
const NodeType& GetNode(int idx)const;
//non-const version
NodeType& GetNode(int idx);
//const method for obtaining a reference to an edge
const EdgeType& GetEdge(int from, int to)const;
//non const version
EdgeType& GetEdge(int from, int to);
//retrieves the next free node index
int
GetNextFreeNodeIndex()const;
//adds a node to the graph and returns its index
int
AddNode(NodeType node);
//removes a node by setting its index to invalid_node_index
void RemoveNode(int node);
//methods to add and remove edges
void AddEdge(EdgeType edge);
void RemoveEdge(int from, int to);
Note como a classe tem métodos para remover nodos e arestas. Isto é um recurso necessário se seu
grafo é dinâmico e tem a capacidade de mudar como o progresso do jogo. Por exemplo, é fácil de
representar uma fenda na terra causada por um terremoto ao se remover (e às vezes ao se adicionar)
arestas em um grafo de navegação. Alternativamente, um jogo parecido com Command & Conquer pode
adicionar e remover arestas quando os jogadores constroem ou destroem pontes e muros.
//returns the number of active + inactive nodes present in the graph
int
NumNodes()const;
//returns the number of active nodes present in the graph
int
NumActiveNodes()const;
//returns the number of edges present in the graph
int
NumEdges()const;
//returns true if the graph is directed
bool isDigraph()const;
//returns true if the graph contains no nodes
bool isEmpty()const;
//returns true if a node with the given index is present in the graph
bool isPresent(int nd)const;
//methods for loading and saving graphs from an open file stream or from
//a filename
bool Save(const char* FileName)const;
bool Save(std::ofstream& stream)const;
bool Load(const char* FileName);
bool Load(std::ifstream& stream);
//clears the graph ready for new node insertions
void Clear();
//iterators clients may use to access nodes and edges
class ConstEdgeIterator;
class EdgeIterator;
class NodeIterator;
class ConstNodeIterator;
};
A partir da informação nesta seção, você aprendeu que os grafos são ferramentas poderosas para
você ter a sua disposição. Entretanto, a estrutura de dados de grafo só possui alguns poucos usos. Muito
do poder dos grafos é apenas compreendido quando eles são operados por algoritmos projetados para
explorá-los, ou para encontrar um nodo específico ou para encontrar um caminho entre nodos. O resto
deste capítulo é dedicado a um estudo de vários desses algoritmos.
3. Algoritmos de Procura em Grafos
A teoria dos garfos foi uma área de estudo popular entre matemáticos por muitos anos e
numerosos algoritmos foram desenvolvidos para procura e exploração da topologia de um grafo. Além de
outras coisas, ao se usar algoritmos de procura é possível:
• Visitar cada nodo em um grafo, mapeando efetivamente a topologia do grafo;
• Encontrar qualquer caminho entre dois nodos. Isto é útil se você quiser encontrar um nodo, mas
não se importa em como você chega lá. Por exemplo, este tipo de procura pode se usado para
encontrar uma (ou mais) solução do puzzle das Torres de Hanoi;
• Encontrar o melhor caminho entre dois nodos. O que é “melhor” depende do problema. Se o grafo
a ser pesquisado é uma grafo de navegação, o melhor caminho pode ser, o caminho mais curto
entre os dois nodos, o caminho que permita o agente percorrer os dois pontos no tempo mais
rápido, o caminho que evita a linha de visão dos inimigos ou o caminho mais silencioso (à la
Thief). Se o grafo é um grafo de estados como o do puzzle das Torres de Hanoi, então o melhor
caminho será o que chega à solução em menos etapas.
Antes de ir as vias de fato, eu gostaria de tornar claro que muitos de vocês inicialmente irão achar
alguns desses algoritmos difíceis de entender. De fato, eu acho que os algoritmos de procura em grafos
deveriam vir com uma advertência de risco a saúde. Algo como o seguinte poderia ser apropriado:
Atenção Tome cuidado! Algoritmos de procura têm a capacidade de criar nos cérebros humanos médios
terríveis quantidades de frustração e confusão, levando a dor de cabeça, náusea e falta de sono.
Gemidos espontâneos e excessivos não são incomuns. Por favor, fique atento a esses sintomas,
eles são comuns nos primeiros estágios da curva de aprendizado e geralmente não são
relevantes. A normalidade em geral retorna dentro de um período de tempo razoável.
(Entretanto, se os sintomas persistirem, fique longe de estradas movimentadas, lâminas afiadas e
armas carregadas. Procure assistência médica na primeira oportunidade).
Falando sério, para muitas pessoas esta coisa pode ser difícil de compreender. Para essa razão eu
vou tomar meu tempo explicando cada algoritmo. É muito importante que você compreende a teoria e não
apenas use técnicas como "recorta e cola", pois frequentemente você pode desejar modificar um
algoritmo para ele se encaixar em seus próprios requisitos. Sem uma compreensão de como essas
pesquisas funcionam, qualquer modificação será quase impossível e você começara a arranhar sua cabeça
em frustração.
Peque um banco e sente-se. Vamos dar continuidade a isto!
3.1 Procuras em Grafos Não-Informadas
Procuras em grafos não-informadas, ou procuras cegas como elas são às vezes chamadas,
pesquisam um grafo sem considerar quaisquer custos de arestas associados. Elas podem distinguir nodos
individuais e arestas, entretanto, habilitando elas a identificar um nodo final ou reconhecer um nodo ou
aresta visitada anteriormente. Esta é a única informação requerida para elas explorarem completamente
um grafo (para visitar todos os nodos) ou encontrar um caminho entre dois nodos.
3.1.1 Procura em Profundidade (Depth First Search)
Conheça o pequeno Billy. Billy está na entrada de um típico parque de diversões temático: uma
aglomeração de brinquedos e outras atrações com caminhos sinuosos através do parque conectando elas.
Billy não têm um mapa, mas ele está ansioso para descobrir o que os brinquedos e os outros
entretenimentos do parque oferecem.
Felizmente, Billy conhece a teoria dos grafos e rapidamente percebe a similaridade entre a
aparência do parque temático e um grafo. Ele vê que cada atração pode ser representada por um nodo e os
caminhos entre elas por arestas. Sabendo isso, Billy pode garantir que vai visitar cada atração e caminhar
por cada caminho usando um algoritmo de procura chamado procura em profundidade ou DFS (depth
first search) para abreviar.
A procura em profundidade é chamada assim, pois ela faz a procura indo tão profundo no grafo
quanto for possível. Quando ela bate em um beco sem saída ela volta a um nodo mais raso onde possa
continuar a exploração. Usando o parque temático como um exemplo, é assim que este algoritmo
funciona:
Na entrada do parque (o nodo raiz), Billy toma uma nota de sua descrição e dos caminhos que se
estendem a partir dela (as arestas) em uma folha de papel. A seguir, ele escolhe um dos caminhos para
descer. Ele não faz nenhuma distinção de qual - ele pode escolher um aleatoriamente, desde que não seja
um caminho que ele já explorou. Toda vez que um caminho conduz Billy a uma nova atração ele toma
uma nota de seu nome e dos caminhos que conectam ela. As ilustrações de A a D na Figura 5.14
demonstram os primeiros passos deste processo. As linhas pretas finas representam os caminhos
inexplorados e as linhas realçadas mostram os caminhos que Billy escolheu descer.
Figura 5.14
Quando ele chega na posição mostrada em D, Billy nota que não há nenhum novo caminho saindo
do Pirate Ship (na terminologia dos grafos, este nodo é conhecido como um nodo terminal). Entretanto,
para continuar a procura ele volta ao 3D Cinema onde há mais caminhos inexplorados para percorrer.
Veja a Figura 5.15 E.
Figura 5.15
Quando ele alcança o Ice Blaster há quatro caminhos inexplorados para tentar. Os primeiros dois
levam ele a lugares que já visitou - a Entrada e a Funhouse - assim ele marca cada caminho como
explorado antes de retroceder ao Ice Blaster para tentar outra rota. Eventualmente ele encontra um
caminho conduzindo as Slot Machines. Veja Figura 5.15 F, G e H.
Este processo de se mover através do grafo o mais longe possível antes de retroceder para
caminhos previamente inexplorados continua até que o parque temático inteiro seja mapeado. As etapas
de I a L na Figura 5.15 mostram alguns dos próximos passos do processo. A Figura 5.16 mostra o grafo
terminado, após Billy ter visitado todas as atrações e andado por todos os caminhos.
Figura 5.16: O mapa completo de Billy
Nota Dado um nodo raiz, a procura em profundidade pode apenas garantir que todos os nodos e arestas
serão visitados em um grafo conectado. Lembre, um grafo conectado é um onde qualquer nodo
pode ser alcançado de qualquer outro. Se você está pesquisando em um grafo não-conectado, tal
como C na Figura 5.3, então o algoritmo deve ser expandido para incluir um nodo raiz para cada
sub-grafo.
Implementação do Algoritmo
O DFS é implementado como uma classe template e pode ser usada com qualquer implementação
de grafos (como em grafos densos) usando a mesma interface da classe SparseGraph mostrada
anteriormente. Primeiro vamos ver a declaração da classe, logo então eu irei descrever o algoritmo de
procura mesmo.
template<class graph_type>
class Graph_SearchDFS
{
private:
//to aid legibility
enum {visited, unvisited, no_parent_assigned};
//create typedefs for the edge and node types used by the graph
typedef typename graph_type::EdgeType Edge;
typedef typename graph_type::NodeType Node;
private:
//a reference to the graph to be searched
const graph_type & m_Graph;
//this records the indexes of all the nodes that are visited as the
//search progresses
std::vector<int> m_Visited;
O m_Visited contém o mesmo número de elementos que a quantia de nodos no grafo. Cada
elemento é inicialmente ajustado como não-visitado (unvisited). Quando a procura progride, cada vez que
um nodo é visitado, seu elemento correspondente no m_Visited será ajustado para visited.
//this holds the route taken to the target.
std::vector<int> m_Route;
O m_Route também contém o mesmo número de elementos que a quantia de nodos no grafo. Cada
elemento é ajustado inicialmente como no_parent_assigned. Quando a procura no grafo prossegue, este
vetor armazena a rota para o nodo final ao gravar os pais de cada nodo no índice relevante. Por exemplo,
se o caminho para o nodo final segue os nodos 3-8-27, então o m_Route[8] terá 3 e o m_Route[27] terá 8.
//the source and target node indices
int
m_iSource,
m_iTarget;
Quando você explora um grafo, frequentemente você não vai querer procurar um objetivo
específico (ou objetivos). Para usarmos a analogia do parque novamente, é como se você estivesse
procurando por um brinquedo como o rollercoaster (montanha-russa). Com isto em mente, os algoritmos
de procura em geral usam uma condição de término, geralmente na forma de um índice do nodo objetivo.
//true if a path to the target has been found
bool
m_bFound;
//this method performs the DFS search
bool Search();
Este método é o código que implementa o algoritmo de procura em profundidade. Nós nos
aprofundaremos nele logo em seguida.
public:
Graph_SearchDFS(const graph_type& graph,
int
source,
int
target = -1):
m_Graph(graph),
m_iSource(source),
m_iTarget(target),
m_bFound(false),
m_Visited(m_Graph.NumNodes(), unvisited),
m_Route(m_Graph.NumNodes(), no_parent_assigned)
{
m_bFound = Search();
}
//returns true if the target node has been located
bool
Found()const{return m_bFound;}
//returns a vector of node indexes that comprise the shortest path
//from the source to the target
std::list<int> GetPathToTarget()const;
};
O algoritmo de procura DFS é implementado usando uma std::stack de ponteiros const para as
arestas que compreendem o grafo em que se está procurando. Uma stack é uma estrutura em forma de
pilha, o último que entra é o primeiro que sai (Last In, First Out – usualmente abreviada como LIFO). A
pilha é usada de uma maneira similar a que nosso amigo Billy usava as folhas de papel para explorar o
parque temático: Arestas são colocadas nela quando a procura prossegue, assim como Billy registrava os
caminhos que ele havia explorado.
Daremos uma rápida olhada no código do método Search e então eu o explicarei com um exemplo
para garantir que você entenda como a mágica é feita.
template <class graph_type>
bool Graph_SearchDFS<graph_type>::Search()
{
//create a std stack of pointers to edges
std::stack<const Edge*> stack;
//create a dummy edge and put on the stack
Edge Dummy(m_iSource, m_iSource, 0);
stack.push(&Dummy);
//while there are edges on the stack keep searching
while (!stack.empty())
{
//grab the next edge
const Edge* Next = stack.top();
//remove the edge from the stack
stack.pop();
//make a note of the parent of the node this edge points to
m_Route[Next->To] = Next->From();
//and mark it visited
m_Visited[Next->To()] = visited;
//if the target has been found the method can return success
if (Next->To() == m_iTarget)
{
return true;
}
//push the edges leading from the node this edge points to onto
//the stack (provided the edge does not point to a previously
//visited node)
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, Next->To());
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
if (m_Visited[pE->To()] == unvisited)
{
stack.push(pE);
}
}
}//while
//no path to target
return false;
}
Para ajudar você a entender, vamos examinar um exemplo simples. Usando o grafo nãodirecionado da Figura 5.17, vamos dizer que queremos procurar o nodo 3 (o nodo alvo, T), começando do
nodo 5 (o nodo fonte ou raiz, S).
Figura 5.17: Um problema simples de procura em grafo
O Search começa criando uma aresta falsa – uma que leva o nodo fonte de volta ao nodo fonte – e
colocando-a na pilha. Veja a Figura 5.18. A aresta realçada indica a aresta na pilha.
Figura 5.18: Uma aresta falsa é colocada na pilha.
A procura prossegue ao se entrar em um loop while. Assim, enquanto houver arestas inexploradas
na pilha, o algoritmo iterará através das seguintes etapas. Os comentários entre parêntesis descrevem a
situação da primeira iteração através do loop.
1. Remover a aresta que está em cima da pilha. (A aresta falsa [5-5]);
2. Registre o pai do nodo destino da aresta inserindo o índice do pai no vetor m_Routes, no elemento
referenciado pelo índice do nodo de destino. (Por causa da aresta falsa ser usada para iniciar o
algoritmo, o pai do nodo 5 também é 5. Assim m_Route[5] é ajustado para 5);
3. Marque o nodo destino da aresta como visitado ao designar a enumeração visited ao índice
relevante no vetor m_Visited (m_Visited[5] = visited);
4. Teste a condição de término. Se o nodo destino da aresta é o nodo final, então a procura pode
retornar o sucesso. (O 5 não é o nodo final, então a procura continua);
5. Se o nodo destino da aresta não é o alvo, então forneça um nodo para a aresta atual apontar que já
não tenha sido visitado, todas as arestas adjacentes são colocadas na pilha. (As arestas [5-2], [5-4]
e [5-6] são colocadas na pilha).
A Figura 5.19 mostra o estado atual do algoritmo depois de uma iteração do loop while. A cor
cinza do nodo fonte indica que ele foi marcado como visitado.
Figura 5.19: As arestas que saem do nodo 5 são colocadas na pilha.
Neste ponto, os galhos do algoritmo voltam ao inicio do loop while, removendo a próxima aresta
de cima da pilha (aresta [5-2]), marcando o nodo destino como visitado (nodo 2) e registrando o pai dele
(o nodo 5 é pai do nodo 2).
Em seguida, o algoritmo considera quais arestas devem ser colocadas na pilha. O nodo 2 (para o
qual a aresta [5-2] aponta) tem duas arestas adjacentes: [2-1] e [2-5]. O nodo 5 foi marcado como
visitado, então a aresta [2-5] não é colocada na pilha. Como o nodo 1 não foi visitado, a aresta que vai
para ele, [2-1], é colocada na pilha. Veja a Figura 5.20. A linha negra grossa da [5-2] indica que esta
aresta em particular não será mais considerada.
Figura 5.20
Novamente os galhos do algoritmo voltam ao inicio do loop while e assim este remove a próxima
aresta da pilha (aresta [2-1]), marca o nodo destino como visitado (nodo 1) e registra o pai deste (o nodo 2
é pai do nodo 1). O nodo 1 tem arestas indo para os nodos 3 e 2. O nodo 2 já foi visitado, então assim
apenas a aresta [1-3] é colocada na pilha. Veja a Figura 5.21.
Figura 5.21
Desta vez quando o algoritmo remove a próxima aresta [1-3] da pilha, depois do procedimento
usual de marcar o nodo destino e o pai dele, o algoritmo descobre que ele localizou o objetivo, ponto no
qual o algoritmo termina. Neste estágio o estado é mostrado na Figura 5.22.
Figura 5.22
Durante a procura, o caminho para o nodo final é armazenado no vetor m_Route (representado nas
figuras anteriores pela tabela usada para armazenar os pais dos nodos). O método GetPathToTarget extrai
esta informação e retorna um vetor de inteiros representado os índices dos nodos que um agente deve
seguir para ir do nodo fonte até o nodo objetivo. Aqui o código fonte:
template <class Graph>
std::list<int> Graph_SearchDFS<Graph>::GetPathToTarget()const
{
std::list<int> path;
//just return an empty path if no path to target found or if
//no target has been specified
if (!m_bFound || m_iTarget<0) return path;
int nd = m_iTarget;
path.push_back(nd);
while (nd != m_iSource)
{
nd = m_Route[nd];
path.push_back(nd);
}
return path;
}
Este é um método muito simples. Ele começa tentando ver qual é o pai no nodo alvo, e então o pai
deste nodo, e assim por diante até que o nodo fonte seja atingido. No exemplo que você seguiu
anteriormente, o caminho que este método retorna é 5-2-1-3.
Nota Por motivos de velocidade e eficiência, as implementações dos algoritmos de procura descritos
neste capítulo são projetadas para operarem em grafos criados antes da procura. Entretanto, para
alguns problemas será impossível se fazer isso por causa do tamanho do grafo ser muito grande para
se armazenar na memória ou por causa da necessidade de se conservar memória apenas com a
criação dos nodos e arestas que são essenciais para a procura. Por exemplo, se você quiser procurar
o espaço de estados de um jogo como xadrez, é impossível se construir um grafo antes da procura,
por causa número massivo de estados possíveis. Assim, os nodos e aresta devem ser criados durante
a procura.
O DFS em ação
Para dar a você um retorno útil, eu criei um programa de demonstração que acompanha este
capítulo, o qual demonstra as várias procuras em grafos em um grafo de navegação com formato de
grade. Este tipo de arranjo de nodos é comumente encontrado em jogos baseados em tiles, onde um nodo
é posicionado no centro de cada tile e as arestas o conectam aos oito vizinhos. Veja a Tela 5.1. As linhas
verticais e horizontais representam os limites dos tiles, os pontos são os nodos do grafo e as linhas finas
saindo dos nodos são as arestas de conexão. Infelizmente, a tela foi impressa em escala de cinzas, então
pode ser difícil ver tudo isso claramente. Se você tem um computador próximo, eu recomendo que rode o
executável PathFinder.exe, e aperte a tecla “G” para ver o grafo sendo mostrado.
Tela 5.1
Nota Embora no mundo real as conexões diagonais na demonstração PathFinder seja maiores que as
conexões verticais e horizontais, a procura em profundidade não considera qualquer custo associado
a arestas, assim trata todas elas como iguais.
Eu usei um arranjo de nodos baseado em grade para a demonstração porque assim é mais fácil de
se criar grafos experimentais com tiles de bloqueio que representam obstáculos ou variação de terreno.
Entretanto, isto não significa que seu jogo deve usar um grafo baseado em grade. Eu enfatizei este ponto
porque vejo com muita freqüência que os iniciantes as vezes tem dificuldade de entender como um grafo
pode ser de qualquer forma além de uma grade. Eles dizem coisas como, “eu sei que o algoritmo de
procura XYZ funciona em jogos RTS baseados em tiles, mas é possível usá-lo em meu FPS?”. Eu vejo
esta questão com freqüência e eu acho que ela é devida a maioria das demonstrações, tutoriais e artigos
sobre pathfinding mostrarem exemplos usando um arranjo de nodos baseado em grade (pelas razões que
eu já disse), e o pessoal acha que é dessa maneira que a coisa deve ser. Por favor... eu imploro a você, não
cometa este mesmo erro! Os grafos podem ser de qualquer forma que você quiser (e com qualquer
número de dimensões).
De qualquer maneira, vamos voltar ao DFS. A Tela 5.2 mostra um simples mapa que eu criei
bloqueando alguns tiles como obstáculos.
Tela 5.2: Um simples mapa de teste (Pela claridade, o grafo não é mostrado, apenas os tiles).
Como a impressão é em escala de cinzas, eu fiz os nodos fonte e objetivo mais fáceis de serem vistos ao
marcá-los com um quadrado e um X, respectivamente. Os números no canto inferior direito mostram o número
de nodos (n) e arestas (e) no grafo.
Melhorias no DFS
Alguns grafos podem ser muito profundos e o DFS pode facilmente demorar explorando
caminhos errados. Em um cenário de pior caso, o DFS pode ser incapaz de se recuperar de uma
escolha errada no início da pesquisa, vindo a ficar permanentemente incapacitado.
Como um exemplo, vamos dizer que você deseja encontrar a solução para um cubo mágico
misturado aleatoriamente. O espaço de estados inteiro deste problema é enorme e proíbe a geração do
grafo de estados completo antes de qualquer pesquisa, portanto os nodos são criados em tempo de
execução, quando cada estado é expandido começando a partir do nodo raiz. Em algum ponto na
pesquisa, o algoritmo DFS pode escolher uma aresta conduzindo para uma sub-grafo de um espaço de
estados que não contém um estado de solução, mas que também é muito grande para se expandi-lo
todo, dado a força computacional disponível. Isto resulta em que uma solução nunca será retornada
pelo DFS, e o computador efetivamente travará.
Felizmente, pela limitação de quantas arestas de profundidade o algoritmo DFS pode pesquisar
antes de começar a retroceder, pode-se prevenir isso. Isso é chamado de procura com profundidade
limitada. Ao se utilizar uma procura com profundidade limitada, com uma profundidade em que o
algoritmo pode pesquisar com a força computacional disponível, o DFS sempre retornará uma solução
se ela existir nessa profundidade.
Entretanto, a procura com profundidade limitada tem um obstáculo maior. Como você pode
saber que limite atribuir a máxima profundidade de pesquisa? Para a maioria dos domínios de
problemas, é impossível se julgar qual limite se escolher. Usando o exemplo do Cubo Mágico, uma
solução pode estar a três ou quinze movimentos. Se a profundidade máxima de pesquisa for atribuída
em dez, pode ou não haver uma solução. Se for atribuído um valor muito alto, o número de estados
possíveis resultantes na pesquisa pode travar o computador. Felizmente, há uma maneira de se
contornar este problema: DFS com aprofundamento iterativo.
A procura com aprofundamento iterativo funciona usando o DFS para pesquisar um grafo com
uma profundidade limita em um, logo então, dois, três, e assim por diante, até que a pesquisa seja
completada. Embora a princípio isto possa parecer um desperdício de recursos já que os nodos em
profundidades rasas são pesquisados múltiplas vezes, na realidade a maioria dos nodos estão sempre
no limite do grafo pesquisado. Isso é especialmente verdade para pesquisas através de grafos com um
alto fator de expansão. Dado um fator de expansão de oito, como o do grafo na demonstração
PathFinder, o número de nodos no limite é mostrado na Tabela 5.1.
Tabela 5.1
Profundidade
Nodos no Limite
Total de Nodos
0
1
1
1
8
9
2
64
73
3
512
585
4
4096
4681
n
8
n
1+ …+8n-1+8n
Eu imagino que alguns de vocês podem pensar coisas como "Mas se, durante uma pesquisa
DFS normal, uma profundidade de n trava o computador, seguramente quando o aprofundamento
iterativo DFS alcançar a mesma profundidade, ele também travará o computador!" A resposta é sim,
se o IDDFS (Iterative Deepening DFS) puder ir tão fundo, você terá problemas, mas o segredo para
usar a abordagem do aprofundamento iterativo é impor um limite, usualmente definido como um
limite de tempo. Quando o tempo destinado para a pesquisa expira, o algoritmo acaba, não
interessando qual nível ele alcançou.
Uma vantagem desta abordagem metódica é que se darmos o tempo bastante e um objetivo
válido, o aprofundamento iterativo não só encontrará o objetivo, mas encontrará o objetivo com
menos passos possíveis.
A linha na Tela 5.3 ilustra o caminho que o DFS fez em sua busca ao objetivo. Como você pode
ver, ele percorre quase toda a área do mapa antes de tropeçar sobre o nodo objetivo, claramente
demonstrando que, embora o DFS possa encontrar o objetivo, ele não garante encontrar a melhor rota
para ele.
Tela 5.3: O DFS em ação
Também note neste exemplo que o DFS não explorou quaisquer arestas que não estivessem no
caminho para o nodo objetivo. Quando o nodo objetivo pode ser alcançado via múltiplos caminhos isto é
comum no DFS, tornando ele um algoritmo veloz para ser empregado quando o comprimento do caminho
não tem importância (por exemplo, quando estamos pesquisando em um espaço de estados para ver se um
estado em particular existe, sem nos importarmos em determinar a rota mais rápida para esse estado).
3.1.2 Busca em Amplitude (Breadth First Search)
Embora o DFS garanta encontrar um nodo objetivo em um grafo conectado, ele não garante
encontrar o melhor caminho para esse nodo – o caminho que contém menos arestas. No exemplo anterior,
o DFS resultou em um caminho com três arestas, enquanto o melhor caminho tinha duas: 5-4-3. Veja a
Figura 5.22.
O algoritmo BFS sai do nodo fonte e examina cada um dos nodos que estão nas suas arestas antes
de então ir para cada um desses nodos e examinar todas as arestas que se conectam a eles e assim em
diante. Você pode pensar nesta pesquisa como explorando todos os nodos que estão a uma aresta de
distância do nodo fonte, então todos os nodos que estão a duas arestas de distância, então três arestas, e
assim em diante até o nodo objetivo ser encontrado. Portanto, quando o objetivo é localizado, fica
garantido que o caminho que conduz para ele contém o menor número de arestas possíveis. (Pode haver
outros caminhos de comprimento igual, mas não haverá nenhum mais curto).
Implementação do Algoritmo
O algoritmo para BFS é quase o mesmo que o para DFS, exceto que este usa uma fila onde o
primeiro que entra é primeiro que sai (First In, First Out - FIFO) em vez de uma pilha.
Consequentemente, desta vez as arestas são tiradas da fila na mesma ordem em que elas são colocadas.
Dê uma olhada no código fonte do método Search do BFS.
template <class graph_type>
bool Graph_SearchBFS< graph_type>::Search()
{
//create a std queue of pointer's edges
std::queue<const Edge*> Q;
//create a dummy edge and put on the queue
const Edge Dummy(m_iSource, m_iSource, 0);
Q.push(&Dummy);
//mark the source node as visited
m_Visited[m_iSource] = visited;
//while there are edges in the queue keep searching
while (!Q.empty())
{
//grab the next edge
const Edge* Next = Q.front();
Q.pop();
//mark the parent of this node
m_Route[Next->To()] = Next->From();
//exit if the target has been found
if (Next->To() == m_iTarget)
{
return true;
}
//push the edges leading from the node at the end of this edge
//onto the queue
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, Next->To());
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
//if the node hasn't already been visited we can push the
//edge onto the queue
if (m_Visited[pE->To()] == unvisited)
{
Q.push(pE);
//the node is marked as visited here, BEFORE it is examined, because
//it ensures a maximum of N edges are ever placed in the queue,
// rather than E edges.
m_Visited[pE->To()] = visited;
}
}
}
//no path to target
return false;
}
Para esclarecer o algoritmo para você, vamos seguir o mesmo exemplo usado anteriormente. A
Figura 5.23 irá refrescar sua memória.
Figura 5.23: Encontre o caminho mais curto do nodo 5 para o 3.
O BFS começa como o DFS. Primeiro uma aresta falsa [5-5] é criada e colocada na fila. Então o
nodo fonte é marcado como visitado. Veja a Figura 5.24.
Figura 5.24
A seguir o algoritmo toma nota do pai do nodo 5. Como antes, por causa da primeira aresta ser
considerada uma aresta falsa, o nodo 5 é ajustado como pai dele mesmo. Esta aresta então é removida da
frente da fila e todas as arestas adjacentes ao nodo 5 (somente as que apontam para nodos não-visitados)
são adicionadas. Veja a Figura 5.25.
Figura 5.25
Até aqui tudo parece como o DFS, mas agora é onde o algoritmo difere. A seguir, a aresta [5-6] é
removida da fila. O nodo 5 é marcado como pai do nodo 6. Como ambas as arestas adjacentes ao nodo 6
apontam para nodos já visitados, elas não são adicionadas na fila. Veja a Figura 5.26.
Figura 5.26
A próxima da fila é a aresta [5-4]. O nodo 5 é marcado como pai do nodo 4. O nodo 4 tem três
arestas adjacentes, mas apenas a aresta [4-3] aponta para o nodo não marcado, assim só esta é colocada na
fila. Veja a Figura 5.27.
Figura 5.27
A próxima é a aresta [5-2]. O nodo 5 é marcado como pai do nodo 2 e a aresta [2-1] é colocada na
fila. Veja a Figura 5.28.
Figura 5.28
A aresta [4-3] é a próxima. O nodo 4 é marcado como pai do nodo 3. Como o nodo 3 é o nodo
objetivo, neste ponto o algoritmo é encerrado. Veja a Figura 5.29. Usando o vetor m_Routes para procurar
os pais do nodo objetivo até o nodo fonte, conseguimos o caminho 3-4-5. Este é o caminho entre os dois
que contém menos arestas... o melhor caminho.
Figura 5.29
Dica Você pode acelerar o BFS (e muitos outros algoritmos de procura em grafos) rodando duas procuras
simultaneamente, uma começando do nodo fonte e outra do nodo objetivo, parando a procura
quando elas se encontram. Isto é chamado de procura bidirecional.
O BFS em Ação
Vamos rodar o programa PathFinder novamente para ver o BFS operando no mundo real.
Primeiro de tudo, eu acho que será útil para você examinar o exemplo simples mostrado na Tela 5.4. (Se
você
já
estava
rodando
o
programa
PathFinder,
carregue
o
arquivo
no_obstacles_source_target_close.map, e clique no botão BF na barra de ferramentas).
Tela 5.4
Neste caso não há obstáculos presentes. O nodo fonte é posicionado próximo ao nodo objetivo
com somente alguns outros nodos (tiles) separando-os. Novamente a linha grossa mostra o caminho que
o algoritmo BFS encontrou. As linhas finas representam todas as arestas que o algoritmo visitou no
caminho para o objetivo. Isto claramente demonstra como o BFS sai do nodo fonte até que o nodo
objetivo seja encontrado. As arestas visitadas formam um quadrado porque o BFS, assim como o DFS,
trata todas as arestas como tendo o mesmo comprimento. O caminho verte para esquerda e então para a
direita em vez de ir diretamente para o nodo objetivo pela mesma razão. Eles tomam o mesmo número de
etapas, mas a forma do caminho é inteiramente dependente da ordem como os nodos das arestas são
explorados.
A Tela 5.5 mostra o BFS em operação no mesmo mapa visto anteriormente. A melhoria no
comprimento do caminho é clara, entretanto isto é esperado já que o DFS não é feito para procuras de
caminhos mais curto. Mais uma vez, note como todas as arestas com a mesma profundidade que a do
nodo fonte até o nodo objetivo são visitadas.
Tela 5.5
Infelizmente, por causa do BFS ser tão sistemático em sua exploração, ele pode ser tornar inviável
para procuras que não sejam em um espaço de procura pequeno. Se nós representarmos o fator de
expansão como b e o número de arestas entre o nodo objetivo e o fonte como d (depth, profundidade),
então o número de nodos examinados é dado pela Equação 5.2.
(5.2)
Se o grafo a ser explorado é muito grande e tem um alto fator de expansão, então o BFS vai gastar
muita memória e ter um desempenho horrível. Pior ainda, é se o espaço de estados tiver um fator de
expansão tão alto que proíba a criação de um grafo completo antes da pesquisa, requerendo que o BFS
expanda os nodos enquanto explora, uma pesquisa pode literalmente levar anos para terminar. Em seu
livro Artificial Intelligence: A Modern Approach, Russell e Norvig dão um exemplo de um puzzle com
um fator de expansão de 10; assumindo que se leva um milissegundo para expandir cada nodo, o BFS
levará 3,500 anos para alcançar uma profundidade de 14! Os computadores se tornaram bestas muito mais
rápidas desde que a primeira edição desse livro foi publicada, mas, até mesmo assim, você ficaria velho
com a quantia de tempo que o BFS leva para resolver esse problema com essa profundidade.
3.2 Procuras em Grafos Baseadas em Custo
Para muitos domínios de problemas, o grafo relatado contém um custo (às vezes chamado de
peso) associado a travessia de uma aresta. Por exemplo, os grafos de navegação usualmente possuem
arestas com um custo proporcional a distância entre os nodos que elas conectam. Para se encontrar os
caminhos mais curtos nesses grafos, esses custos devem ser levados em conta. Não é o bastante
simplesmente – como fizemos anteriormente com o BFS – encontrar o caminho que contém o menor
número de arestas, pois, com um custo associado, pode ser muito melhor percorrer várias arestas curtas
do que duas longas. Veja a Figura 5.30.
Figura 5.30: O caminho 1 - 5 - 4 - 3 é mais curto que o 1 - 2 - 3, mesmo tendo mais arestas.
Embora seja possível se usar o BFS ou o DFS para procurar exaustivamente todas as rotas para
um objetivo, adicionando custos para cada caminho e então se selecionando o caminho com o menor
custo, isto é obviamente uma solução muito ineficiente. Felizmente há métodos muito melhores a nossa
disposição.
3.2.1 Relaxamento de Arestas
Os algoritmos de procura discutidos no restante deste capítulo são baseados em uma técnica
chamada relaxamento de arestas. Quando um algoritmo prossegue, ele junta informações sobre o melhor
caminho encontrado até aqui (best path so far - BPSF) do nodo fonte até qualquer outro nodo na rota
para o nodo objetivo. Esta informação é atualizada quando novas arestas são examinadas. Se uma aresta
examinada recentemente infere que o caminho para um nodo pode ser tornado mais curto ao se usar ele
em vez do melhor caminho existente, então essa aresta é adicionada e o caminho é atualizado de acordo.
Este processo de relaxamento, como todas as operações com grafos, é muito mais fácil de
entender ao se observar um diagrama. Veja a Figura 5.31. Com o grafo mostrado em A, o melhor
caminho de 1 a 4 via 3 não é melhorado ao se examinar a aresta [5-4]. Assim nenhum relaxamento é
necessário. Com o grafo B, entretanto, a aresta [5-4] pode ser utilizada para criar um caminho mais curto
para 4; assim o BPSF deve ser atualizado de acordo para mudar o pai do nodo 4 de 3 para 5 (levando ao
caminho 1 - 2 - 5 - 4).
Figura 5.31
Este processo é chamado de relaxamento de arestas, pois imita a maneira como um pedaço de
elástico esticado ao longo das arestas do BPSF pode relaxar (vir a ficar menos tenso) quando uma aresta
encontrada facilita um caminho mais curto.
Cada algoritmo mantém um std::vector de floats (indexados por nodo) representando o melhor
custo total para cada nodo encontrado pelo algoritmo até aqui. Dado o caso generalizado mostrado na
Figura 5.32, o pseudo-código para relaxar um caminho pode parecer um o seguinte:
if (TotalCostToThisNode[t] > TotalCostToThisNode[n] + EdgeCost(n-to-t))
{
TotalCostToThisNode[t] = TotalCostToThisNode[n] + EdgeCost(n-to-t));
Parent(t) = n;
}
Figura 5.32
3.2.2 Árvores dos Caminhos mais Curtos
Dado um grafo G e um nodo fonte, a árvore do caminho mais curto (shortest path tree - SPT) é a
sub-árvore de G que representa o caminho mais curto de qualquer nodo na SPT até o nodo fonte.
Novamente, uma imagem vale mais que mil palavras, então dê uma olhada na Figura 5.33. Ela mostra
uma SPT com a raiz posicionada no nodo 1.
Figura 5.33: A árvore do caminho mais curto para o nodo 1 é mostrada na esquerda pelas arestas grossas e é representada
novamente na direita por uma árvore direcionada. Para se encontrar o caminho mais curto no grafo para o nodo 1, tudo que
você tem que fazer é traçar uma rota reversa na SPT saído do nodo em questão. Por exemplo, traçando o caminho do nodo 3
para o nodo 1, leva ao caminho 1 - 6 - 4 - 3.
Os algoritmos a seguir encontram os caminhos mais curtos em grafos com pesos ao “fazer
crescer” uma árvore de caminho mais curto a partir do nodo fonte.
3.2.3 O Algoritmo de Dijkstra
O professor Edsger Wybe Dijkstra forneceu a informática muitas contribuições valiosas, mas uma
das mais famosas é seu algoritmo para encontrar o caminho mais curto em grafos com pesos.
O algoritmo de Dijkstra constrói uma árvore de caminho mais curto com uma aresta de cada vez,
adicionando primeiro o nodo fonte na SPT e então adicionando a aresta que leva o caminho mais curto do
nodo fonte até um nodo que não está na SPT. Este processo resulta em uma SPT contendo o caminho
mais curto de cada nodo no grafo até o nodo fonte. Se o algoritmo é equipado com um nodo objetivo, o
processo termina quando ele é encontrado. Nesse ponto o algoritmo termina, a SPT gerada contém o
caminho mais curto do nodo fonte até o nodo objetivo e de cada nodo visitado durante a procura.
Nota Histórica Dijkstra é também famoso por ter projetado e codificado o compilador Algol 60 e por
denunciar ferventemente o uso do comando goto na programação. Eu também vi ele dizer
que "a questão de se os computadores podem pensar é a mesma questão de se os
submarinos podem nadar." Infelizmente, Dijkstra morreu em 2002 de câncer.
Vamos seguir um exemplo usando o mesmo grafo mostrado na Figura 5.33 mas desta vez o nodo
fonte será o nodo 5.
Primeiro, o nodo 5 é adicionado na SPT e as arestas que saem dele são colocadas na fronteira de
procura. Veja a Figura 5.34.
Figura 5.34: O nodo 5 é adicionado na SPT. As arestas na fronteira de procura estão realçadas.
O algoritmo então examina os nodos de destino das arestas na fronteira – 6 e 2 – e adiciona o mais
próximo ao fonte (o nodo 2 está a distância de 1.9) na SPT. A seguir, as arestas que deixam o nodo 2 são
adicionadas a fronteira. Veja a Figura 5.35.
Figura 5.35: As arestas negras grossas representam as que estão na SPT.
Novamente o algoritmo examina os nodos de destino na fronteira. O custo para ir até o nodo 3 a
partir do fonte é 5 (1.9 + 3.1), o custo para ir até o nodo 6 é 3. Assim o nodo 6 é próximo nodo a ser
adicionado na SPT, e todas as arestas que saem dele são adicionadas na fronteira. Veja a Figura 5.36.
Figura 5.36
O processo é repetido mais uma vez. Como o custo para o nodo 4 é menor que o custo para o nodo
3, este é adicionado a SPT. Desta vez, entretanto, a única aresta que sai do nodo 4 vai para o nodo 3 – um
nodo que já foi o nodo de destino de uma aresta na fronteira. Aqui é onde o relaxamento de arestas entra.
Ao se examinar ambos os caminhos para 3, o algoritmo vê que o caminho 5 – 2 – 3 tem um custo de 5.0 e
o caminho 5 – 6 – 4 – 3 têm um custo maior, com 7.8. Assim, a aresta [2-3] permanece na SPT e a aresta
[4-3] é removida de qualquer consideração posterior. Veja a Figura 5.37.
Figura 5.37
Finalmente o nodo 3 é adicionado na SPT. Veja a Figura 5.38. Note como a aresta [3-5] não foi
adicionada na fronteira. Isto porque o nodo 5 já está na SPT e não precisa de consideração posterior.
Adicionalmente, note como o nodo 1 não foi adicionado na SPT. Desde que haja somente arestas que
saem do nodo 1, ele fica efetivamente isolado a partir dos outros nodos no grafo.
Figura 5.38
Implementação do Algoritmo de Dijkstra
A implementação do algoritmo de caminho mais curto Dijkstra pode ser difícil de entender a
princípio e eu confesso que não foi de primeira que eu consegui escrever esta parte do capítulo, pois
reconheço que não é fácil explicar! Eu acho que ambos precisamos respirar fundo antes de seguir:
inspire... mantenha... três, dois, um... e expire.
Agora está muito melhor. Certo, deixe-me começar mostrando a você a declaração da classe. Os
comentários dentro do código fornecem explicações de cada um dos atributos, a maioria dos quais deve
soar agora como familiares.
template <class graph_type >
class Graph_SearchDijkstra
{
private:
//cria typedefs para os tipos nodo (node) e aresta (edge) usados pelo grafo
typedef typename graph_type::EdgeType Edge;
typedef typename graph_type::NodeType Node;
private:
const graph_type &
m_Graph;
//este vetor contém as arestas que compreendem a árvore de caminho mais curto //uma sub-árvore direcionada do grafo que encapsula os melhores caminhos a partir
//de cada nodo na SPT para o nodo fonte.
std::vector<const Edge*>
m_ShortestPathTree;
//este é indexado pelo índice do nodo e mantém o custo total de melhor
//caminho encontrado até aqui para o dado nodo. Por exemplo, m_CostToThisNode[5]
//manterá o custo total de todas as arestas que compreendem o melhor caminho
//para o nodo 5 encontrado até aqui ns procura (se o nodo 5 está presente e foi
//visitado é claro).
std::vector<double>
m_CostToThisNode;
//este é um vetor indexado (por nodo) das arestas "pais" que saem dos nodos
//conectados a SPT, mas que não foram ainda adicionadas na SPT.
std::vector<const Edge*> m_SearchFrontier;
int
int
m_iSource;
m_iTarget;
void Search();
public:
Graph_SearchDijkstra(const graph_type& graph,
int
source,
int
target = -1):m_Graph(graph),
m_ShortestPathTree(graph.NumNodes()),
m_SearchFrontier(graph.NumNodes()),
m_CostToThisNode(graph.NumNodes()),
m_iSource(source),
m_iTarget(target)
{
Search();
}
//retorna o vetor de arestas que define a SPT. Se um objetivo é fornecido
//no construtor, então este será a SPT que compreende todos os nodos
//examinados antes de o objetivo ser encontrado, se não, ele conterá todos os nodos
//no grafo.
std::vector<const Edge*> GetAllPaths()const;
//retorna um vetor de índices de nodo que compreende o caminho mais curto
//a partir do fonte até o objetivo. Ele calcula o caminho funcionando
//reversamente através da SPT a partir do nodo objetivo.
std::list<int>
GetPathToTarget()const;
//retorna o custo total para o objetivo
double
GetCostToTarget()const;
};
Este algoritmo de procura é implementado usando uma fila de prioridade ordenada. Uma fila de
prioridade, ou PQ (priority queue) para abreviar, é uma fila que mantém seus elementos ordenados em
ordem de prioridade (nenhuma surpresa até então). Este tipo de estrutura de dados pode ser utilizado para
armazenar os nodos de destino das arestas na fronteira de procura, em ordem crescente de distância
(custo) do nodo fonte. Este método garante que o nodo na frente da PQ não é só um nodo que já está na
SPT, mas é o nodo mais próximo ao nodo fonte. Isto faz sentido para você até aqui? Se não, por favor,
leia este parágrafo outra vez com muita atenção.
Uma PQ deve ser capaz de manter os elementos armazenados dentro de uma ordem. Isto implica
que cada nodo do grafo deve ter um atributo adicional para armazenar os custos acumulados para esse
nodo, a fim de que os operadores possam ser sobrecarregados para se obter o comportamento correto.
Embora, se usar um atributo adicional seja certamente uma solução válida, eu optei por não mudar o nodo
de grafo existente, além disso, isto pode ser problemático quando múltiplas procuras são executadas
simultaneamente, já que cada procura individual utilizará a mesma estrutura de dados. Isto pode ser
contornado ao se criar cópias dos nodos, mas então as preciosas memória e velocidade serão perdidas.
A alternativa é usar uma fila de prioridade indexada (iPQ para abreviar). Este tipo de PQ indexa
um vetor de chaves. Neste exemplo, as chaves são os custos acumulados para cada nodo armazenado no
vetor m_CostToThisNode. Um nodo é adicionado na fila ao se inserir seu índice. Semelhantemente,
quando um nodo é recuperado da iPQ, é seu índice que é retornado e não o próprio nodo (ou um ponteiro
para o nodo). Este índice pode então ser utilizado para acessar o nodo e seus dados via o
m_Graph::GetNode.
É hora de mostrar a você algum código fonte. Garanta que você tomará seu tempo e compreenderá
todas as linhas deste algoritmo; isto será de grande ajuda a você a longo prazo. Eu fiz comentários dentro
do fonte para auxiliar na sua compreensão, mas, se você é um mero mortal, eu duvido que só os
comentários sejam o bastante para da o "estalo" em sua primeira leitura. (Se depois de algumas leituras
você ainda tem dificuldades com o algoritmo, eu recomendo fortemente que você siga o código em uma
folha de papel usando um exemplo simples).
template <class graph_type>
void Graph_SearchDijkstra<graph_type>::Search()
{
//cria uma fila de prioridade indexada que ordena em ordem crescente
//(frente para trás). Note que o úmero máximo de elementos que a iPQ
//pode conter é NumNodes(). Isto é porque nenhum nodo pode ser representado
//na fila mais de uma vez.
IndexedPriorityQLow<double> pq(m_CostToThisNode, m_Graph.NumNodes());
//coloca o nodo fonte na fila
pq.insert(m_iSource);
//enquanto a fila não está vazia
while(!pq.empty())
{
//pega o nodo com o menor custo da fila. Não esqueça, o valor retornado
//é um *índice de nodo*, não o próprio nodo. Este nodo já está na
// SPT e é o nodo mais perto do nodo fonte
int NextClosestNode = pq.Pop();
//move esta aresta da fronteira de procura para a SPT
m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
//se o objetivo foi encontrado sai
if (NextClosestNode == m_iTarget) return;
//agora relaxe as arestas. Para cada aresta conectada ao próximo nodo mais perto
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
//o custo total para o nodo que esta aresta aponta é o custo para o
//nodo atual mais o custo da aresta que conecta ele.
double NewCost = m_CostToThisNode[NextClosestNode] + pE->Cost();
//se esta aresta nunca esteve na fronteira, tome nota do custo
//para atingir o nodo a que ela aponta, então adicione a aresta na fronteira
//e o nodo de destino na PQ.
if (m_SearchFrontier[pE->To()] == 0)
{
m_CostToThisNode[pE->To()] = NewCost;
pq.insert(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
//se não, teste para ver se o custo para atingir o nodo de destino via o
//nodo atual é melhor que o melhor custo encontrado até aqui. Se
//este caminho é melhor, designamos o novo custo para o nodo de destino,
//atualiza esta entrada na PQ para refletir a mudança, e adiciona a
//aresta na fronteira
else if ( (NewCost < m_CostToThisNode[pE->To()]) &&
(m_ShortestPathTree[pE->To()] == 0) )
{
m_CostToThisNode[pE->To()] = NewCost;
//por causa de o custo ser menor que o anterior, a PQ deve ser
//reordenada para contar com isto.
pq.ChangePriority(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
}
}
}
Dica A implementação da fila de prioridade indexada utiliza uma pilha de dois sentidos para armazenar
os elementos. Para grafos esparsos, se cada aresta examinada produz uma melhoria no custo
(requerendo que o IndexedPriorityQLow::ChangePriority seja chamado), o algoritmo leva um
tempo de Elog2N em um cenário de pior caso, entretanto na prática o tempo de execução será
significantemente menor.
É possível se ganhar melhorias de velocidade ao se usar uma pilha de d-sentidos onde d é uma
função de densidade de grafo. Assim o tempo levado em um cenário de pior caso será de ElogdN.
Agora que tudo foi dito, o algoritmo de caminho mais curto Dijkstra tem um desempenho muito
bom e garante encontrar o caminho mais curto entre dois nodos se ele existe.
O Algoritmo de Dijkstra em Ação
Vamos iniciar o programa PathFinder novamente e ver como o algoritmo de Dijkstra se
desempenha nos exemplos vistos anteriormente. A Tela 5.6 ilustra o algoritmo operando no problema
simples.
Tela 5.6
O resultado é similar ao BFS, porém agora a árvore que compreenda as arestas examinadas é de
aparência circular. Isso é por que o algoritmo Dijkstra funciona com os custos das arestas e assim desta
vez as arestas diagonais custam mais para serem atravessadas que as horizontais e verticais. Com isto em
mente você pode ver como o algoritmo procurou em uma distância similar em todas as direções antes de
atingir o objetivo.
A Tela 5.7 mostra o algoritmo Dijkstra operando em um mapa mais complexo.
Tela 5.7
Como o BFS, o algoritmo de Dijkstra examina muitas arestas. Será que não seria bom se o
algoritmo pudesse ser informado quando progredisse para orientar a procura na direção correta? Bom,
felizmente para nós, isto é possível. Damas e cavalheiros, por favor, uma salva de aplausos e seja bem
vindo A*!
3.2.4 O Dijkstra com uma Melhoria: A*
O algoritmo de Dijkstra faz a procura minimizando o custo do caminho até aqui. Isso pode ser
melhorado significativamente ao se considerar, quando colocamos os nodos na fronteira, uma estimativa
do custo do objetivo para cada nodo considerado. Essa estimativa é usualmente chamada de heurística, e
o nome dado ao algoritmo que usa esse método de procura heuristicamente orientada é A* (pronunciado
a-estrela). E ele é muito bom também!
Se a heurística utilizada pelo algoritmo resulta em um valor menor que o custo real (subestimando
o custo) de qualquer nodo para o objetivo, então é garantido que o A* leve a caminhos ótimos. Para
grafos que contenham informações espaciais, tais como os grafos de navegação, há várias funções de
heurística que você pode usar, a mais usada é o comprimento de uma linha reta entre os nodos em
questão. Esta é às vezes chamada como a distância Euclidiana.
O A* procede de forma quase idêntica ao algoritmo de procura de Dijkstra. A única diferença é o
cálculo dos custos dos nodos na fronteira de procura. O custo ajustado F, para o nodo quando posicionado
na fila de prioridade (a fronteira de procura), é calculado como:
(5.3)
Onde G é o custo cumulativo para atingir um nodo e H é a heurística estimada da distância para o
objetivo. Para uma aresta E que está na fronteira e foi adicionada na SPT, o pseudocódigo para calcular o
custo para o nodo de destino é o seguinte:
Cost = AccumulativeCostTo(E.From) + E.Cost + CostTo(Target)
Utilizando uma heurística desta maneira, o custo modificado direciona a procura na direção do
objetivo em vez de irradiar igualmente em todas as direções. Isso resulta em que apenas algumas arestas
são examinadas, assim a aceleração da procura é a diferença primária entre o A* e o algoritmo de
Dijkstra.
Nota Se você ajusta o custo da heurística em zero no A*, o procura resultante será exatamente a mesma
que a do algoritmo de Dijkstra.
Vamos dar uma olhada em como o A* opera nos grafos problemas usados no programa
PathFinder.
O A* em Ação
A Tela 5.8 mostra o resultado do A* operando no problema exemplo simples. Como você pode
ver, nenhuma aresta estranha foi considerada, o caminho leva diretamente ao objetivo. A função de
heurística usada é a distância de uma linha reta entre dois nodos.
Tela 5.8: Não supera o Go, então não ganha 200 libras.
A Tela 5.9 é impressionante. Observe como apenas algumas arestas são consideradas pelo A*
antes de descobrir o objetivo. Como uma consequência disso, o tempo levado para a pesquisa ser
desempenhada é consideravelmente menor que para qualquer outra pesquisa (ainda que uma raiz
quadrada do mal seja necessária para se calcular o custo da heurística).
Tela 5.9
Nota O A* é induvidavelmente de eficiência ótima. Em outras palavras, nenhum outro algoritmo de
procura expandirá tão poucos nodos na procura pelo caminho com menor custo entre o nodo fonte e
o objetivo.
Implementação do A*
A classe A* é muito semelhante a Graph_SearchDijkstra. A implementação da procura requer que
dois std::vectors de custos sejam mantidos: uma para o custo F de cada nodo, o qual é indexado em uma
fila de prioridade, e um para o custo G de cada nodo. Em adição quando, quando criamos uma instância
desta classe, devemos especificar, como um parâmetro template, a heurística a ser usada. Este projeto
torna fácil o uso de heurísticas personalizadas com a classe, como a heurística da distância Manhattan,
mencionada no fim deste capítulo.
Aqui a declaração da classe para você usar:
template <class graph_type, class heuristic>
class Graph_SearchAStar
{
private:
//create a typedef for the edge type used by the graph
typedef typename graph_type::EdgeType Edge;
private:
const graph_type&
m_Graph;
//indexed into by node. Contains the "real" cumulative cost to that node
std::vector<double>
m_GCosts;
//indexed into by node. Contains the cost from adding m_GCosts[n] to
//the heuristic cost from n to the target node. This is the vector the
//iPQ indexes into.
std::vector<double>
m_FCosts;
std::vector<const Edge*>
std::vector<const Edge*>
m_ShortestPathTree;
m_SearchFrontier;
int
int
m_iSource;
m_iTarget;
//the A* search algorithm
void Search();
public:
Graph_SearchAStar(graph_type& graph,
int
source,
int
target):m_Graph(graph),
m_ShortestPathTree(graph.NumNodes()),
m_SearchFrontier(graph.NumNodes()),
m_GCosts(graph.NumNodes(), 0.0),
m_FCosts(graph.NumNodes(), 0.0),
m_iSource(source),
m_iTarget(target)
{
Search();
}
//returns the vector of edges that the algorithm has examined
std::vector<const Edge*> GetSPT()const;
//returns a vector of node indexes that comprise the shortest path
//from the source to the target
std::list<int>
GetPathToTarget()const;
//returns the total cost to the target
double
GetCostToTarget()const;
};
A heurística a ser usada por esta classe deve fornecer um método estático Calculate com a
seguinte assinatura:
//calculate the heuristic cost from node nd1 to node nd2
static double Calculate(const graph_type& G, int nd1, int nd2);
Já que o grafo usado pela demonstração PathFinder representa informações espaciais, o custo de
heurística é calculado como a distância de uma linha reta (também conhecida como distância Euclidiana)
para o nodo objetivo a partir do nodo sob consideração. O seguinte código mostra como a heurística é
implementada como uma classe que pode ser usada como uma parâmetro template para a
Graph_SearchAStar.
class Heuristic_Euclid
{
public:
Heuristic_Euclid(){}
//calculate the straight-line distance from node nd1 to node nd2
template <class graph_type>
static double Calculate(const graph_type& G, int nd1, int nd2)
{
return Vec2DDistance(G.GetNode(nd1).Position, G.GetNode(nd2).Position);
}
};
O tipo da heurística é passado como um parâmetro template quando uma instância da classe de
procura A* é criada. Aqui está como o programa de demonstração PathFinder cria uma instância da
procura A* usando a heurística Euclidiana:
//create a couple of typedefs so the code will sit comfortably on the page
typedef SparseGraph<NavGraphNode<>, GraphEdge>
NavGraph;
typedef Graph_SearchAStar<NavGraph, Heuristic_Euclid> AStarSearch;
//create an instance of the A* search using the Euclidean heuristic
AStarSearch AStar(*m_pGraph, m_iSourceCell, m_iTargetCell);
A implementação do método Search do A* é quase idêntico ao usado pelo algoritmo de Dijkstra.
A única exceção é que o custo obtido para um nodo específico antes dele ser colocado na fronteira é agora
calculado como G + H (em vez de apenas G). O valor de H é determinado pela chamada ao método
estático da classe de heurística.
template <class graph_type, class heuristic>
void Graph_SearchAStar<graph_type, heuristic>::Search()
{
//create an indexed priority queue of nodes. The queue will give priority
//to nodes with low F costs. (F=G+H)
IndexedPriorityQLow<double> pq(m_FCosts, m_Graph.NumNodes());
//put the source node on the queue
pq.insert(m_iSource);
//while the queue is not empty
while(!pq.empty())
{
//get lowest cost node from the queue
int NextClosestNode = pq.Pop();
//move this node from the frontier to the spanning tree
m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
//if the target has been found exit
if (NextClosestNode == m_iTarget) return;
//now to test all the edges attached to this node
graph_type::ConstEdgeIterator ConstEdgeItr(m_Graph, NextClosestNode);
for (const Edge* pE=ConstEdgeItr.begin();
!ConstEdgeItr.end();
pE=ConstEdgeItr.next())
{
//calculate the heuristic cost from this node to the target (H)
double HCost = heuristic::Calculate(m_Graph, m_iTarget, pE->To());
//calculate the "real" cost to this node from the source (G)
double GCost = m_GCosts[NextClosestNode] + pE->Cost();
//if the node has not been added to the frontier, add it and update
//the G and F costs
if (m_SearchFrontier[pE->To()] == NULL)
{
m_FCosts[pE->T()] = GCost + HCost;
m_GCosts[pE->To()] = GCost;
pq.insert(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
//if this node is already on the frontier but the cost to get here this
//way is cheaper than has been found previously, update the node costs
//and frontier accordingly.
else if ((GCost < m_GCosts[pE->To()]) &&
(m_ShortestPathTree[pE->To()]==NULL))
{
m_FCosts[pE->To()] = GCost + HCost;
m_GCosts[pE->To()] = GCost;
pq.ChangePriority(pE->To());
m_SearchFrontier[pE->To()] = pE;
}
}
}
}
Dica Se você está trabalhando com requisitos de memória muito restritos, você pode diminuir a quantia
de memória que as procuras do A* ou do Dijkstra usam, limitando o número de nodos colocados na
fila de prioridade. Em outras palavras, somente os n melhores nodos são mantidos na fila. Isso é
conhecido como uma procura limitada (beam search ou Simplified Memory-Bounded).
A Heurística da Distância Manhattan
Você pode ter visto como a classe de algoritmo de procura A* pode ser usada com a heurística
Euclidiana (distância em linha reta). Outra função de heurística popular entre programadores de jogos que
possuem grafos de navegação com topologia em forma de grade, como jogos de guerra baseados em tiles,
é a distância Manhattan entre dois nodos: a soma do deslocamento em tiles verticalmente e
horizontalmente. Por exemplo, a distância Manhattan entre os nodos v e w na figura 5.39 é 10 (6 + 4).
Figura 5.39: Calculo da distância Manhattan entre dois nodos
A distância Manhattan fornece uma melhoria de velocidade sobre a heurística Euclidiana, pois
nenhuma raiz quadrada é necessária para o calculo.
4. Conclusão
Você deve agora ter uma compreensão decente de grafos e dos algoritmos que você pode usar para
fazer procuras neles. Como a maioria das técnicas de IA, sua compreensão crescerá enormemente através
da experiência prática, assim eu sugiro você a tentar resolver ao menos alguns dos seguintes problemas.
4.1 A prática leva a perfeição
1. Use um lápis e um papel para traçar os algoritmos DFS, BFS e Dijkstra no grafo a seguir. Use um
nodo de início e fim para cada procura. Pontos extras serão dados para o uso de estilos e cores.
2. Crie uma classe de heurística com a distância Manhattan para estimar a distância entre um nodo e
o objetivo em um grafo de navegação. Experimente essa heurística com diferentes grafos. Ela é
melhor ou pior que a heurística Euclidiana para grafos baseados em grade?
3. A heurística Euclidiana calcula a distância de uma linha reta entre dois nodos. Esse cálculo requer
o uso de uma raiz quadrada. Crie uma heurística que funcione no espaço da distância quadrada e
note a forma do caminho que ela cria.
4. Crie um programa para encontrar a melhor solução para o puzzle Torres de Hanoi com n-argolas,
onde n pode ser qualquer inteiro positivo. Para fazer isso você deve reescrever o algoritmo BFS
para que os nodos e arestas sejam adicionados ao grafo de estados quando a procura prossegue.
Esta é uma maneira excelente de você testar o seu entendimento do material apresentado neste
capítulo.
5. Agora modifique o algoritmo que você criou no problema 4 para procurar a melhor solução
usando DFS com aprofundamento iterativo. Como ele se compara?
6. Use o algoritmo A* para resolver um cubo mágico (Rubik’s Cube) misturado. Dê muita
consideração ao projeto da função de heurística. Este é um problema difícil, procurar em um
espaço de estados potencialmente enorme, então tente primeiro criar seu algoritmo para um cubo
que esteja a somente uma rotação da solução, então duas e assim por diante. (Dica: Se você está
tendo dificuldades em projetar uma heurística, procure na internet... há vários artigos interessantes
sobre o assunto).
Figura 5.40