Em consonância com a expansão do mercado tecnológico, a complexidade dos problemas computacionais tem aumentado, o que implicou na busca de máquinas mais potentes para processá-los. Entretanto, tais recursos são limitados e por isso devem ser utilizados de maneira eficiente. Tendo em vista esta problemática e com o objetivo de destacar a importância do projeto e análise de algoritmos, o grupo propôs uma análise de quatro soluções distintas para um problema clássico da Ciência da Computação, o Problema do Caixeiro Viajante (Traveling Salesman Problem). Os algoritmos utilizados foram:
- Brute Force
Gera permutações de todos os caminhos possíveis e verifica dentre eles qual forma um ciclo e dos que formam um ciclo qual tem a menor distância
- Branch and Bound
Gera uma árvore com todos os caminhos testando todas as ramificações parciais e podando aquelas que já são maiores que a solução atual.
- Dynamic Programming
Resolve problemas com caminhos hamiltonianos menores e vai comparando essas soluções para gerar soluções com caminhos maiores.
- Genetic Algorithm
Gera uma população inicial de indivíduos onde cada indivíduo é um circuito hamiltoniano e, a partir dessa população, realiza mutações nos indivíduos um certo números de vezes. O melhor indivíduo será o resultado.
Como o problema envolve naturalmente a estrutura de dados Grafo, todos os algoritmos a usam. Neste trabalho criamos uma classe TSP (Traveling Salesman Problem) que serve como uma classe abstrata e classe base para os outros algoritmos que também são representados por classes.
Grafo - Representado por uma matriz VxV de números flutuantes onde V é o número de vértices. Vetor - Um vetor de inteiros de V+1 elementos que representa o caminho a ser percorrido no grafo e também salva o caminho percorrido de menor peso.
O Brute Force gera um array com V+1 vértices e permuta todas as suas V-1 posições, sempre começando do vértice 0 e terminando no vértice 0.
A função permutation(int array[], int size) irá gerar permutações dos vértices entre a posição 1 a V. E na hora de percorrer o caminho é adicionado vértice 0 no final do array.
Ex: 0 1 2 3 0.
Esses seriam os vértices que seriam percorridos para um grafo de 3 vértices.
- 0 1 2 3 0
- 0 1 3 2 0
- 0 2 3 1 0
- 0 2 1 3 0
- 0 3 1 2 0
- 0 3 2 1 0
Cada um desses arrays significam um caminho a ser percorrido no grafo e todos são percorridos realizando a soma de cada peso entre um vértice e outro.
A função walkThePath(int[] array) é responsável por fazer essa computação. Ela chama a função sumPath(int[] array) que retorna a soma do caminho atual e então verifica se a soma atual é menor do que a menor soma já encontrada, se caso for a menor a walkThePath também guarda esse array de cidades para mostrar o menor caminho depois.
Função permutation(int array[], int size)
void BruteForce::permutation(int array[], int size)
{
if (size == 1) // final da permutação
{
walkThePath(array);
return;
}
for (int i = 1; i < size; i++)
{
permutation(array, size - 1);
if (size % 2 == 1)
swap(array[1], array[size - 1]);
else
swap(array[i], array[size - 1]);
}
}Essa função é a principal do paradigma do Brute Force é ela que gera as permutações de todos os caminhos que serão percorridos. Ela deixa fixo o último número do array e permuta os N-2 números restantes. Essa é uma adaptação do algoritmo de Heap que foi proposto por B.R Heap em 1963. Na nossa versão começamos o loop do segundo elemtno do array, deixando assim o primeiro elemento do array fixo e por isso a permutação é entre os outros N-2 elementos.
Similar ao Brute Force, o Branch and Bound gera uma árvore de recursão com diversos caminhos para seguir. Entretanto, não gera todas as possibilidades para descobrir o melhor caminho, mas, a cada cidade que avança, o algoritmo compara se a soma das arestas passadas é maior que o melhor caminho atual. Caso o teste seja verdadeiro, o cálculo é abortado e o programa testa outro caminho na árvore de recursão descartando, assim, vários outros testes desnecessários.
A função principal do algoritmo possui os seguintes parâmetros:
double **matriz: ponteiro para a matriz de adjacência(grafo);double parcial: tamanho do caminho parcial;int nivel: nível atual da árvore de recursão;int *caminho_parcial: ponteiro para vetor com os vértices do caminho atual na árvore de recursão;bool *visitados: ponteiro para vetor que representa vértices visitados;
O algoritmo começa inicializando os vetores caminho_parcial e visitados. Logo após, passamos todos os parâmetros para
o método principal. Sendo que parcial é inicializado com 0 e o nivel se inicia com 1. Assim, finalizadas as
inicializações, podemos começar a analisar o método.
A ideia é bastante simples. No início do método, é testado se o algoritmo chegou ao último nível da árvore de recursão. Caso
seja verdadeiro, se houver caminho direto até a raiz, somamos este caminho ao caminho parcial e testamos se esta soma é menor
que a menor distância anterior. Se este teste também for verdadeiro, o vetor com o melhor caminho é atualizado e o seu custo
é armazenado para futuras comparações. Veja abaixo o trecho:
if (nivel == vertices)
{
if (matriz[nivelAnterior][caminhoParcial[0]] != UNDEFINED)
{
double resultadoAtual =
parcial + matriz[nivelAnterior][caminhoParcial[0]];
if (resultadoAtual < this→distance)
{
atualizarMelhorCaminho(caminhoParcial);
this->distance = resultadoAtual;
}
}
}Caso o algoritmo ainda não estiver no fim da árvore, o primeiro “if” será falso e, assim, cairemos no “else”. Este bloco
possui um “for” que passa por todos os vértices ainda não visitados. Em sua estrutura, temos uma chamada recursiva que é
requisitada caso o custo do caminho parcial até o momento, parcial, seja menor que o custo do menor caminho atual. Porém,
se esse teste for falso, ou seja, se o percorrido até este momento já é maior que o menor caminho armazenado, o teste
falha e, portanto, descartamos computações desnecessárias.
Veja o código abaixo:
for (int x = 0; x < vertices; x++)
{
if (!visitados[x] && matriz[nivelAnterior][x] != UNDEFINED)
{
parcial += matriz[nivelAnterior][x];
if (parcial < this→distance)
{
caminhoParcial[nivel] = x;
visitados[x] = true;
branchAndBound(matriz, parcial, nivel + 1, caminhoParcial, visitados);
}
parcial -= matriz[nivelAnterior][x];
memset(visitados, false, vertices);
for (int y = 0; y < nivel; y++)
visitados[caminhoParcial[y]] = true;
}
}Como a estrutura de dados e a forma de memoização desse algoritmo são mais peculiares, vou usar algumas imagens para ilustrar melhor o que foi feito.
No caso dessa imagem, g(i, S) é uma função que calcula o menor custo possível para
chegar no vértice i passando por todos os vértices do subconjunto S.
O truque da programação dinâmica aqui é que, por exemplo, o custo mínimo para chegar
no vértice 1, passando pelos vértices 2 e 3, ou seja, g(1, {2, 3}) é igual ao
mínimo entre:
I) chegar no vértice 2, passando pelo vértice 3 e do vértice 2 ir para o 1 ou
II) chegar no vértice 3, passando pelo vértice 2 e do vértice 3 ir para o 1
porém "chegar no vértice 2, passando pelo vértice 3" é exatamente g(2, {3})
e "chegar no vértice 3, passando pelo vértice 2" é exatamente g(3, {2}), ou seja,
ao guardar a solução de problemas menores, consigo resolver problemas maiores.
No início do algoritmo eu já calculo o custo de todos caminhos que terminam em um
vértice v qualquer e não precisam de passar por nenhum outro, ou seja, são chamadas
à função g do tipo: g(v, Ø). Nesse caso, o custo é o custo de sair de v e ir para
o vértice inicial que é o 0. Ou seja, é a aresta entre esses dois vértices.
Faço isso nesse trecho de código, onde memoTable[A][B] significa g(B, A).
for (size_t city = 1; city < numCities; city++)
memoTable[0][city] = graph[city][0];Em memoTable, eu indexo as linhas pelo subconjunto e as colunas pelo vértice final.
Além disso, eu represento os subconjuntos por números inteiros que na verdade são
pensados como números binários. Ou seja, ao ler 14, você deve imaginar 1110. E esse
número indica quais cidades estão nesse subconjunto. Nesse caso, as cidades 1, 2 e 3.
Ou seja, memoTable[14][0] indicaria o custo mínimo para chegar no vértice 0 passando
pelas cidades 1, 2 e 3
Esse trecho é a execução do algoritmo de fato:
int dynamicTSP(vector<vector<int>> &memoTable, double **graph, int citiesSubset,
int endingCity, int numCities)
{
int newSubset = removeCity(endingCity, citiesSubset);
int bestCost = MAX, cost = memoTable[newSubset][endingCity];
if (cost != UNDEFINED) return cost;
for (int newEndingCity = 1; newEndingCity < numCities; newEndingCity++)
{
if (notIn(newSubset, newEndingCity)) continue;
cost = dynamicTSP(memoTable, graph, newSubset, newEndingCity, numCities) +
graph[newEndingCity][endingCity];
if (cost < bestCost) bestCost = cost;
}
return memoTable[newSubset][endingCity] = bestCost;
}Ao receber um subconjunto de cidades (citiesSubset) e uma cidade final (endingCity),
eu removo essa endingCity do subconjunto e vejo se já não existe o custo de chegar
na endingCity passando pelo novo subconjunto gerado (newSubset) na memoTable. Caso
sim eu posso retornar esse valor. Caso não, eu faço uma repetição por todas as cidades
desse novo subconjunto (newSubset) e vou escolhendo cada uma delas para ser a nova
cidade final (newEndingCity) do subconjunto. A newEndingCity que gerar o custo
mínimo será a definitiva.
Esses dois trecho de código já explicam o funcionamento do algoritmo em geral. O primeiro trecho é o que eu considero como um indivíduo no algoritmo genético.
/**
* Chromosome
*/
class Individual
{
public:
/** Genes */
vector<int> cities;
int pathCost = -1;
};Já o segundo trecho é a execução do algoritmo de fato.
int numVertices = this->graph.getV();
int numGenerations = numVertices * numVertices;
int populationSize = numGenerations / 4;
if (populationSize < 1) populationSize = 1;
int mutationRate = 50;
createRandomPopulation(population, populationSize, numVertices, bestPath);
for (int generationNum = 1; generationNum <= numGenerations; generationNum++)
mutatePopulation(population, mutationRate, numVertices, bestPath);Inicialmente, calculo um número de gerações, o tamanho da população de indivíduos e a taxa de mutação. Daí eu crio uma população inicial de forma aleatória e depois começa a mutar a população de acordo com a taxa de mutação. Ao mutar a população inteira eu passo para a próxima geração. Um detalhe importante é que a função que muta um indivíduo faz várias tentativas até que ele se torne melhor do que era antes. No caso desse algoritmo, coloquei o número máximo de tentativas como 3.
O formato de entrada e saída de dados, bem como decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.
A primeira linha da entrada é um número N (3 <= N <=15) que representa o número de vértices do grafo. As N próximas linhas recebem cada uma um valor X aleatório (0 <= X <=1000) e um valor Y aleatório (0 <= Y <=1000) que representam as coordenadas dos vértices. Esse padrão se repete 15 vezes para cada valor de N com N variando de 3 em 3 até chegar em 15.
A saída de de dados é um arquivo no formato .csv com os dados separados por ponto e virgula. A primeira linha contém os nomes dos paradigmas. Existem 5 colunas, cada valor das colunas representam a média de tempo para execução do paradigma para N cidades. Essa saída é colocada no Excel para gerar os gráficos comparativos e individuais de cada paradigma.
| Sistema Operacional | Compilador | Editor de Código |
|---|---|---|
| Windows/Linux | gcc ou g++ que suporte c++14 | Visual Studio Code |
Para mais informações Linux/Mac:
./run.sh --help
Para mais informações Windows, caso não tenha ativado a execução de scripts no PowerShell,
abra-o e rode Set-ExecutionPolicy Bypass Process.
./run.ps1 --help
Rodando todos os algoritmos Linux/Mac:
./run.sh branch brute dynamic genetic
Rodando todos os algoritmos Windows (PowerShell):
./run.ps1 branch brute dynamic genetic
sumPath
double TSP::sumPath(int *array, int arraySize)
{
double sum = 0.0;
int weight;
double **graphMatrix = this->graph.getGraph();
for (int i = 0, j = 1; j < arraySize; i++, j++)
{
weight = graphMatrix[array[i]][array[j]];
if (weight != UNDEFINED)
sum += weight;
else
return -1; // O caminho não gera um ciclo hamiltoniano (faltou aresta)
}
return sum;
}Operação relevante: Soma dos pesos
Essa função percorre um array de inteiro do elemento 0 até o N-2.
Melhor caso: Todos os testes if(weight != UNDEFINED) darão falso, ou seja, todas as arestas entre dois vértices não foram preenchidas. Nesse caso nenhuma operação será realizada.
Pior caso Todos os testes f(weight != UNDEFINED) darão verdadeiro, ou seja, todas as arestas entre dois vérticesforam preenchidas. Nesse caso N-2 operações serão realizadas.
Função de complexidade: F(n) = N-2
Complexidade: O(n)
void BruteForce::walkThePath(int *array)
{
int V = this->graph.getV();
double sum = sumPath(array);
if (sum == -1) return;
if (sum < this->distance)
{
this->distance = sum;
// preenche o vetor de cidades com o maior caminho
for (int i = 0; i < V; i++)
this->cities[i] = array[i];
}
}Operação relevante: Atribuição de elementos no array cities
Pior caso: A soma do caminho atual será menor do que a menor distância já calculada dos caminhos do grafo. Então será feita N atribuições no vetor cities.
Melhor casoA soma do caminho atual não será menor do que a menor distância já calculada dos caminhos do grafo. Então será feita 0 atribuições no vetor cities.
Função de complexidade: F(n) = n
Complexidade: O(n)
permutation
void BruteForce::permutation(int array[], int size)
{
if (size == 1) // final da permutação
{
walkThePath(array);
return;
}
for (int i = 1; i < size; i++)
{
permutation(array, size - 1);
if (size % 2 == 1)
swap(array[1], array[size - 1]);
else
swap(array[i], array[size - 1]);
}
}Operação relevante: Troca de elemento no array
Essa função deixa fixo o último elemento do array e permuta os outros N-2 elementos. Sempre que ele encontra todas as permutações dos N-2 elementos que estão com o atual último elemento fixo esse elemento é trocado e novamente é gerada N-2 permutações, esse processo se repete até que todos os N-1 (menos o 0) elementos tenham sido fixados na última posição.
Melhor e pior caso: No caso dessa função o pior caso e o melhor caso sempre serão iguais, pois sempre ele irá gerar n-1 x (n-2)! operações.
Função de complexidade: F(n) = n-1 x (n-2)!
Complexidade: O(n!)
void BranchAndBound::atualizarMelhorCaminho(int *caminhoParcial)
{
int vertices = this->graph.getV();
for (int x = 0; x < vertices; x++)
this->cities[x] = caminhoParcial[x];
}Operação relevante: atribuição ao array cities
Em todos os casos: Percorre todo o vetor com o melhor caminho atualizando-o
Função de complexidade: F(n) = n
Complexidade: O(n)
void BranchAndBound::run()
{
int vertices = this->graph.getV();
int caminhoParcial[vertices + 1];
bool visitados[vertices];
double **matriz = this->graph.getGraph();
this->distance = MAX;
memset(caminhoParcial, -1, vertices + 1);
memset(visitados, false, vertices);
visitados[0] = true;
caminhoParcial[0] = 0;
branchAndBound(matriz, 0, 1, caminhoParcial, visitados);
}Operação relevante: Atribuição para os vetores
Em todos os casos: Inicializa dois vetores de tamanho n necessários para o algoritmo.
Função de complexidade: F(n) = 2*n + 2
Complexidade: O(n)
void BranchAndBound::branchAndBound(double **matriz, double parcial, int nivel,
int *caminhoParcial, bool *visitados)
{
int vertices = this->graph.getV();
int nivelAnterior = caminhoParcial[nivel - 1];
if (nivel == vertices && matriz[nivelAnterior][caminhoParcial[0]] != UNDEFINED) {
double resultadoAtual = parcial + matriz[nivelAnterior][caminhoParcial[0]];
if (resultadoAtual < this->distance) {
atualizarMelhorCaminho(caminhoParcial);
this->distance = resultadoAtual;
}
}
else
{
for (int x = 0; x < vertices; x++) {
if (!visitados[x] && matriz[nivelAnterior][x] != UNDEFINED) {
parcial += matriz[nivelAnterior][x];
if (parcial < this->distance) {
caminhoParcial[nivel] = x;
visitados[x] = true;
branchAndBound(matriz, parcial, nivel + 1, caminhoParcial,
visitados);
}
parcial -= matriz[nivelAnterior][x];
memset(visitados, false, vertices);
for (int y = 0; y < nivel; y++)
visitados[caminhoParcial[y]] = true;
}
}
}
}Operação relevante: Comparações
Pior caso: Executará como o Brute Force para um caso onde nenhuma parte da árvore de
recursão será descartada. Ou seja, percorrerá toda a árvore e testará todas
as permutações de caminhos possíveis. Assim, cada chamada da recursividade,
haverá 3 comparações. Portanto, a função de complexidade será F(n) = 3*n!
ou O(n!).
-Função de complexidade: T(n) = T(n-1)*O(n) + O(n²)
-Ordem de complexidade: T(n) = O(n!)
Melhor caso: O melhor caminho é encontrado na primeira descida até o final da árvore. Portanto, na volta desta
recursividade, todos os outros testes serão descartados com uma única comparação.
-Função de complexidade: T(n) = O(n) + (n-1)
-Ordem de complexidade: T(n) = O(n)
A análise acima desconsidera que a programação dinâmica consegue reaproveitar soluções de problemas menores para resolver problemas maiores. A análise de complexidade real do algoritmo não pode ser feita pelo código. É uma análise matemática. A ideia é descobrir quantos subproblemas existem, pois, ao resolver todos os subproblemas, as novas chamadas recursivas são todas O(1). A quantidade máxima de subproblemas é O(n * 2^n). Como é necessário fazer isso n vezes na primeira chamada, o tempo total é O(n² * 2^n).
Descrever os testes realizados, mostrando a saída do programa além de eventuais análises e comparações que foram solicitadas no enunciado.
Em todos os gráficos, o eixo x é o número de cidades e o eixo y é o tempo gasto em milisegundos.
O trabalho foi muito bom para o grupo. Pudemos melhorar nossas habilidades na programação de algoritmos e também melhorar o nosso raciocínio lógico.
As principais dificuldades que tivemos foram nos algoritmos de Branch and Bound e Dynamic Programming. Porém, foi muito interessante tentar enxergar a sobreposição de problemas no algoritmo de Dynamic Programming. Além disso, pensar em como guardar os resultados dos subproblemas também foi bem interessante.
https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
https://www2.cs.sfu.ca/CourseCentral/125/tjd/tsp_example.html
https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and-bound-2/
https://www.youtube.com/watch?v=1FEP_sNb62k
https://www.geeksforgeeks.org/traveling-salesman-problem-using-genetic-algorithm/
https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
https://www.youtube.com/watch?v=Q4zHb-Swzro
https://www.youtube.com/watch?v=cY4HiiFHO1o
https://www.youtube.com/watch?v=udEe7Cv3DqU
https://www.youtube.com/watch?v=-JjA4BLQyqE
https://www.youtube.com/watch?v=JE0JE8ce1V0
https://www.geeksforgeeks.org/measure-execution-time-with-high-precision-in-c-c/
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/NPcompleto.html