Slide 1Slide 2Slide 3Slide 4Slide 5Ancient BacktrackingSlide 7BacktrackingBacktracking Pseudo Code By MatuszekCh. Eick: Randomized Hill Climbing and BacktrackingRandomized Hill Climbing Randomized Hill Climbing NeighborhoodHill Climbing: Sample p points randomly in the neighborhood of the currently best solution; determine the best solution of the n sampled points. If it is better than the current solution, make it the new current solution and continue the search; otherwise, terminate returning the current solution.Advantages: easy to apply, does not need many resources, usually fast.Problems: How do I define my neighborhood; what parameter p should I choose?Ch. Eick: Randomized Hill Climbing and BacktrackingMaximize f(x,y,z)=|x-y-0.2|*|x*z-0.8|*|0.3-z*z*y| with x,y,z in [0,1]Neighborhood Design: Create solutions 50 solutions s, such that:s= (min(1, max(0,x+r1)), min(1, max(0,y+r2)), min(1, max(0, z+r3)) with r1, r2, r3 being random numbers in [-0.05,+0.05].Example Randomized Hill ClimbingExample Randomized Hill ClimbingCh. Eick: Randomized Hill Climbing and BacktrackingTerminates at a local optimum (moreover, the deviation between local and global optimum is usually unknown)Has problems with plateau (terminates), especially if the size of the plateau is larger than the neighborhood size.Has problems with ridges (usually falls of the “golden” path)The obtained solution strongly depends on the initial configuration.Too large neighborhood sizes random search, might shoot over hills.Too small neighborhood sizes slow convergence, might get stuck on small hills.Too large parameter p slow search; too small parameter p terminates without getting really close to the mountain topProblems Hill ClimbingProblems Hill ClimbingCh. Eick: Randomized Hill Climbing and BacktrackingExecute algorithm for a number of initial configurations (randomized hill climbing with restart)Use information of the previous runs to improve the choice of initial configurations.Dynamically adjust the size of the neighborhood and the number of points sampled. For example, start with large size neighborhoods and decrease the size of the neighborhood as the search evolves.Allow downward moves: Simulated Annealing Resample before terminating (e.g. sample p points; if there is no improvement sample another 2p points; if there is still no improvement sample another 4p points; if there is no improvement after that finally terminate).Use domain specific knowledge to determine neighborhood sizes and number of points sampled.Hill Climbing VariationsHill Climbing VariationsCh. Eick: Randomized Hill Climbing and BacktrackingDefine a neighborhood as the set of states that can be reached by n operator applications from the current state (where n is a constant to be chosen based on the characteristics of a particular search problem)The state space version creates all states in the neighborhood of the current state (alternatively, it could just create some states which would be a randomized version), and picks the one with the best evaluation as the new current state, or it terminates unsuccessfully if there is no state that is better than the current state.A variable path has to be added to the hill climbing code that memorizes the path from the initial state to the current state. The path variable is initialized with an empty list. Every time a new current state is obtained the operator or operator sequence that was used to reach this state is appended to the path variable. A goal test has to be added to the hill climbing code (if it returns true the algorithm terminates returning the contents of its path variable as its solution). IHill Climbing for State Space SearchHill Climbing for State Space SearchCh. Eick: Randomized Hill Climbing and BacktrackingAncient BacktrackingAncient Greek legends tell of King Minos of Crete, who had the inventor Daedalus create a labyrinth beneath his palace in which was housed the Minotaur, a fearsome monster with the head of a bull and body of a man. The Minotaur was said to have been slain by the Greek hero Theseus, who then managed to find his way out of the labyrinth with the aid of a ball of thread that had been given to him by Ariadne, the daughter of Minos.Ch. Eick: Randomized Hill Climbing and BacktrackingAssume you have to search a labyrinth of interconnected rooms trying to find a particular room that contain a red flower. There will be many intersections of walkways that connect rooms all of which look completely the same; you will not know if you entered a particular crossing before; however, you will be given a piece of chalk that allow you to put signs of your own choosing on a wall. Devise a search strategy that will find a room with a red flower assuming that such a room exists. To be discussed on February 6, 2019 in class!Motivation: https://www.youtube.com/watch?v=8P-ALSqmWRI Un-graded Homework1 2019Un-graded Homework1 2019Goal State7:27: shows what happensyou if I you do not know howto search intelligently…Ch. Eick: Randomized Hill Climbing and BacktrackingBacktrackingPopular for state space search problems and CSPIdea (make the initial state the “current state”; the proceed as outlined below):1. Apply an (the best) operator that has not been applied before to the current state. The so obtained state becomes the new current state (if it is a goal state the algorithm terminates and returns a solution)2. If there is no such operator, backtrack: the predecessor of the current state becomes the new current state (if you applied all operators to the initial state the algorithm terminates without a solution). XXAlready exploredDirection I came fromCh. Eick: Randomized Hill Climbing and BacktrackingBacktracking Pseudo Code By Matuszekhttps://www.cis.upenn.edu/~matuszek/cit594-2002/Pages/backtracking.html Wikipedia: