fbruta.c

001   #include "fbruta.h"
002   #include <stdio.h>
003   #include <string.h>
004   #include <limits.h>
005   #include <stdlib.h>
006   
007   
008   void fbrutaRecursa(TPcvData *PcvData)
009   {
010       // Obtém o vértice 'u', que é o último no caminho feito até agora
011       int u = PcvData->anCaminho[PcvData->nVisitados - 1];
012       int v;
013   
014       // Laço para procurar pelo vértice seguinte
015       for (v = 0; v < PcvData->nNumVertices; v++) {
016           // Prossegue apenas se encontrar vértice branco
017           if (PcvData->acCorVert[v] != COR_BRANCO) continue;
018   
019           // Encontrou um vértice 'v' não visitado:  Pinta-o de cinza
020           PcvData->acCorVert[v] = COR_CINZA;
021           // Registra o novo vértice no caminho pesquisado
022           PcvData->anCaminho[PcvData->nVisitados] = v;
023           // Adiciona o custo da aresta (u,v) no total percorrido
024           PcvData->nDistTotal += PcvData->anDist[u][v];
025   
026           // Se esta recursão for a mais profunda possível
027           // (isto é, todos os vértices já foram visitados)...
028           if (PcvData->nVisitados == PcvData->nNumVertices - 1) {
029               // Adiciona o custo da aresta que fecha o ciclo
030               int nDistTotal = PcvData->nDistTotal +
031                   PcvData->anDist[v][PcvData->anCaminho[0]];
032   
033               // Se a distância percorrida neste ciclo for menor
034               // do que a encontrada até agora...
035               if (PcvData->nMinDistTotal > nDistTotal) {
036                   // Registra esta distância como a menor descoberta até agora
037                   PcvData->nMinDistTotal = nDistTotal;
038                   // Armazena o caminho percorrido
039                   memcpy(&PcvData->anMinCaminho, &PcvData->anCaminho,
040                       PcvData->nNumVertices * sizeof(int));
041               }
042   
043           // Senão -- este não é o nível mais profundo de recursão
044           // (ainda há vértices brancos)
045           } else {
046               // Incrementa o número de vértices visitados para entrar em nova recursão
047               PcvData->nVisitados++;
048               // Chama nova recursão
049               fbrutaRecursa(PcvData);
050               // Restaura o número de vértices visitados
051               PcvData->nVisitados--;
052           }
053   
054           // Decrementa o custo da aresta (u,v), pois vamos buscar um novo 'v'
055           PcvData->nDistTotal -= PcvData->anDist[u][v];
056           // Pinta o vértice 'v' de branco
057           PcvData->acCorVert[v] = COR_BRANCO;
058       }
059   }
060   
061   
062   // Procura a melhor solução para o Problema do Caixeiro Viajante
063   // utilizando força bruta (testando todos os caminhos possíveis)
064   void procCaminhoFBruta(TPcvData *PcvData)
065   {
066       // Inicializa o vetor de cores:  todos os vértices iniciam na cor branca
067       memset(&PcvData->acCorVert, COR_BRANCO, PcvData->nNumVertices *
068           sizeof(char));
069   
070       // Registra que a maior distância encontrada até agora é "infinito"
071       PcvData->nMinDistTotal = INT_MAX;
072   
073       // A recursão é iniciada pelo vértice 0:
074       // Pinta o vértice '0' de cinza
075       PcvData->acCorVert[0] = COR_CINZA;
076       // Registra o primeiro passo do caminho pesquisado
077       PcvData->anCaminho[0] = 0;
078       // Registra quantos vértices foram visitados
079       PcvData->nVisitados = 1;
080       // Registra a distância total percorrida até agora
081       // (0, pois não passou por nenhuma aresta)
082       PcvData->nDistTotal = 0;
083   
084       // Inicia a recursão
085       fbrutaRecursa(PcvData);
086   }