Hill Climbing Search Solved Example using Local and Global Heuristic Function by Dr. Mahesh Huddar
Summary
TLDRThis video tutorial explains the Hill Climbing algorithm's application in transitioning from an initial state to a goal state using both local and global heuristic functions. It illustrates the process with a block-stacking example, highlighting the limitations of local heuristics leading to a local maximum and demonstrating how global heuristics can guide the algorithm to the optimal solution. The explanation clarifies the use of heuristic functions in overcoming local maxima and achieving the goal state.
Takeaways
- π The video discusses the application of the hill climbing algorithm using both local and global heuristic functions to transition from an initial state to a goal state.
- π The example given involves moving blocks labeled A, B, C, and D to their correct positions on top of each other to reach the goal state.
- π€ Local heuristic functions consider immediate consequences and reward blocks that are resting on the correct block with a +1, while incorrectly placed blocks receive a -1.
- π Global heuristic functions take into account the overall support structure of each block, rewarding correct placements with +1 and penalizing incorrect ones with -1.
- π’ The start state's value is calculated by assigning points based on the local heuristic function, resulting in a total value of 0 for the given example.
- π― The goal state's value is calculated as +4 using the local heuristic function, indicating all blocks are correctly placed.
- π« A disadvantage of using local heuristic functions is the potential to reach a local maximum, where no further improvement is possible, as demonstrated when moving block D.
- π To overcome local maxima, the video switches to using a global heuristic function, which considers the entire structure of block placement.
- π The initial state's value using the global heuristic function is -6, indicating that none of the blocks are correctly placed.
- π By applying operators and moving blocks according to the global heuristic function, the algorithm successfully reaches the goal state with a value of +6.
- π The video illustrates the process of using hill climbing with heuristic functions to find a solution path from the start state to the goal state in a block puzzle scenario.
Q & A
What is the Hill Climbing algorithm?
-The Hill Climbing algorithm is a heuristic search algorithm that aims to find the peak of a cost function, which represents the solution to a problem. It iteratively moves to the best local solution until it reaches a peak, which may or may not be the global optimum.
What is the difference between a local and a global heuristic function?
-A local heuristic function considers only the immediate consequences of a move to decide the next step, whereas a global heuristic function takes into account the overall state of the problem to guide the search towards the goal.
What is the initial state in the context of the given script?
-The initial state is the starting configuration of the blocks where the goal is to rearrange them so that each block is on top of the block it should be, according to the problem's goal state.
What is the goal state in the described scenario?
-The goal state is the final configuration where block A is on the ground, block B is on top of A, block C is on top of B, and block D is on top of C.
How does the local heuristic function assign rewards in the given example?
-The local heuristic function assigns a plus one reward for each block that is resting on the block it is supposed to be on, and a minus one reward if it is not in the correct position.
What is the problem with using only a local heuristic function in the script's example?
-The problem with using only a local heuristic function is that it can lead to a local maximum, where no further improvements can be made based on immediate consequences, thus potentially failing to reach the global optimum or goal state.
How does the global heuristic function differ in assigning rewards compared to the local heuristic?
-The global heuristic function assigns rewards based on the correct support structure of each block. It gives a plus one reward for each block with the correct support and a minus one reward for each block with an incorrect support structure.
What is the advantage of using a global heuristic function over a local heuristic function?
-The advantage of using a global heuristic function is that it considers the overall state of the problem, which can help avoid local maxima and provide a better chance of reaching the global optimum or the goal state.
What does the script illustrate about the process of moving from the initial state to the goal state using heuristic functions?
-The script illustrates that by applying different heuristic functionsβlocal and globalβone can evaluate the current state and choose the best next move. It shows that sometimes a local heuristic might not be sufficient, and a global heuristic might be necessary to reach the goal state.
What is the final outcome of applying the global heuristic function in the script's example?
-The final outcome is that the algorithm successfully moves from the initial state with a value of minus six to the goal state with a value of plus six, indicating that all blocks are in their correct positions.
Outlines
π€ Introduction to Hill Climbing Algorithm with Heuristics
This paragraph introduces the concept of the hill climbing algorithm in the context of a block stacking problem. The speaker explains the goal of transitioning from an initial state to a goal state using heuristic functions. Two types of heuristics are discussed: local and global. The local heuristic function rewards each block that is correctly positioned with a +1, while incorrectly positioned blocks receive a -1. The global heuristic function considers the overall structure and assigns rewards or penalties based on the correctness of the entire stack beneath each block. The speaker uses an example with four blocks (A, B, C, D) to illustrate the process, starting with an initial configuration and aiming for a goal configuration where each block is correctly stacked.
π Overcoming Local Maxima with Global Heuristics
In this paragraph, the speaker delves into the limitations of using only local heuristic functions, which can lead to local maxima where the algorithm gets stuck and cannot reach the goal state. To overcome this, the speaker introduces the use of global heuristic functions. The global heuristic function assigns a score based on the correctness of the entire support structure beneath each block. The speaker demonstrates how applying global heuristics can lead to a series of moves that successfully transition from the initial state to the goal state. The example shows a step-by-step application of different operators to improve the state's value, ultimately achieving the goal state with a positive value, highlighting the effectiveness of global heuristics in the hill climbing algorithm.
Mindmap
Keywords
π‘Hill Climbing Algorithm
π‘Heuristic Function
π‘Local Heuristic Function
π‘Global Heuristic Function
π‘Initial State
π‘Goal State
π‘Local Maximum
π‘Operator
π‘Support Structure
π‘Optimization Problem
π‘Reward
Highlights
Introduction to hill climbing algorithm and its application in transitioning from an initial state to a goal state using heuristic functions.
Explanation of the example involving four blocks (A, B, C, D) and the goal state configuration.
Differentiation between local and global heuristic functions in decision-making processes.
Description of the local heuristic function rewarding blocks resting on their correct positions.
Calculation of the start state's value using the local heuristic function resulting in zero.
Goal state's value calculation with all blocks correctly positioned yielding a positive value.
Demonstration of applying operators to move from the start state towards the goal state.
Encountering a local maximum where further progress with the local heuristic function is not possible.
Introduction of the global heuristic function considering the entire structure for evaluation.
Calculation of the start state's value using the global heuristic function resulting in a negative value.
Goal state's value calculation with the global heuristic function showing a positive outcome.
Step-by-step application of the global heuristic function to overcome the local maximum and progress towards the goal state.
Illustration of moving block A to the ground and recalculating the state's value with the global heuristic function.
Exploration of moving block D to different positions and evaluating the outcomes.
Use of the global heuristic function to successfully transition from the initial state to the goal state.
Conclusion on the effectiveness of using both local and global heuristic functions in the hill climbing algorithm.
Encouragement for viewers to like, share, subscribe, and turn on notifications for more content.
Transcripts
hi
welcome back in this video i will
discuss how to apply hill claiming
search algorithm to go from initial
state to gold state
using local and global heuristic
function
we take this example where we have four
blocks abcd
we want to go from this particular
initial state or a start state to this
particular goal state
where we are expecting
a should be present on the ground on the
top of a b should be present on the top
of b we should have c on the top of c we
should have d in this case so this is
what is expected
now if you want to go from this
particular start state to gold state
we have to use one heuristic function
we have to use either the local
heuristic function where we will
consider only the immediate consequences
so that we can decide what to do next
or we have to consider the global
heuristic function
where we will consider the global
information or we can say that what will
happen
in future
based on that we will select the
operator
where we can go from start state to gold
state here
so first we will consider the local
heuristic function
uh in this local heresy function we will
give plus one reward for each block that
is resting on a thing it is supposed to
be resting on
that is for example we are expecting b
should rest on a a should rest on ground
similarly c should rest on b
d should rest on c if it is the case we
will give plus one if anything else is
there for example
in this particular start state only
b is present on a ground but what we are
expecting a should be present on the
ground so it will be given as a minus
one
ah we are expecting
c should be present on b yes it is
present so it will be given as a plus
one and so on so that is what the local
uh uh information or a local heuristic
function here
so we will try to calculate what is the
value for the start state
the start state is it will be minus one
because it is not present at the correct
position here
for c c is expected to be present on b
and it is present so it will be plus 1
this is also plus 1 but this is minus 1
so the total value of this particular
start state is 0 here
now when it comes to goal state all of
them are present on the current position
of course they are present on the
correct position so everything will be
given as
you can say that plus 1 over here
so the answer or the value of this
particular function is you can say that
the plus 4 here
now
using this particular local information
we have to go from start state to gold
state over here
now we have to apply some different
operators at the start state so that we
can go to the goal state here
so first operator is i will bring this
particular a to the ground so that is
the only option what we have here
now
b is present on the ground that is
incorrect position so it will be -1
c is present at the correct position d
is present at the correct position so
this will be given as a plus one here
is present at what we can say that the
correct position so it will be given as
the plus one now if i add everything i
will get the plus two as the answer in
this case
now uh there are two possibilities are
there either i can move this particular
d to this on the top of a or i can move
this particular d to this particular
ground
now if i do this particular operator if
i if i apply this particular operator
what will happen we will try to see
if i move this particular d on the top
of a
i will get the value as 0
and if i move this particular d to the
ground i am getting the value of 0
why because
b is incorrectly placed d is incorrectly
placed
a and c are correctly placed here so the
value is 0 similarly c is correctly
placed here k is correctly placed
b and d are incorrectly placed so
because of that we are getting 0 here
because we are getting 0 0 in both the
cases we have i ended up with something
called as
the local
maximum
or can say that a local optimum
okay so because of this we cannot go
ahead from here onwards
this is the disadvantage of using a
local elastic function or a local
information
i am not able to reach what you can say
that the goal state using this function
so what i do is i will use a global
information or a global heuristic
function
we will try to see whether i will be
able to go from
the start state to goal state or not
so in this case again the start state
and the goal states are same but the
heuristic function is something like
this for each block that has the correct
support structure the plus one will be
given as a reward for each one
for every block you can say
for each block that has a wrong support
structure a minus one will be given
support structure in the sense uh the
blocks which are present below the
current block if if all of them are
correctly placed uh one will be given
for every block actually
if they are not correctly placed minus 1
will be given for every block again okay
so you can see here
below b we don't have anything so it
will be 0
but below c b is present whether b is
present the correct position no so it
will be -1
below d
c and b are there both of them are
correctly placed no they are not
correctly placed so it will be minus 2
below a
b c d are there all of them are not
correctly placed with respect to the
gold state so it will be minus 3
so the total value of this particular
state is -6
now coming back to this goal state
of course all of them
are present at the correct position so
below a we don't have anything so it is
0
below b we have one node so it will be 1
here
for this one it will be 2
for this one it will be
3 here because below d 3 nodes are there
or the three
blocks are there all of them are
correctly placed here so it is plus six
so the intention is to go from start
state to gold state that is minus six
two plus six here by applying different
operators
so what i do here is first i will move
this particular a to this particular
ground
now if i move this particular a to the
ground
b below b we don't have anything so it
is 0 below c b is present it is
incorrectly placed
below d we have c and b
both of them are incorrectly placed
below a we don't have anything so it is
0 so the total value of this state is -3
now there are two possibilities are
there either i can move d on the ground
or d on the top of a
and now i will move this particular d on
the ground i will see what will happen
uh now if i move d on the ground
this one will be zero below c we have
one block that is incorrectly placed
below a we don't have anything so it is
0 below d we don't have anything hence
it is 0 so the total value of this
particular state is minus 1 so it is
better than the previous one so we will
consider it
now i will move c on the ground it will
look something like this
all of them
are not correctly placed but be below
this particular thing the support
structure is not present so all of them
are having 0 0 as the value
so the value of this particular state is
0. again it is better than the previous
one so i will continue from here onwards
now i will put
b on the top of a here so if i put b on
the top of a
for a it is 0 because below a we don't
have anything below b we have one
we can say that the block
which is correctly placed since it is
plus one
and then uh for d it is zero for c it is
zero so the total value of this state is
one year
now i will move c on the top of b
uh below a we don't have anything that's
the reason it is zero
below b we have one
block and it is correctly placed so it
is one below c we have two blocks a and
b both of them are correctly placed it
is two
below d we don't have anything so it is
zero so the total value of this
particular state is three in this case
now coming back to the last one that is
mo d on the top of c
all of them are correctly placed
for a it is 0 for b it is 1 because 1
correctly block is present below b
below c we have 2 blocks both of them
are correctly placed below d we have 3
blocks all three blocks are correctly
placed here so the total value of this
particular state is equivalent to plus
six
so we started with minus six we ended up
with plus six using this particular
global heuristic function in this case
so this is how actually we can use
either local or global heuristic
function
to go from initial state to gold state
using hill claiming algorithm
i hope this particular concept is clear
if you like the video do like and share
with your friends press the subscribe
button for more videos press the bell
icon for regular updates thank you for
watching
Browse More Related Video
Informed Search: Best First Search Part-1
Lecture 22: Kernighan β Lin (KL) Algorithm
What is Heuristic in AI | Why we use Heuristic | How to Calculate Heuristic | Must Watch
Frontly - Create Dynamic App Pages Using Block Versions & Local State
State Management in Nylo 5 | Flutter Framework
local and global Scope in JavaScript | JavaScript Tutorial in Hindi #88
5.0 / 5 (0 votes)