Blog # 44 : Hill Climbing (A local Search)

In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution. If the change produces a better solution, an incremental change is made to the new solution, repeating until no further improvements can be found.

For example, hill climbing can be applied to the Traveling Salesman Problem. It is easy to find an initial solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much shorter route is likely to be obtained.

Read more about Hill Climbing Problem

Code:

#include<iostream>
#include<cstdio>
using namespace std;
int calcCost(int arr[],int N){
 int c=0;
 for(int i=0;i<N;i++){
  for(int j=i+1;j<N;j++) if(arr[j]<arr[i]) c++;
 }
 return c;
}

void swap(int arr[],int i,int j){
 int tmp=arr[i];
 arr[i]=arr[j];
 arr[j]=tmp;
}

int main(){
 int N;
 scanf("%d",&N);
 int arr[N];
 for(int i=0;i<N;i++) scanf("%d",&arr[i]);
 int bestCost=calcCost(arr,N),newCost,swaps=0;;
 while(bestCost>0){
  for(int i=0;i<N-1;i++){
   swap(arr,i,i+1);
   newCost=calcCost(arr,N);
   if(bestCost>newCost){
    printf("After swap %d: \n",++swaps);
    for(int i=0;i<N;i++) printf("%d ",arr[i]);
    printf("\n");
    bestCost=newCost;
   }
   else swap(arr,i,i+1);
  }
 }
 printf("Final Ans\n");
 for(int i=0;i<N;i++) printf("%d ",arr[i]);
 printf("\n");
 return 0;
}