際際滷

際際滷Share a Scribd company logo

Hillclimbing search algorthim #introduction

Download as ODP, PDF
Mohamed Gad
Mohamed Gad

Hill climbing is a heuristic search algorithm that starts with an initial solution and iteratively improves it by incrementally changing a single element of the solution. It selects the change that results in the greatest improvement to the solution based on an evaluation function. However, hill climbing is prone to getting stuck at local optima rather than finding the global optimum. Solutions include backtracking, making larger jumps, or applying multiple changes before evaluating.

1 of 8
Downloaded 244 times
Introduction HillHill climbingclimbing
Artificial Intelligence search algorithms Search techniques are general problem-solving methods. When there is a formulated search problem, a set of states, a set of operators, an initial state, and a goal criterion we can use search techniques to solve the problem (Pearl & Korf, 1987)
Search Methods Brute-Force / Blind Search Methods Breadth-First Search Depth-First Search DFS Iterative Deepening (DFID) Iterative Broadening British Museum
Search Methods Heuristic Search Hill Climbing Steepest Ascent Branch and Bound Best-First Search Beam Search A* Iterative-Deepening A* B' Simulated Annealing
Hill Climbing Looking at all of our operators, we see which one, when applied, leads to a state closest to the goal. We then apply that operator. The process repeats until no operator can improve our current situation (which may be a relative maximum, such as in the TSP).
Hill Climbing Problems with hill climbing: local maxima (we've climbed to the top of the hill, and missed the mountain), plateau (everything around is about as good as where we are), ridges (we're on a ridge leading up, but we can't directly apply an operator to improve our situation, so we have to apply more than one operator to get there).
Hill Climbing Solutions include: backtracking, making big jumps (to handle plateaus or poor local maxima), applying multiple rules before testing (helps with ridges).
Hill-Climbing Methodology Construct a sub-optimal solution that meets the constraints of the problem Take the solution and make an improvement upon it Repeatedly improve the solution until no more improvements are necessary/possible

More Related Content

Hillclimbing search algorthim #introduction

  • 2. Artificial Intelligence search algorithms Search techniques are general problem-solving methods. When there is a formulated search problem, a set of states, a set of operators, an initial state, and a goal criterion we can use search techniques to solve the problem (Pearl & Korf, 1987)
  • 3. Search Methods Brute-Force / Blind Search Methods Breadth-First Search Depth-First Search DFS Iterative Deepening (DFID) Iterative Broadening British Museum
  • 4. Search Methods Heuristic Search Hill Climbing Steepest Ascent Branch and Bound Best-First Search Beam Search A* Iterative-Deepening A* B' Simulated Annealing
  • 5. Hill Climbing Looking at all of our operators, we see which one, when applied, leads to a state closest to the goal. We then apply that operator. The process repeats until no operator can improve our current situation (which may be a relative maximum, such as in the TSP).
  • 6. Hill Climbing Problems with hill climbing: local maxima (we've climbed to the top of the hill, and missed the mountain), plateau (everything around is about as good as where we are), ridges (we're on a ridge leading up, but we can't directly apply an operator to improve our situation, so we have to apply more than one operator to get there).
  • 7. Hill Climbing Solutions include: backtracking, making big jumps (to handle plateaus or poor local maxima), applying multiple rules before testing (helps with ridges).
  • 8. Hill-Climbing Methodology Construct a sub-optimal solution that meets the constraints of the problem Take the solution and make an improvement upon it Repeatedly improve the solution until no more improvements are necessary/possible