Referência ao ficheiro dynamicProgramming.cpp

#include "dynamicProgramming.h"
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
#include "../constants.h"
#include "../graph.h"

Diagrama de dependências de inclusão para dynamicProgramming.cpp:

Funções
void	getSolution (vector< vector< int >> &memoTable, int citiesSubset, int endingCity, int numCities, int *cities)
	Discover what is the best solution Dynamic Programming found. Mais...
bool	notIn (int subset, int city)
	Checa se uma cidade não está no subconjunto. Mais...
int	removeCity (int city, int subset)
	Remove uma cidade do subconjunto de cidades. Um subconjunto é uma sequência de bits. Mais...
int	dynamicTSP (vector< vector< int >> &memoTable, double **graph, int citiesSubset, int endingCity, int numCities)
void	initMemoTable (vector< vector< int >> &memoTable, double **graph, int numCities)
	Populate memoTable with know values from the graph. For example, for the empty cities subset (0), if I consider the ending city as 1, then, the cost to pass through this path is the cost to go from city 1 to city 0 that is the starting and ending city. Mais...
int	dynamicTSP (double **graph, int numCities, int *cities)
	Solve the Travelling Salesman Problem using Dynamic Programming. Mais...

Documentação das funções

dynamicTSP() [1/2]

int dynamicTSP	(	vector< vector< int >> &	memoTable,
		double **	graph,
		int	citiesSubset,
		int	endingCity,
		int	numCities
	)

Given a set of cities and an ending city in this set, returns the minimum cost to reach it passing through all cities in the set.

Parâmetros

memoTable	Table were the rows are acessed via an integer number that represents the subset of cities (Ex.: 1110 = 14 would represent a set with cities 1, 2 and 3. Each 1 represent a city in the set) and the columns are also acessed via an integer number that represents the desired ending city. So, memoTable[14][0] will represent the minimum cost to reach city 0 passing through the cities in the subset {1, 2, 3}.
graph	Hamiltonian graph.
citiesSubset	The subset of cities this function will analyze.
endingCity	A city in the subset that will be the last in the path.
numCities	Total number of cities.

Retorna

The minimum cost to reach the endingCity passing through all cities in the citiesSubset.

dynamicTSP() [2/2]

int dynamicTSP	(	double **	graph,
		int	numCities,
		int *	cities
	)

Solve the Travelling Salesman Problem using Dynamic Programming.

Parâmetros

graph	Given graph.
numCities	Number of cities (number of vertices of the graph).
cities	Pointer to an array to store the sequence of cities of the best solution.

Retorna

int The cost of the best solution.

See dynamicTSP() documentation above to understand this table

getSolution()

void getSolution	(	vector< vector< int >> &	memoTable,
		int	citiesSubset,
		int	endingCity,
		int	numCities,
		int *	cities
	)

Discover what is the best solution Dynamic Programming found.

Parâmetros

memoTable	Table were the rows are acessed via an integer number that represents the subset of cities (Ex.: 1110 = 14 would represent a set with cities 1, 2 and 3. Each 1 represent a city in the set) and the columns are also acessed via an integer number that represents the desired ending city. So, memoTable[14][0] will represent the minimum cost to reach city 0 passing through the cities in the subset {1, 2, 3}.
citiesSubset	The subset of cities this function will analyze.
endingCity	A city in the subset that will be the last in the path.
numCities	Total number of cities.
cities	Pointer to an array to store the sequence of cities of the best solution.

initMemoTable()

void initMemoTable	(	vector< vector< int >> &	memoTable,
		double **	graph,
		int	numCities
	)

Populate memoTable with know values from the graph. For example, for the empty cities subset (0), if I consider the ending city as 1, then, the cost to pass through this path is the cost to go from city 1 to city 0 that is the starting and ending city.

Parâmetros

memoTable	Table were the rows are acessed via an integer number that represents the subset of cities (Ex.: 1110 = 14 would represent a set with cities 1, 2 and 3. Each 1 represent a city in the set) and the columns are also acessed via an integer number that represents the desired ending city. So, memoTable[14][0] will represent the minimum cost to reach city 0 passing through the cities in the subset {1, 2, 3}.
graph	Hamiltonian graph.
numCities	Total number of cities.

notIn()

bool notIn	(	int	subset,
		int	city
	)

Checa se uma cidade não está no subconjunto.

Parâmetros

city	Índice da cidade a ser checada. Considerando que a city 0 seria a última à direita (Little Endian).
subset	Subconjunto de cidades. Ex.: subset = 14 = 1110 (cidades 1, 2 e 3)

Retorna

true caso a cidade não esteja no subconjunto. Ex.: notIn(14, 0) = true.

false caso contrário.

removeCity()

int removeCity	(	int	city,
		int	subset
	)

Remove uma cidade do subconjunto de cidades. Um subconjunto é uma sequência de bits.

Parâmetros

city	Índice da cidade a ser removida. Considerando que a city 0 seria a última à direita (Little Endian).
subset	Subconjunto de cidades. Ex.: subset = 14 = 1110 (cidades 1, 2 e 3)

Retorna

int O novo subconjunto com a cidade removida. Ex.: removeCity(2, 14) = 10 = 1010