Seguinte: Módulo de filas de
Acima: Estrutura da implementação
Anterior: Módulo do algoritmo de
Módulo do algoritmo de heurística: heuristica.c
Presente apenas na implementação heuristica. As rotinas deste módulo são as seguintes:
- procCaminhoHeuristica( ): É o ponto de entrada para o código do módulo. Esta
rotina inicializa as variáveis temporárias, executa o corpo principal da heurística -
descrita na resposta à questão 2.b, tópico ``Sobre o algoritmo'' -, controla os resultados
obtidos ao longo do tempo (detectando os melhores resultados à medida em que são
conseguidos) e aplica o algoritmo de melhoria por intercâmbio de vértices;
- calcDistCaminho( ): Rotina auxiliar que calcula o custo de um dado caminho,
compara-o com o melhor caminho até o momento e, se for o caso, o substitui;
- heuristProcuraCicloTotal( ): Dado um determinado conjunto de arestas - que
corresponde às arestas conseguidas por uma Árvore Geradora Mínima mais as arestas que são
um matching guloso dos vértices ímpares da árvore -, esta rotina devolve uma
seqüência de vértices que corresponde a um ciclo curto-circuitado envolvendo todas essas
arestas. A obtenção desse ciclo curto-circuitado é o coração da heurística proposta;
- heuristProcuraCiclo( ): Rotina auxiliar à heuristProcuraCicloTotal( ),
esta procura um ciclo usando o conjunto de arestas descrito no item anterior, mas não
garante a obtenção de um ciclo total, isto é, usando todos os vértices. Dessa maneira, esta
rotina é chamada várias vezes para incluir cada vez mais arestas no ciclo descoberto até o
momento, até que todos os vértices participam do caminho, compondo um resultado para o
problema;
- Rotinas Vdpq*( ): Conjunto de rotinas que implementa a interface de fila de
prioridades de vértices, usada pelo algoritmo;
- Rotinas Adpq*( ): Conjunto de rotinas que implementa a interface de fila de
prioridades de arestas, usada pelo algoritmo.
Seguinte: Módulo de filas de
Acima: Estrutura da implementação
Anterior: Módulo do algoritmo de
VilarNt
2003-06-20