Monday 25 July 2016

Simple Hill Climbing

In this blog, I will be introducing you to the first heuristic algorithm Simple Hill Climbing.
It is relatively simple to implement, making it a popular first choice. Although more advanced
algorithms may give better results, in some situations hill climbing works well.

The algorithm is as follows :

Step 1: Evaluate the initial state. It is also a goal state, then return it and quit.
            Otherwise continue with the initial state as the current state.
Step 2: Loop until a solution is found or until there are no new operators left to be
            applied in the current state :
            (a) Select an operator that has not yet been applied to the current state and
            apply it to produce a new state.
            (b) Evaluate the new state.
                (i)    If it is a goal state, then return it and quit .
                (ii)   If it is not a goal state, but it is better than the
                        current state, then make it the current state.
                (iii)  If it is not better than the current state, then continue
                        in the loop.

Here "evaluate" denotes the heuristic function. It measures the heuristic value of the
node.

This algorithm does not evaluate all the successive nodes at once. The first node that
has the higher heuristic value than the current node is set as the current node.

This picture will clear your doubts.



But, there is a big disadvantage of this algorithm. It cannot traverse back to its
parent and gets stuck at an intermediate node. This intermediate node is known as Local
Maximum.

There are three types of situation which prevents the algorithm to reach the Global
Maximum :

Local Maximum : A local maximum is a state that is better than all its neighbours but
is not better than some other states farther away.

Plateau: A Plateau is a flat area of the search space in which a whole set of
neighbouring states have the same value.

Ridge : A ridge is a special kind of local maximum. It is an area of the search space
that is higher than surrounding areas and that itself has a slope.



To get a clear understanding, I have implemented Simple Hill Climbing algorithm
in the Four Queens Problem. The Four Queens Problem is a problem where four
queens are to be placed in such a way that no queens attack each other in
the 4 x 4 chessboard.

Here is the C# code :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Windows.UI;
using Windows.UI.Xaml.Controls;
using Windows.UI.Xaml.Media;
using Windows.UI.Xaml.Media.Imaging;
using Windows.UI.Xaml.Shapes;
namespace Win81AppSimpleHillClimbing4Queens
{
    public class FourQueensProblem
    {
        private int NumberOfQueensPlaced;
        private bool IsAttacked, IsPlaced;
        private Rectangle[,] Queens, Rects;
        private string Result;
        public FourQueensProblem(Rectangle[,] Queens, Rectangle[,] Rects)
        {
            this.Queens = Queens;
            this.Rects = Rects;
        }
        private void SetIndicatorYellow(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 255, 0));
        }
        private void SetIndicatorGreen(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 0, 255, 0));
        }
        private void SetIndicatorRed(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 0, 0));
        }
        private void SetIndicatorNormal(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 9, 93, 240));
        }
        private bool CheckUpperLeftDiagonalCells(int i, int j)
        {
            bool culdc = false;
            int t;
            if (i == j)
                t = i;
            else if (i < j)
                t = i;
            else
                t = j;
            for (int x = 0; x < t; x++)
            {
                --i;
                --j;
                if (IsQueenPresent(i, j) == true)
                {
                    culdc = true;
                    break;
                }
                else
                    culdc = false;
            }
            return culdc;
        }
        private bool CheckUpperRightDiagonalCells(int i, int j)
        {
            bool curdc = false;
           
            for (int x = 0; x < 3; x++)
            {
                --i;
                ++j;
                if (i >= 0 && j < 4)
                {
                    if (IsQueenPresent(i, j) == true)
                    {
                        curdc = true;
                        break;
                    }
                    else
                        curdc = false;
                }
                else
                {
                    break;
                }
            }
            return curdc;
        }
        private bool CheckUpperTopCells(int i, int j)
        {
            bool cutc = false;
            int t = i;
            for (int x = 0; x < t; x++)
            {
                --i;
                if (IsQueenPresent(i, j) == true)
                {
                    cutc = true;
                    break;
                }
                else
                    cutc = false;
            }
            return cutc;
        }
        //Simple Hill Climbing
        public async Task Solve(int a, int b)
        {
            NumberOfQueensPlaced = 0;
            IsPlaced = true;
            for (int i = 0; i < 4; i++)
            {
                if(IsPlaced == true)
                {
                    for (int j = 0; j < 4; j++)
                    {
                        if (i == a && j < b)
                            continue;
                        else
                        {
                            SetIndicatorYellow(i, j);
                            await Task.Delay(TimeSpan.FromSeconds(1));
                            if (IsQueenAttacked(i, j) == false) //Evaluate
                            {
                                SetIndicatorGreen(i, j);
                                SetQueen(i, j); //set as current state
                                await Task.Delay(TimeSpan.FromSeconds(1));
                                IsPlaced = true;
                                ++NumberOfQueensPlaced;
                                break;
                            }
                            else
                            {
                                SetIndicatorRed(i, j);
                                await Task.Delay(TimeSpan.FromSeconds(1));
                                SetIndicatorNormal(i, j);
                                IsPlaced = false;
                            }
                        }
                    }
                }
                else
                {
                    break;
                }
            }
            if (NumberOfQueensPlaced == 4)
                Result = "Success";
            else
                Result = "Failure";
        }
        public string GetResult()
        {
            return Result;
        }
        //heuristic function
        private bool IsQueenAttacked(int i, int j)
        {
            IsAttacked = false;
           
            if (i == 0)
                IsAttacked = false;
            else if (CheckUpperLeftDiagonalCells(i, j) == true)
                IsAttacked = true;
            else if (CheckUpperTopCells(i, j) == true)
                IsAttacked = true;
            else if(CheckUpperRightDiagonalCells(i, j) == true)
                IsAttacked = true;
            else
                IsAttacked = false;
            return IsAttacked;
        }
        private void SetQueen(int i, int j)
        {
            ImageBrush ib = new ImageBrush();
            ib.ImageSource = new BitmapImage(new Uri("ms-appx:///Assets/chess_piece_queen2.png"));
            Queens[i, j].Fill = ib;
            Queens[i, j].IsTapEnabled = false;
        }
        private bool IsQueenPresent(int i, int j)
        {
            bool IsPresent = false;
            if (Queens[i, j].IsTapEnabled == false)
                IsPresent = true;
            else
                IsPresent = false;
            return IsPresent;
        }
        public void ResetQueens()
        {
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    SetIndicatorNormal(i, j);
                    Queens[i, j].Fill = null;
                    Queens[i, j].IsTapEnabled = true;
                }
            }
        }
    }
}


Here is the video of how it works :



That's the end of this blog. I hope you find it useful. Keep coding.

5 comments:

  1. i want to see a video how it works with n = 6 it look to me like backtraking !?

    ReplyDelete
    Replies
    1. I m not sure if Simple Hill Climbing using 6 Queens is possible or not. But I will give it a try. But if you have any other scenario which can be shown to the user for proper understanding, please do share.

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. hello, may i know what kind of software needed to run this source code? i really need your help, thanks

    ReplyDelete