Enunciado:
Considerando o transporte coletivo de Curitiba, mais restritamente os Ligeirinhos e seus respectivos Tubos, o obejtivo desse trabalho é desenvolver um sistema capaz de identificar dois melhores caminhos entre dois Tubos:
- o caminho com o menor número de Tubos; e
- o caminho com o menor número de Ligeirinhos.
A entrada deve ser feita pela entrada padrão (stdin). O arquivo será composto por uma linha com os Tubos inicial e final que se deseja procurar o menor caminho, e uma lista de rotas dos Ligeirinhos e seus Tubos, uma por linha, como no exemplo abaixo:
2 12 1 2 3 4 5 # 5 6 2 7 8 # 2 9 10 11 5 12 #
O # no final de cada linha é para facilitar a leitura. Considere que o número do Ligeirinho começa em 1. Este processo já está implementado no arquivo main.c disponibilizado.
A saída deve ser feita pela saída padrão (stdout). O arquivo será composto por duas linhas: a primeira com o caminho composto pelo menor número de Tubos; e a segunda com o caminho composto pelo menor número de Ligeirinhos. Cada Tubo destes caminhos deve ser mostrado entre parênteses e cada Ligeirinho entre “-”. Por exemplo um conteúdo do arquivo de saída válido.
(2)-1-(3)-1-(4)-1-(5)-3-(12) (2)-3-(9)-3-(10)-3-(11)-3-(5)-3-(12)
Solução:
1. Introdução
São inúmeras as estruturas que podem ser representadas através de grafos em nosso cotidiano, e da mesma forma são inúmeras as aplicações - muitas vezes implícitas - de algoritmos que efetuem buscas de determinados dados nestas estruturas.
Uma forma interessante e elucidativa de imaginar um grafo são as possibilidades de percorrimento de rotas reais, tais como estradas, pontes ou linhas de ônibus.
No presente trabalho foi proposto como modelo a utilização do famoso, inovador e sofrido sistema de transporte de Curitiba com suas futurísticas estações tubo. Dentre tantas possíveis conexões, qual o menor caminho e o menor número de conexões que podem ser feitas entre dois tubos do sistema integrado?
2. Métodos e Discussões
Utilizou-se a linguagem C e o compilador GCC para a elaboração de um programa que recebe uma listagem de dados que consistem no ponto inicial, final e as rotas dos ônibus.
Toma-se o custo de percorrimento como constante entre cada aresta da estrutura, o que é especialmente ideal ao considerar as voltas e desvios de algumas linhas de ligeirinhos. Justamente esta consideração é a que promove o uso do algoritmo de busca em largura, pois a solução encontrada será sempre a melhor [3], além de ser mais adequada para grafos menores [2].
Aproveitaram-se as funções da biblioteca fornecida pela especificação do trabalho, sendo que o esforço de implementação girou mais sobre as funções `caminho_minimo_tubos` e `caminho_minimo_linhas`.
Uma forma conveniente de tratar este conjunto de dados é através da construção de uma lista de adjacência [2] para então empregar a busca. Esta busca funciona de modo exastivo examinando todas as possibilidades de caminho nível a nível [1].
busca em largura (Início , Alvo) entra (Fila, Início) enquanto (a Fila não for vazia) Nó := sai (Fila) se (Nó = Alvo) retorna Nó para cada (Filho em Expande(Nó)) se (não visitado(Filho)) marca como visitado (Filho) entra (Fila, Filho)
Já para o menor número de conexões de um ponto a outro empregou-se um algoritmo de cálculo do fecho transitivo. Novamente faz-se um processo exaustivo que detecta todos os vértices que podem ser alcançados a partir do vértice de origem, e os percorre de acordo com a função já utilizada anteriormente.
Retorna-se então a menor rota que passa pelo menor número de trocas.
Como o trabalho deve utilizar a função de escrita de lista já proposta, foi feita uma segunda função para inserção de elementos na lista, `insere_final`. Esta função extra percorre toda a lista no ato da inserção para viabilizar a utilização da `escreve_caminho`, colocando os elementos na ordem devida.
3. Conclusão:
O algoritmo de busca em largura mostra-se eficiente para a tarefa de encontrar o menor número de linhas e tubos entre dois pontos de Curitiba. Suposições ideais são feitas para simplificar o processo e, dependendo da cisrcusntância, é empregado o encontro do fecho transitivo através de `calcula_fecho`.
O que comumente é feito em distâncias reais é a conversão das distâncias do grafo em valores unitários, sempre iguais, e desta maneira pode-se empregar o algoritmo de busca em largura de maneira eficiente e uniforme para encontrar o menor caminho [7].
Embora talvez para uma aproximação real este algoritmo possa não ser o mais adequado, a circunstância é válida devido ao exercício de trabalhar com buscas em árvores de dados, servindo também de uma introdução para a ampliação de conceitos de busca em grafos.
Código fonte: Download.
Referências:
[1] Wikipedia: Breadth-first search - Acessado em 06/12/09
[2] SEDGEWICK, Robert - Algorithms in C
[3] Prof. Paulo Feofiloff: Grafos: Busca em largura - Acessado em 06/12/09
[4] Prof. Paulo Feofiloff: Algoritmos para grafos: listas de adjacência - Acessado em 06/12/09
[5] INF-UFSC: Busca em grafos - Acessado em 06/12/09
[6] Wikipedia: Floyd–Warshall algorithm
[7] Wikipedia: Uniform-cost search