C++

Forum

 
Why am I getting memory leaks?

closed account (1Afj1hU5)
Hello, I have written a somewhat decent solution for the travelling salesman problem. However, according to the visual leak detector, I have 12 memory leaks and I do not know why! I am freeing all memory in the destructor.

Anyway, here's my code:

Hill Climb Algorithm solution for TSP: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
HillClimbing::HillClimbing()
{}

HillClimbing::~HillClimbing()
{
	int c = 0;
	while (Cities.size() != 0)
	{
		delete Cities[c];
		Cities[c] = nullptr;
		c++;
	}
}

// Hill Climbing Search Algorithm
void HillClimbing::Climb()
{
	m_iBestDistance = iCalculateDistances();
	int iCurrDistance = m_iBestDistance;

	while (true)
	{
		int c = 0;
		int iTemp = iCalculateDistances();
		while (c < Cities.size())
		{
			CNode* temp = Cities.back();
			Cities[Cities.size() - 1] = Cities[c];
			Cities[c] = temp;
			iCurrDistance = iCalculateDistances();

			if (iCurrDistance < m_iBestDistance)
			{
				m_iBestDistance = iCurrDistance;
				break;
			}
			else
			{
				// Swap
				temp = Cities.back();
				Cities[Cities.size() - 1] = Cities[c];
				Cities[c] = temp;
			}
			c++;
		}

		if (iCurrDistance == iTemp)
			break;
	}
}

// Find distance between two Cities
int HillClimbing::iCalcDistance(CNode* x, CNode* y)
{
	int localX = abs(x->GetX() - y->GetX());
	int localY = abs(x->GetY() - y->GetY());

	int iDistance = pow(localX, 2) + pow(localY, 2);

	return (sqrt(iDistance));
}

// Calculate distance between all cities
int HillClimbing::iCalculateDistances()
{
	int iCurrDistance = 0;
	for (unsigned int i = 0; i < Cities.size(); ++i)
	{
		if (i == Cities.size() - 1)
		{
			iCurrDistance == iCalcDistance(Cities[i], Cities[0]);
		}
		else
		{
			iCurrDistance += iCalcDistance(Cities[i], Cities[i + 1]); 
		}
	}
	return iCurrDistance;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
// Pre-processor directives etc...
int main()
{
	srand(static_cast<unsigned int>(time(NULL)));

	HillClimbing ClimbTheHill;
	CNode* newNode = nullptr;
	int iGetDistances = 0;

	for (unsigned int i = 0; i < 10; ++i)
	{
		int X = (rand() % 1000);
		int Y = (rand() % 800);
		newNode = new CNode(X, Y);
		ClimbTheHill.Cities.push_back(newNode);
		ClimbTheHill.Climb();
		ClimbTheHill.SetBestDistance(ClimbTheHill.iCalculateDistances());
		iGetDistances = ClimbTheHill.GetBestDistance();
		cout << "Distance: " << iGetDistances << endl;
	}

	return 0;
}


Please help me find the memory leaks. I must hand in this assignment next week :(

I'm still pretty happy I actually solved the TSP problem though ^^
Last edited on
Peter87 (11179)
Not sure if it has anything to do with your memory leak but I noticed that your destructor has a bug. You are never actually removing any elements from the vector so the loop condition Cities.size() != 0 will stay true forever.

I also spotted a problem on line 71 where you use == instead of +=.
ne555 (10692)
> newNode = new CNode(X, Y);
I doubt that you need pointers in the first place.
Topic archived. No new replies allowed.