"Highways, telephone lines, electric power systems, computer chips,
water delivery systems, and rail lines: these physical networks, and
many others, are familiar to all of us. In each of these problem settings,
we
often wish to send some good(s) (vehicles, messages, electricity, or
water)
from one point to another, typically as efficiently as possible --
that is, along a shortest route or via some minimum cost flow pattern.''
- Ahuja, Magnanti, Orlin, and Reddy
Este exercício-programa consiste na implementação do algoritmo de Bellman-Ford-Moore que recebe um grafo g com comprimentos nos arcos e um vértice r e devolve um ciclo negativo acessível a partir de r ou um passeio de comprimento mínimo de r a v, para cada vértice v do grafo. O comprimento len(a) de cada arco a de g é um número inteiro (possivelmente negativo). Se
P=<r=v0,a1,v1,a2,v3,...,vk-1,ak,vk=v>é um passeio de um vértice r a um vértice v então seu comprimento len(P) é
len(a1) + len(a2) + ... + len(ak).Assim, o comprimento de um passeio é a soma dos comprimentos do arcos no passeio; levando-se em conta o número de vezes que cada arco ocorre no passeio. Um passeio P é dito (de comprimento) mínimo se len(P) <= len(P') para todo passeio P' com a mesma ponta inicial e a mesma ponta final de P. A distância de um vértice r a um vértice v é o menor comprimento de um caminho de r a v.
O seu programa C (documento CWEB) deve chamar-se bellman.c (bellman.w, respectivamente). O programa deve utilizar a biblioteca do SGB para representação e recuperação um grafo, como descrito a seguir.
Nota. A descrição do algoritmo de Bellman-Ford-Moore que está abaixo foi extraída do livro:
R.E. Tarjan, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia, Pennysylvania, 1983.
Seja g um grafo com comprimentos nos arcos e r um vértice de g. Denotaremos por n e m o número de vértices e de arcos de g.
Teorema 0. Sejam r e v vértices de um grafo com comprimentos nos arcos. Suponha que v é acessível a partir de r. Vale uma, e apenas uma, das seguintes afirmação:
Demonstração. Exercício.
É evidente que se v é acessível a partir de r, então existe um caminho mínimo de r a s. Entretanto, encontrar caminhos mínimos é um problema computacionamente difícil (a menos, é claro, que não tenhamos pressa em encontrar o caminho). Encontrar um caminho mínimo de r a v é tão difícil quanto encontrar um caminho hamiltoniano de r a v (um problema difícil pra cachorro).
Felizmente (ou curiosamente) existem algoritmos eficientes para encontrar-se passeios mínimos quando estes existem. Mais ainda, os passeios (mínimos) encontrados pelos algoritmos são caminhos. Uma maneira compacta de representar passeios/caminhos mínimos de um dado vértice r a todos os demais vértices de um grafo é através de uma certa árvore com raiz r.
Um árvore (ou arborescência) com raiz r é dita uma árvore de caminhos mínimos se todo vértice acessível a partir de r está na árvore e para cada vértice v na árvore o caminho de r a v na árvore é um passeio mínimo no grafo.
Teorema 1. Seja g um grafo com comprimentos nos arcos e r um de seus vértices. Vale uma, e apenas uma, das seguintes afirmação:
Demonstração. Exercício. (Este teorema é uma das conseqüências da correção do algoritmo de Bellman-Ford-Moore.)
Se t é uma árvore (ou arborescência) de g com raiz r e v é um vértice de g, então definimos dist[v] como sendo o comprimento do único caminho de r a v na árvore. Note que dist[v] não é a distância r a v no grafo, mas sim na árvore; por esta razão dist[v] é muitas vezes chamdo de distância tentativa (ou candidato a distância) de r a v no grafo. Para os vértices que não estão em t definimos dist[v] como sendo INFINITO, onde INFINITO é um número suficientemente grande. Se n é o número de vértices do grafo e L é o valor absoluto do maior comprimento de um arco então, para os nossos propósitos, podemos considerar que INFINITO = n × L + 1. Note que para cada arco uv na árvore vale que
dist[u] + len(uv) = dist[v].
O método descrito a seguir baseia-se no teorema abaixo.
Teorema 2.
Uma árvore com raiz r é de caminhos mínimos
se e somente se
dist[u] == INFINITO ou dist[v] <= dist[u] + len(uv,) para cada arco uv de g,onde dist[w] é o comprimento do caminho de r a w na árvore.
Demonstração. Exercício. :-)
O teorema 2 pode ser usado na implementação de um trecho de código que em tempo linear verifica se uma suposta árvore de caminhos mínimos é de fato uma árvore de caminhos mínimo Esta vérificação será usada na implementação do algoritmo de Bellman-Ford-Moore, veja a seção ``comportamento do se programa''.
EXERCÏCIO : Escreva uma função
int distancias_ok (Graph *g, Vertex *r){...}
que recebe um grafo g com comprimentos nos arcos
(possivelmente negativos) e um vértice r e devolve 1
se para cada vértice v o valor v->dist é
distância de r a v, em caso contrário a função
devolve 0. O consumo de tempo de sua função deve ser
linear.
O teorema 2 sugeri o seguinte método iterativa, o chamado labeling method, para tentar construir uma árvore de caminhos mínimos com raiz r.
No início de cada iteração tem-se uma árvore t com raiz r e
o comprimento dist[v] do caminho de r a
v na árvore, para cada vértice v do grafo.
Para representar a árvore t tem-se uma função
predecessor que para cada vértice v fornce o vértice
pred[v] predecessor (ou pai) de v na
árvore.
No início da primeira iteração pred[v] = NULL
para cada vértice v, dist[r] = 0 e dist[v] =
INFINITO para os demais vértices.
Itere o seguinte passo até
que dist[u] + len(u,v) >= dist[v] para cada arco uv
do grafo:
LABELING STEP
(L.R. Ford).
Selecione um arco uv tal que
dist[v] > dist[u] + len(uv). Faça
dist[v] = dist[u] + len(u,v) e pred[v] = u.
O labeling method não pára caso o grafo contenha um ciclo negativo. Ademais, mesmo que o grafo não contenha ciclos negativos e o método pare, ele pode demorar muito. Nosso primeiro refinamento será evitar que arcos sejam examinados desnecessariamente.
EXERCÏCIO : Mostre um grafo com comprimentos arbitrários e sem ciclos negativos em que o LABELING STEP consome tempo exponecial.
O labeling and scanning method mantém uma partição dos vértices em três estados: NÃO-VISTO, VISITADO e EXAMINADO. Os vértices no estado VISITADO ou EXAMINADO são exatamente aqueles que têm `distância tentativa' finita. Inicialmente r é VISITADO e os demais vértices são NÃOVISTOS. O método consiste em iterar o seguinte passo até que não hajam vértices com estado VISITADO.
SCANNING STEP. Selecione um vértice VISITADO u e examine-o, mudando o seu estado para EXAMINADO, através da aplicação do labeling step a cada arco uv tal que dist[u] + len(u,v) < dist[v] e convertendo o estado de v para VISITADO (não importa se o estado de v era NÃO-VISTO ou EXAMINADO).
O labeling and scanning method, a exemplo do labeling method, é ineficiente e não pára caso o grafo contenha um ciclo negativo acessível a partir de r. Entretanto, podemos transformar este método em um algoritmo eficiente através de uma escolha apropriado da ordem em que os vértices no estado VISITADO são examinados, como descrito logo a seguir.
E.F. Moore e, independentemente, R.E. Bellman propuseram que os vértices com estado VISITADO fossem examinados de acordo com uma ordem de busca em largura (breadth-first order): entre os vértices com estado VISITADO examine aquele que está nesse estado a mais tempo. Para implementar a busca em largura representamos o conjunto de vértices no estado VISITADO através de uma fila. Nesta implementação surge a questão do que fazer com um vértice no estado VISITADO que é visitado novamente. Um interpretação estrita de busca em largura requer que nós movamos um tal vértice no estado VISITADO para o fim da fila. Entretanto, aplicaremos uma interpretação mais livre, deixaremos o vértice no estado VISITADO na sua posição corrente na fila. A descrição abaixo implementa esta versão do labeling and scanning method usando busca em largura. Note que o método, como descrito, ainda não pára se o grafo contém ciclos negativos.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BELLMAN-FORD-MOORE (Grafo g, Vértice r)
para cada vértice v de g faça
estado[v] := NÃO-VISTO
dist[v] := INFINITO
pred[v] := NULL
estado[r] := VISITADO
dist[r] := 0
Q := INICIALIZA-FILA(r)
enquanto Q não está vazia faça
u := PRIMEIRO-DA-FILA(Q)
para cada uv em Adj[u] faça
se dist[u] + len(u,v) < dist[v] então
estado[v] := VISITADO
dist[v] := dist[u]+len(u,v)
pred[v] := u
se v não está em Q então
INSIRA-NA-FILA(Q,v)
estado[u] := EXAMINADO
devolva dist e pred
Ao longo do algoritmo, Q é uma fila de vértices; essa fila é o segredo do funcionamento do algoritmo. O comando INICIALIZA-FILA(r) cria uma fila com um só elemento, o vértice r. O comando PRIMEIRO-DA-FILA(Q) devolve e remove o primeiro elemento da fila Q. O comando INSIRA-NA-FILA(Q,v) insere v no fim da fila Q.
Para analisar o desempenho deste método divide-se a sua execução em passos. O passo zero consiste do exame do vértice r. Para j > 0, o passo j consiste do exame de todos os vértices na fila ao final do passo j - 1. Cada passo pode ser executado em tempo O(n+m) pois durante cada passo cada vértice e cada arco é examinado no máximo uma vez. (Hmmm, esse O(n+m) pode ser trocado por O(m). Por quê?) O teorema a seguir fornece um limitante superior para o número total de passos.
Teorema 3. Se g é um grafo com n vértices,m arcos e sem ciclos negativos acessíveis a partir de r, então o método de BELLMAN-FORD-MOORE gasta tempo O(n+nm) e não mais do que n-1 passos são realizados.
Demonstração. Pode-se mostrar por indução em k que se existe um passeio mínimo de r a um vértice v usando k arcos, então no início do passo k a distância tentativa dist[v] é menor ou igual ao comprimento deste passeio mínimo.
Para transforma o método de Bellman-Ford-Moore acima em um algoritmo deve-se fazer com que ele pare mesmo na presença de ciclos negativos. Uma maneira fácil de fazer isto é contar o número de passos executados. Inclua duas variáveis ao método, um inteiro passo e uma váriavel último indicando o último vértice que foi examinado durante o presente passo do método. Inicialmente passo = 0 e último = r. Depois que o vértice último é examinado incrementa-se de 1 a variável passo e último passa a ser o último vértice da fila Q. Se passo recebe o valor n com a fila Q não vazia, o (agora) algoritmo deve parar e anunciar a presença de um ciclo negativo no grafo. Com este contador de passos o algoritmo gasta tempo O(n + nm) não importando se o grafo tem ou não um ciclo negativo. Usando o lema a seguir pode-se localizar um ciclo negativo, caso um tal ciclo exista. Se v é um vértice, então
pred1[v] = pred[v]e assim por diante.
pred2[v] = pred[pred[v]]
pred3[v] = pred[pred[pred[v]]]
[...]
Lema 4. Se a fila Q não está vazia no final do passo n-1 então predk[v] = v para algum vértice v e inteiro k e o correspondente ciclo em g é negativo.
Demonstração. Suponha que o algoritmo é executado até que um vértice w seja examinado no passo n. Defina passo[v] de um vértice v como sendo o máximo j tal que v é examinado durante o passo j. Se passo[v] é definido e positivo então pred[v] e passo[pred[v]] são definidos e passo[pred[v]] >= passo[v] - 1. Temos que passo[w]=n. Seguindo os apontadores pred a partir de w nos devemos, em algum momento, repetir algum vértice, pois existem somente n vértices e o passo de cada vértice decresce de no máximo um em cada passo.
Uma descrição alternativa do método de Bellman-Ford-Moore, mais próxima de programação dinâmica, é a que passamos a apresentar.
Defina para cada vértice v o valor dk(v) como sendo o menor comprimento de um passeio de r a v que possui no máximo k arcos, faça dk(v) = INFINITO se não existe um tal passeio.
Claramente, se não existe um ciclo negativo acessível a partir de r, a distância de r a v é igual a dn(v) (na verdade, dn-1(v)).
Algoritmicamente, a função d0 é fácil de ser computada: d0(r) = 0 e d0(v) = INFINITO se v é um vértice distinto de r. Em seguida, d1, d2, d3,... podem ser computadas sucessivamente através da seguinte regra:
dk+1(v) = min{dk(v), min(dk(u)+len(uv): uv arco)}para cada vértice v.
Este método fornece a distância de r a v, para cada vértice v. Como vimos anteriormente não é difícil adaptar o médoto para construir uma árvore de caminhos mínimo com raiz r; se o grafo não possui ciclo negativo é claro.
Teorema 5. Dados um grafo com comprimentos nos arcos e um vértice r tais que todo ciclo acessível a partir de r tem comprimento não-negativo, uma árvore de caminhos mínimos com raiz em r pode ser encontrada em tempo O(n2+nm).
Demonstração. Existem no máximo n iterações e cada uma consome tempo O(n+m).
Um ciclo negativo pode ser determinado de maneira semelhante.
Teorema 6. Dados um grafo com comprimentos nos arcos e um vértice r, um ciclo negativo acessível a partir de r pode ser encontrado em tempo O(n2+nm).
Demonstração. Se dn != dn-1, então dn(v) < dn-1(v) para algum vértice v. Logo, o algoritmo encontra um passei P de r a v de comprimento dn(v), que atravessa n arcos. Como P atravessa n arcos, então P contém um ciclo C. Removendo C de P obtém-se um passeio P' de r a v com menos do que n arcos. Assim,
len(P') >= dn-1(v) > dn(v) = len(P) = len(P') + len(C)e portanto len(C) < 0.
Tendo em vista o algoritmo de programação dinâmica dsecrito acima pode-se facilmente implementar uma função
void bellman-ford-moore (Graph *g, Vertex *r) {...}que recebe um grafo g com comprimentos arbitrários nos arcos e um vértice r e se o grafo não tem um ciclo negativo acessível a partir de r, então devolve um caminho de comprimento mínimo de r a v para cada vértice v do grafo. Eis a função
void
bellman-ford-moore (Graph *g, Vertex *r)
{
Vertex *u0 = g->vertices;
Vertex *un = g->vertices + g->n;
long passo;
for (u = u0; u < un; u++)
{
u->dist = infinito;
u->pred = NULL;
}
r->dist = 0;
for (passo = 0; passo < n; passo++)
{
for (u = u0; u < un; u++)
{
if (u->dist != infinito)
{
Arc *a;
for (a = u->arcs; a; a = a->next)
{
Vertex *v = a=>tip;
long d = u->dist + a->len;
if (v->dist > d)
{
v->dist = d;
v->pred = u;
}
}
}
}
}
}
Este trecho de código exibe a simplicidade do método. O consumo de tempo da função bellman-ford-moore é O(n2 + nm). Do ponto de vista de consumo de tempo assintótico de pior caso, esta função é tão eficiente quanto a que será implementada neste exercício-programa. Entretanto, a implementação sugerida para este exercício-programa é mais eficiente na prática.
EXERCÏCIO (Análise experimental) : Compare o consumo de tempo do seu exercício-programa com o consumo de tempo da função acima.
Neste exercício-programa você implementará o Algoritmo de Bellman-Ford-Moore para encontrar passeios mínimos em grafos com arcos de comprimentos arbitrários (possivelmente negativos). Você pode escrever o programa em C cru ou em CWEB. Documente corretamente todas as funções do programa.
O programa deve receber como entrada um grafo, um vértices origem e um vértice destino e deve fornecer como saída um passeio mínimo do vértice origem ao vértice destino.
O nome do seu programa deverá ser bellman e poderá ser chamado das seguintes formas (você pode implementar mais funcionalidades de desejar):
O seu programa deve prever pelo menos os seguintes casos, informando o fato ao usuário com uma mensagem conveniente:
Não deixe de incluir algumas funções de auto-teste em seu programa: Se o usuário digitar a opção "-teste", essas funções farão testes em vários pontos do programa. Por exemplo, verificarão se um suposto caminho é de fato um caminho, se uma suposta árvore de caminhos mínimos é de fato uma árvore de caminhos mínimo, etc Se a opção "-teste" estiver ativa, é uma boa idéia exibir a seqüência de vértices sendo examinados.
Sugestões são bem-vindas!
A saída do seu programa deve ser enviada para a saída padrão (stdout).
Os comprimentos dos passeios mínimos encontrados devem ser fornecido, bem como o passeio do vértice origem ao(s) vértice(s) destino(s). Se o programa é chamado com os nomes dos vértices, os passeios mínimos fornecidos na saída devem listar os nomes dos vértices. Caso o programa seja chamado usando os números dos vértices, os passeios fornecidos devem listar os números dos vértices.
Você pode implementar o algoritmo de Bellman-Ford-Moore como uma função em seu programa, de forma a permitir que, no futuro, a mesma função possa ser usada inalterada por outros programas que você escrever, nesta ou em outras disciplinas.
O algoritmo precisa de uma estrutura de dados auxiliar que permita as operações INICIALIZA-FILA, PRIMEIRO-DA-FILA, INSIRA-NA-FILA, e REMOVA-DA-FILA. A fila pode ser implementada como uma lista duplamente ligada com cabeça de vértices (estruturas do tipo Vertex). Como fizemos para o algoritmo de Dijkstra.
Agora, vamos imaginar que um dia você queira usar, ou testar, uma outra estrutura de dados para representar está fila, talvez mais rápida. Levando isso em consideração, o uso da fila em seu programa deve ser de tal forma modularizada que permita, sem necessidade de mudanças na função principal do bellman, que outra estrutura de dados substitua em seu programa as rotinas de fila que você escrever.
Se você está em busca de inspiração, então dê uma olhada no modulo GB_DIJK (gb_dijk.w) do SGB para ver uma implementação do Algoritmo Dijkstra. O módulo MILES_SPAN (miles_span.w) contém uma implementação de uma fila através de um heap.
Copiado do arquivo gb_miles.w:
The subroutine call
The constructed graph will be ``complete''---that is, it will have edges between every pair of vertices---unless special values are given to the parameters max_distance or max_degree. If max_distance!=0, edges with more than max_distance miles will not appear; if max_degree!=0, each vertex will be limited to at most max_degree of its shortest edges.
Um exemplo de uso da função miles pode ser encontrado no módulo MILES_SPAN (miles_span.w), como mostrado abaixo.
#include "gb_miles.h" /* the |miles| routine */
[...]
main(argc,argv)
int argc; /* the number of command-line arguments */
char *argv[]; /* an array of strings containing those arguments */
{@+unsigned long n=100; /* the desired number of vertices */
unsigned long n_weight=0; /* the |north_weight| parameter */
unsigned long w_weight=0; /* the |west_weight| parameter */
unsigned long p_weight=0; /* the |pop_weight| parameter */
unsigned long d=10; /* the |max_degree| parameter */
long s=0; /* the random number seed */
unsigned long r=1; /* the number of repetitions */
char *file_name=NULL; /* external graph to be restored */
@;
while (r--) {
if (file_name) g=restore_graph(file_name);
else g=miles(n,n_weight,w_weight,p_weight,0L,d,s);
if (g==NULL || g->n<=1) {
fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
panic_code); /* panic_code is set nonzero if graph
* generator panics.
* panic_code indica o problema que ocorreu,
* veja gb_graph.w
*/
return -1; /* error code 0 means the graph is too small */
}
Copiado do arquivo módulo GB_RAND (gb_rand.w):
This GraphBase module provides two external subroutines called random_graph and random_bigraph, which generate graphs in which the arcs or edges have been selected ``at random.'' A third subroutine, random_lengths, randomizes the lengths of the arcs of a given graph. The performance of algorithms on such graphs can fruitfully be compared to their performance on the nonrandom graphs generated by other GraphBase routines.[...]
The procedure
If dist_from or dist_to are NULL, the probability distribution is uniform over vertices; otherwise the dist parameter points to an array of n nonnegative integers that sum to 230, specifying the respective probabilities (times 230) that each given vertex will appear as the source or destination of the random arcs.
[...]
Gostaria de destacar que o uso do WEB, segundo o seu criador D. Knuth, tem as seguintes finalidades de
Mudando de assunto, um comentário sobre comentários: ``Antes de cada função [e bloco] diga o que a função [e bloco] faz. Procure responder as perguntas que um usuário faria: que dados essa função recebe? que suposições faz sobre esses dados? que resultados devolve? Não perca tempo tentando dizer como a função faz o que ela faz.''(Paulo Feofiloff) Se o tamanho de seus blocos é razoavelmente pequeno, como deve ser, o conselho é extremamente útil.
Observação. Cópiei o comentário acima da página de grafos do prof. José Augusto
cweave, latex,
ctangle (se você fez em CWEB) e gcc.
meu_prompt> make bellman.texgere o documento bellman.tex correspondente ao seu EP4,
meu_prompt> make bellman.dviproduza o Make.dvi correspondente ao seu EP4,
meu_prompt> make bellman.ccrie o arquivo bellman.c correspondente ao seu EP4, e
meu_prompt> make bellmanproduza o executável de nome bellman correspondente ao seu EP4.
meu_prompt>tar -xvf ep4.tarcrie um diretório que tenha o seu login na rede Linux como nome. Neste diretório devem estar todos os arquivos do seu EP3, inclusive o Makefile que você usou. Se você achar necessários coloque junto um arquivo 00-leia-me, onde você descreve algo que achar necessário: como limitações e bugs no seu programa.