Implement the Uniform Cost Search Method in JAVA using the algorithm given below. Use the traveling salesperson example as the domain for the search problem.

The program requirements are as follows:

Input: Start State, Intermediate States, Goal Test, Path Cost.

Processing: The search method goes from the start state to the goal state.

Output: Path(s) traced from start state to goal state by the program, Total path cost calculated by the program, and a physically drawn out Search Tree.

*Note: It is not required to develop a GUI in the program to show the state map or the paths traced. It is sufficient to show the paths by listing the states from start to goal as a program output.*

Chapter 3. Solving Problems by Searching function UNIFORM-COST-SEARCH(problem) returns a solution, or failure node a node with STATE = problem.INITIAL-STATE, PATH-COST = 0 frontier-a priority queue ordered by PATH-COST, with node as the only element explored an empty set loop do if EMPTY?(frontier) then return failure node POP(frontier) /* chooses the lowest-cost node in frontier if problem.GOAL-TEST(node.STATE) then return SOLUTION(node) add node.STATE to explord for each action in problem.ACTIONS(node.STATE) do child CHILD-NODE( problem, node, action) if child.STATE is not in explored or frontier then frontier INSERT( child, frontier) else if child.STATE is in frontier with higher PATH-COST then replace that frontier node with child Figure 3.14 Uniform-cost search on a graph. The algorithm is identical to the general graph search algorithm in Figure 3.7, except for the use of a priority queue and the addition of an extra check in case a shorter path to a frontier state is discovered. The data structure for frontier needs to support efficient membership testing, so it should combine the capabilitis of a priority queue and a hash table