cs28 Prove A is admissible the proof should show that A sear

cs28

Prove A* is admissible. the proof should show that: A* search will terminate. During its execution, there is always a node on open that lies on an optimal path to the goal. If there is a path to a goal. A* will terminate by finding the optimal path.

Solution

A* is also called as the best first search algorithm in this alorithm we explore the node which has the smallest data and we need to maintaine 2 datastructures to store visited and unvisited nodes they are

open:containe the nodes or states which is visited

clse:containes the nodes or states which is unvisited.

proof::

start from the root node A and insert it into open list

IF(ROOT==GOAL)

compare with goal if it equal then success

else

and explore the child which having the low cost.A {c1,c2,c3,.......,cn}

after exploring the child node then compare the nodes that is not visited if any node that is having the low weight then the control goes to that node and explore the min_weighted(NODE).

IF(OPEN[]==CURRENT_NODE)

IF(CURRENT_NODE==GOAL)

compare with goal if it equal then success

else

do until the goal node reached

if there is any node equal when comapre with the goal then success then terminates otherwise it explore all the states and then terminates

////////////////////////////////////