Chapter 3, Problem 25E

Program Plan Intro

Best-first-search algorithm:

• The best-first-search algorithm is a search algorithm used to search a particular node of a graph.
• This search algorithm explores the graph like, it chooses a most promising node according to some specific rules.
• The best-first-search algorithm refer specifically to a search with a heuristic. This search tries to predict how close the end of a path is to a solution, so that paths that are considered closer to a solution are extended first.
• The specific type of search is called pure heuristic search or greedy best-first search.

A* search algorithm:

• The A* search algorithm is a search algorithm used to search a particular node of a graph.
• A* algorithm is a variant of the best-first algorithm based on the use of heuristic methods to achieve optimality and completeness.
• The algorithm A* is an example of a best-first search algorithm.
• If a search algorithm has the property of optimality, it means that the best possible solution is guaranteed to be found. Here, the user wants the shortest path to the final state.

Uniform cost search:

• The uniform cost search algorithm is used to traverse weighted tree or graph.
• The ultimate aim of the uniform cost search is that to find the goal node that has the lowest cumulative cost.
• The uniform cost search expands nodes based on the root node’s path cost.
• The algorithm is used to solve the graph, tree where the cost is in demand.