Module 2

Problem Solving using searching

INFORMED (HEURISTIC) SEARCH
STRATEGIES

Problem-specific knowledge beyond the definition of the
problem itself

Search strategy which searches the most promising
branches of the state space first.

can find solutions more efficiently than an uninformed
strategy
Hill Climbing

Simple hill climbing is the simplest way to implement a hill climbing algorithm.

It only evaluates the neighbor node state at a time and selects the first one
which optimizes current cost and set it as a current state.

It only checks it's one successor state, and if it finds better than the current
state, then move else be in the same state.

This algorithm has the following features:

Less time consuming

Less optimal solution and the solution is not guaranteed
Hill Climbing-Algorithm

Evaluate the initial state, if it is goal state then return success and Stop.

Loop Until a solution is found or there is no new operator left to apply.
 Select and apply an operator to the current state.
 Check new state:

If it is goal state, then return success and quit.

Else if it is better than the current state then assign new
state as a current state.

Else if not better than the current state, Continue in the
loop.

Hill Climbing-Algorithm

Hill climbing function

Function HILL-CLIMBING (problem) returns a state that is local maximum

Inputs: problem, a problem

Local variables: current: a Node, Neighbor: a Node

Current<--- MAKE-NODE( INTIAIL –STATE[PROBLEM)

Loop do

Neighbor <-- a highest-valued successor of current

IF value [neighbor] ≤ value[current] then return STATE[current]

Current <-- Neighbor
Hill Climbing
Hill Climbing- problems

Hill climbing suffers from the following problems ‫ـــ‬

a) Local maximum: It is a state which is better than all of its neighbors but
is not better than some other states which are farther away. Please note that
at local maximum, all moves appear to make the things worse. They are
sometimes frustrating also as they often occur almost within sight of
solution. They are also called as foot-hills.

Solution for this problem

1. One possible solution is backtracking.
 We can backtrack to some earlier node and try to go in a different
direction to attain the global peak.

2. Another solution is list of promising plan.
Hill Climbing- problems

b) Plateau: It is a flat area of the search space in which a whole set of
neighboring states (nodes) has the same value. On plateau, it is not possible
to determine the best direction in which to move by making local
comparisons.

Solution for this problem

Big jump in some direction can be done in order to get to a new section of
search space. This method is recommended as in a plateau all neighboring
points have the same value.

2. Applying small steps several times in the same direction.
Steepest Ascent Hill Climbing


The steepest-Ascent algorithm is a variation of simple hill climbing
algorithm.

This algorithm examines all the neighboring nodes of the current
state and selects one neighbor node which is closest to the goal
state.

This algorithm consumes more time as it searches for multiple
neighbors

In simple hill climbing, the first closer node is chosen, whereas in
steepest ascent hill climbing all successors are compared and the
closest to the solution is chosen.
Steepest Ascent Hill Climbing -Algorithm

Evaluate the initial state, if it is goal state then return success and
stop, else make current state as initial state.

Loop until a solution is found or the current state does not change.
 Let SUCC be a state such that any successor of the current state will
be better than it.
 For each operator that applies to the current state:
 Apply the new operator and generate a new state.
 Evaluate the new state.
 If it is goal state, then return it and quit, else compare it to the SUCC.
 If it is better than SUCC, then set new state as SUCC.
 If the SUCC is better than the current state, then set current state to
SUCC.
BEST-FIRST SEARCH
Best First search is a way of combining the advantage of both
DFS and BFS.
Depth first search is good because it allows a solution to be
found without all competing branches having to be expanded.
BFS is good because it does not get trapped on dead-end
paths.
One way of combining the two is to follow a single path at a
time, but switch paths whenever some competing path looks
more promising than the current one does
BEST-FIRST SEARCH

Best-first search is an instance of the general TREE-SEARCH
or GRAPH-SEARCH algorithm inwhich a node is selected for
expansion based on an evaluation function, f(n).

The evaluation function is construed as a cost estimate, so the
node with the lowest evaluation is expanded first.

The choice of f determines the search strategy.

Most best-first algorithms include as a component of f a
heuristic function, denoted h(n):

h(n) = estimated cost of the cheapest path from the state at
node n to a goal state. if n is a goal node, then h(n)=0.
BEST-FIRST SEARCH
At each step of best first search process, we select the most promising of the
nodes we have generated so far.
If one of them is a solution, we can quit.
If not, all those new nodes are added to the set of nodes generated so far. Again
most promising branch is explored.
But, if a solution is not found, the branch will start to look less promising branch,
previously ignored. The old branch is not forgotten and the search can be return to
it whenever all the others get bad enough that it is again the most promising path.
The best first search algorithm uses an open [ ] list to keep track of the current
fringe of the search. ie. Nodes that have been generated and the heuristic function
had applied to them. OPEN is actually a priority queue in which elements with
highest priority are the most promising nodes.
closed [ ] list to keep a record of states already visited or examined before.
BEST-FIRST SEARCH-Algorithm

