Is this Hill Climbing Algorithm code?

[Maima Van Persie]

Hello, just wanted to know if the code below is considered hill climbing.

 calcCost (int ArrayOfCities[], const int NUM_CITIES) 
{
	int c = 0;
	for (int i = 0; i < NUM_CITIES; ++i)
	{
		for (int j = i + 1; j < NUM_CITIES; ++j)
		{
			if (ArrayOfCities[j] < ArrayOfCities[i])
			{
				c++;
			}
		}
	}
	return c;
}

void SwapElements (int ArrayOfCities[], int i, int j)
{
	int temp = ArrayOfCities[i];
	ArrayOfCities[i] = ArrayOfCities[j];
	ArrayOfCities[j] = temp;
}

int main()
{
	const int CITIES = 8;
	int iIndex = 1;
	int ArrayOfCities[CITIES];

	for (int i = 0; i < CITIES; ++i)
	{
		cout << "Enter distance for city " << iIndex << endl;
		cin >> ArrayOfCities[i];
		++iIndex;
	}

	int bestCost = calcCost(ArrayOfCities, CITIES);
	int iNewCost = 0, iSwaps = 0;
	while (bestCost > 0) 
	{
		for (int i = 0; i < CITIES - 1; ++i)
		{
			SwapElements(ArrayOfCities, i, i + 1);
			iNewCost = calcCost(ArrayOfCities, CITIES);
			if (bestCost > iNewCost)
			{
				++iSwaps;
				cout << "Performing Swap: " << iSwaps << endl;
				for (int i = 0; i < CITIES; ++i)
				{
					cout << ArrayOfCities[i] << "->";
				}

				cout << "\n";
				bestCost = iNewCost;
			}
			else
			{
				SwapElements(ArrayOfCities, i, i + 1);
			}
		}
	}
	
	cout << "\nFinal Route: \n";
	for (int i = 0; i < CITIES; i++)
	{
		cout << ArrayOfCities[i] << endl;
	}

Thanks!

[Uk Marine]

This does look like a Hill Climbing algorithm to me but it doesn't look like a very good Hill Climbing algorithm. What you wrote is a "Greedy Hill Climbing" algorithm which isn't very good for two reasons:

1) It could get stuck in local maxima.
2) It doesn't always find the best (shortest) path. (I assume you're writing this to solve the salesperson problem)

I think you should look into Stochastic hill climbing instead of basic Hill Climbing if you want a more optimized Hill Climber that finds the shortest route and doesn't get stuck.

Try looking into Simulated Annealing (SA). It's a more optimized version and it is very easy to implement (it's about 10 lines of code total).

Reference: https://en.wikipedia.org/wiki/Simulated_annealing

[Maima Van Persie]

Thank you Marine :) It's nice to see you're still around! :p

I tried to implement the SA but for some reason it couldn't find the shortest route, I'll give it another go.

Thank you again and nice MMA record! xD