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.