Create 2 empty lists: OPEN and CLOSED

Start from the initial node (say N) and put it in the ‘ordered’ OPEN list
Repeat the next steps until the GOAL node is reached
If the OPEN list is empty, then EXIT the loop returning ‘False’
Select the first/top node (say N) in the OPEN list and move it to the
CLOSED list. Also, capture the information of the parent node
If N is a GOAL node, then move the node to the Closed list and exit the
loop returning ‘True’. The solution can be found by backtracking the path
If N is not the GOAL node, expand node N to generate the ‘immediate’
next nodes linked to node N and add all those to the OPEN list
Reorder the nodes in the OPEN list in ascending order according to an
evaluation function f(n)
BEST-FIRST SEARCH-Algorithm

[Link] with OPEN containing just the initial state.

[Link] a goal is found or there are no nodes left on OPEN do:
a) Pick them best node on OPEN.
b) Generate its successors.
c) For each successor do:
i) if it has not been generated before, evaluate it, add it to OPEN,
and record its parent.
ii) If it has been generated before, change the parent if this new path
is better than the previous one.
In that case, update the cost of getting to this node and to any
successors that this node may already have.
BEST-FIRST SEARCH-Algorithm

This algorithm will traverse the shortest path first in the queue.
The time complexity of the algorithm is given by O(n*logn).
BEST-FIRST SEARCH-Example
BEST-FIRST SEARCH-Example
Initialization: Open [S], Closed [ ]
Expand the nodes of S and put in the CLOSED list
Iteration 1: Open [A, B], Closed [S]
Iteration 2: Open [A], Closed [S, B]
Iteration 3 : Open [E, F, A], Closed [S, B]
Iteration 4 : Open [E, A], Closed [S, B, F]
Iteration 5: Open [I, G, E, A], Closed [S, B, F]
Iteration 6: Open [I, E, A], Closed [S, B, F, G]

Hence the final solution path will be: S----> B----->F----> G

A* Search

A* search is the most commonly known form of best-first search.

It uses heuristic function h(n), and cost to reach the node n from the start
state g(n).
A* Search-Algorithm

1) Place the starting node in the OPEN list.

2) Check if the OPEN list is empty or not, if the list is empty then return failure
and stops.
3)Select the node from the OPEN list which has the smallest value of
evaluation function (g+h), if node n is goal node then return success and
stop, otherwise
4)Expand node n and generate all of its successors, and put n into the closed
list. For each successor n', check whether n' is already in the OPEN or
CLOSED list, if not then compute evaluation function for n' and place into
Open list.
5)Else if node n' is already in OPEN and CLOSED, then it should be attached
to the back pointer which reflects the lowest g(n') value.
6)Return to Step 2.
 PROBLEM REDUCTION
( AND - OR graphs - AO * Algorithm)
When a problem can be divided into a set of sub problems, where each sub
problem can be solved separately and a combination of these will be a solution,
AND-OR graphs or AND - OR trees are used for representing the solution.
The decomposition of the problem or problem reduction generates AND arcs.
One AND are may point to any number of successor nodes.
All these must be solved so that the arc will rise to many arcs, indicating several
possible solutions.
Hence the graph is known as AND - OR instead of AND.
AND - OR graphs

To pass any exam, we have two options,

either cheating or hard [Link] this
graph we are given two choices, first do
cheating or (The red line) work hard and
(The arc) pass.
When we have more than one choice and
we have to pick one, we apply OR
condition to choose one
Here we have replicated the arc between
the work hard and the pass because by
doing the hard work possibility of
passing an exam is more than cheating.
AO* Algorithm

Step-1: Create an initial graph with a single node (start node).

Step-2: Traverse the graph following the current path, accumulating node
that has not yet been expanded or solved.
Step-3: Select any of these nodes and explore it. If it has no successors then
call this value- FUTILITY else calculate f'(n) for each of the successors.
Step-4: If f'(n)=0, then mark the node as SOLVED.
Step-5: Change the value of f'(n) for the newly created node to reflect its
successors by backpropagation.
Step-6: Whenever possible use the most promising routes, If a node is
marked as SOLVED then mark the parent node as SOLVED.
Step-7: If the starting node is SOLVED or value is greater than FUTILITY
then stop else repeat from Step-2.
AO* Algorithm-Example
AO* Algorithm-Example
AO* Algorithm-Example