What's wrong with my hill climbing? (salesman problem)

[1Afj1hU5]

Hello, I have decided to try and solve one of the most common problems, that is the travelling salesman problem. For some reason my algorithm is not giving me the correct path from lowest distance to highest. I don't know where I'm going wrong but I'd gladly appreciate your input.

Thank you.

Here's my attempt:

// Function Prototypes
int CalculateDistance(int distanceArray[], int);
void Swap(int[], int, int);

int main()
{
	srand(static_cast<unsigned int>(time(NULL)));

	int iRand = 0;
	int iOldCost = 0;
	int iNewCost = 0;
	int iSwaps = 0;

	const int NUM_CITIES = 6;
	int cities[NUM_CITIES];
	string citiesNames[NUM_CITIES];

	citiesNames[0] = "New York";
	citiesNames[1] = "Auckland";
	citiesNames[2] = "New Delhi";
	citiesNames[3] = "Rio de janeiro";
	citiesNames[4] = "New Orleans";
	citiesNames[5] = "Barcelona";

	for (int i = 0; i < NUM_CITIES; ++i)
	{
		iRand = rand() % 100 + 1;
		cities[i] = iRand;
	}

	cout << "List of cities and their distances: \n";
	for (int i = 0; i < NUM_CITIES; ++i)
	{
		cout << citiesNames[i] << "		: " << cities[i] << "km." << endl;
	}

	iOldCost = CalculateDistance(cities, NUM_CITIES);

	while (iOldCost > 0)
	{
		for (int i = 0; i < NUM_CITIES - 1; ++i)
		{
			Swap(cities, i, i++);
			iNewCost = CalculateDistance(cities, NUM_CITIES);

			if (iOldCost > iNewCost)
			{
				++iSwaps;

				printf("After swap %d: \n", iSwaps);
				for (int i = 0; i < NUM_CITIES; ++i)
				{
					cout << cities[i] << endl;
					iOldCost = iNewCost;
				}
			}
			else
			{
				Swap(cities, i, i++);
			}
		}
	}

	cout << "\nOur journey will look something like this: \n";
	for (int i = 0; i < NUM_CITIES; ++i)
	{
		cout << cities[i] << "km." << endl;
	}

	int iTemp = 0;
	cin >> iTemp;
	return 0;
}

int CalculateDistance(int distanceArray[], int num)
{
	int c = 0;

	for (int i = 0; i < num; ++i)
	{
		for (int j = i + 1; j < num; ++j)
		{
			if (distanceArray[j] < distanceArray[i])
			{
				c++;
			}
		}
	}
	return c;
}

void Swap(int myArray[], int x, int y)
{
	int iTemp = myArray[x];
	myArray[x] = myArray[y];
	myArray[y] = iTemp;
}

[Peter87]

The problem is Swap(cities, i, i++);, for two reasons.

1. i is modified so if you go into the else and swap again you will not swap the same cities.

2. The evaluation of arguments are unsequenced. You want the third argument (i++) to be evaluated first so that the second argument (i) evaluates to the new value of i but that's not a safe assumption to make. The code has undefined behaviour so anything is allowed to happen.

I don't think you need to change i at all here. Instead of i++ you probably should use i+1.