General Pseudocode for Depth/Breath/Best First SearchGeneral Pseudocode for SMA*/A*SearchSampreeth Chebolu, Theodoros Tavoulareas and Christoph F. Eick COSC 4368: Fundamentals of Artificial Intelligence Spring 2020Problem Set1 (Individual Tasks1)Fourth DraftDeadline: Sa. February 22, 11:59p Last Updated: Feb. 16, 9aWeight: 34-42% of the points available for the 3 problem sets!Comment: Points allocated to each of the 5 tasks are tentative and subject to change. 1) Applying Various Search Strategies to a State Space (12 pts) Theodoros Assume that you have the following search graph, where S is the start node and G1 and G2 are goal nodes. Arcs are labeled with the cost of traversing them and the estimated cost to a goal is reported inside nodes. Apply the search strategies listed below to the search graph:, (a) indicate which goal state is reached if any, (b) list, in order, the states expanded, and (c) show the final contents of the OPEN and CLOSED lists. (Recall that a state is expanded when it is removed from the OPEN list.) When there is a tie with respect to which node has to be expanded next, nodes should be expanded in alphabetical order. The used search strategies include;1. breadth-first2. depth-first3. best-first (using f = h)4. A* (using f = g + h) 5. SMA* (using f=g+h and limiting the open-list to just 3 elements)1 Collaboration with other students is not allowed! PAGeneral Pseudocode for Depth/Breath/Best First Search OPEN = { startNode } // Nodes under consideration. CLOSED = { } // Nodes we're done with. while OPEN is not empty { remove an item from OPEN based on search strategy used - call it X if goalState?(X) return the solution found otherwise // Expand node X. { 1) add X to CLOSED 2) generate the immediate neighbors (ie, children of X) 3) eliminate those children already in OPEN or CLOSED 4) add REMAINING children to OPEN } } return FAILURE // Failed if OPEN exhausted without a goal being found.General Pseudocode for SMA*/A*Search OPEN = { startNode } // Nodes under consideration. CLOSED = { } // Nodes we're done with. while OPEN is not empty { remove an item from OPEN based on search strategy used - call it X if goalState?(X) return the solution found otherwise // Expand node X. { 1) add X to CLOSED 2) generate the immediate neighbors (ie, children of X) 3) add all children to OPEN } } return FAILURE // Failed if OPEN exhausted without a goal being found.Submission Guidelines: The solution needs to be as follow:GOAL Reached firstExpanded statesOPEN ListCLOSE ListFailure to follow above instruction will lead to point deductionsPA2) Describe a Search Space (10 points) SampreethIn the water-jug puzzle we are given a 3 liter jug, named Three, and a 4 liter jug, named Four. Initially, Three and Four are empty. A jug can be filled from a tap T, and, we can discard the water from either jug into a drain, D. Water in one jug may also be poured into the other jug; however, this operation is only allowed if the receiver jug has sufficient capacity to receive the water. There are no other measuring devices. We want tofind a set of operations that will leave precisely two liters of water in Four. (a) Formulate this problem as a state-space search problem. Give a precise definition of a state, the start state, the goal state or goal condition, and the operators. Operators should be specified as "schemas" that indicate for a given state, when the operator is legal (i.e., a set of constraints on when the operator can be applied to an arbitrary state) and the description of the successor state after the operator is applied. In other words, each operator should be specified in a way that it would easily implemented in a program to solve this problem.(b) Show the State SpaceDraw the complete state-space graph that includes all nodes (and legal directed arcs connecting these nodes) for this problem. Inside each node show the state description, and label each arc with its associated operator. Highlight a path that gives a solution to the problem.3) A* (10 points) Theodoros a) What characteristics should a good evaluation function h for A* have? Give reasons for your answer! b) Assume A* is used with a heuristic h(s) that sometimes overestimates the cost of reaching the goal state from s. Will A* in this case still find the optimal solution? If your answer is yes, give a reason for your answer! If your answer is now, gives an example of a search problem with the above characteristics for which A* no longer finds the optimal solution! c) Assume h1 and h2 are both admissible heuristics for A* for a search problem; is h(x)=max(h1(x), h2(x)) also an admissible heuristic? Do you prefer heuristic h over heuristics h1 and h2 or not? Give reasons for your answer! 4) Implementing and Experimenting with Randomized Hill Climbing (26pts) Theodoros Implement Randomized Hill Climbing and apply it to a minimization problem involving the following function f: with x,y∈[−6,+6]Your procedure should be called RHC and have the following input parameters:● sp: is the starting point2 of the Randomized Hill Climbing run● p the number of neighbors of the current solution that will be generated2 A vector (x,y) with x,y∈[-6,+6]PA● z neighborhood size; for example if z is set to z=0.5 p neighbors for the current solution s are generated by adding vectors v=(z1,z2) with z1 and z2 being random numbers in [-0.5,+0.5] uniformly distributed ● seed which is an integer that will be used as the seed3 for the random generator you employ in your implementation. RHC returns a vector (x,y) the value of f(x,y) and the number solutions that were generated during the run of RHC.Run your randomized hill climbing procedure RHC twice4 for the following parameters:sp= (2.9, 3.2), (-2.5,+3.2), (4.2,-2) and (0,0)p= 30 and 120z= 0.03 and z=0.1For each of the 32 runs report:a. the best solution (x,y) found and its value for fb. number of solutions generated during the run5. Summarize your results in 4 tables; one for each p and z combination6. Interpret7the obtained results evaluating solution quality, algorithm speed, impact of sp, p, and z on solution quality and algorithm speed. Do you believe with other values for p and rbetter results could be accomplished? At last, assess if RHC did a good, medium or bad job in computing a (local) minimum for f. Finally, produce one more run using