Define admissible heuristic with an example. Explain the working mechanism and limitations of hill climbing search.

This answer is restricted. Please login to view the answer of this question.

Login Now

Admissible heuristics are used to estimate the cost of reaching the goal state in a search algorithm. Admissible heuristics never overestimate the cost of reaching the goal state. The use of admissible heuristics also results in optimal solutions as they always find the cheapest path solution.

For a heuristic to be admissible to a search problem, needs to be lower than or equal to the actual cost of reaching the goal.

Admissible heuristic
Source: Hamrocsit

Here is an example:

In the A* search algorithm, the evaluation function (where {\displaystyle n}n is the current node) is:

f(n)=g(n)+h(n)

where

f(n) = evaluation function.

g(n) = cost from start node to current node

h(n) = estimated cost from current node to goal

Here, h(n) gets calculated with the use of the heuristic function. If a non-admissible heuristic was used, it is possible that the algorithm would not reach the optimal solution because of an overestimation in the evaluation function.

 

A hill-climbing algorithm is a local search algorithm that moves continuously upward (increasing) until the best solution is attained. This algorithm comes to an end when the peak is reached.

This algorithm has a node that comprises two parts: state and value. It begins with a non-optimal state (the hill’s base) and upgrades this state until a certain precondition is met. The heuristic function is used as the basis for this precondition. The process of continuous improvement of the current state of iteration can be termed as climbing. This explains why the algorithm is termed as a hill-climbing algorithm.

State-space diagram analysis

A state-space diagram provides a graphical representation of states and the optimization function. If the objective function is the y-axis, we aim to establish the local maximum and global maximum.

If the cost function represents this axis, we aim to establish the local minimum and global minimum. More information about local minimum, local maximum, global minimum, and global maximum can be found here.

The following diagram shows a simple state-space diagram. The objective function has been shown on the y-axis, while the state-space represents the x-axis.

Hill Climbing Algorithm in AI

Image Source: Hamrocsit

A state-space diagram consists of various regions that can be explained as follows;

  • Local maximum: A local maximum is a solution that surpasses other neighboring solutions or states but is not the best possible solution.
  • Global maximum: This is the best possible solution achieved by the algorithm.
  • Current state: This is the existing or present state.
  • Flat local maximum: This is a flat region where the neighboring solutions attain the same value.
  • Shoulder: This is a plateau whose edge is stretching upwards.

Problems with hill climbing

There are three regions in which a hill-climbing algorithm cannot attain a global maximum or the optimal solution: local maximum, ridge, and plateau.

Local maximum

At this point, the neighboring states have lower values than the current state. The greedy approach feature will not move the algorithm to a worse off state. This will lead to the hill-climbing process’s termination, even though this is not the best possible solution.

This problem can be solved using momentum. This technique adds a certain proportion (m) of the initial weight to the current one. m is a value between 0 and 1. Momentum enables the hill-climbing algorithm to take huge steps that will make it move past the local maximum.

Plateau

In this region, the values attained by the neighboring states are the same. This makes it difficult for the algorithm to choose the best direction.

This challenge can be overcome by taking a huge jump that will lead you to a non-plateau space.

Plateau

Image Source: Hamrocsit

Ridge

The hill-climbing algorithm may terminate itself when it reaches a ridge. This is because the peak of the ridge is followed by downward movement rather than upward movement.

This impediment can be solved by going in different directions at once.

Ridge in Hill Climbing

Image Source: Hamrocsit

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .