A* Algorithm : - In best first search we found a heuristic value called evaluation function value. It is the value that estimate how far a particular node is from the goal node. A part from the evaluation function values one can also bring in cost function. Cost function indicates how much resources like time, energy, money ect... have been spend in reaching a particular node from the start node.
While evaluation function value deal with future, cost function value deal with past.
If if is possible for one obtain the evaluation function and cost function value, then A* algorithm can be used.
The sum of evaluation function value and cost function value is known as fitness.
The fitness number is the total evaluation value and the cost function value. While best first search uses the evaluation function values only for expanding the best node. Where as A* uses fitness number for its computation.
Algorithm :-
While evaluation function value deal with future, cost function value deal with past.
If if is possible for one obtain the evaluation function and cost function value, then A* algorithm can be used.
The sum of evaluation function value and cost function value is known as fitness.
The fitness number is the total evaluation value and the cost function value. While best first search uses the evaluation function values only for expanding the best node. Where as A* uses fitness number for its computation.
Algorithm :-
- Step 1 :- Put the initial node on the list BEGIN.
- Step 2 :- If (BEGIN = EMPTY) or (BEGIN = GOAL) terminate search.
- Step 3 :- Remove the first node from BEGIN call this node as A
- Step 4 :- If (A = GOAL) terminate the search process.
- Step 5 :- Else if node has a successor than generate all of them estimate the fitness number of successor by totally the evaluation function value and cost function value sort the list by fitness number.
- Step 6 :- Name the list as BEGIN 1
- Step 7 :- Replace BEGIN with BEGIN 1
- Step 8 :- GOTO Step 2.
No comments:
Post a Comment