Chapter 5 - Searching the Knowledge Space II (1).pptx

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 5: Searching the Knowledge Space –Informed Search 1  Introduction We ha...

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 5: Searching the Knowledge Space –Informed Search 1  Introduction We have seen uninformed search methods that systematically explore the state space and find the goal – They are typically too inefficient to do so in practice. Informed search methods use problem specific knowledge (heuristic function) : – to improve average search performance, – and may be more efficient  Heuristic Search Heuristic Search: Heuristic search use domain-specific knowledge to traverse the search space. This contrasts with blind search techniques that use “brute force” methods to scan the alternative nodes without any regard to domain knowledge. ES-Spring 2018, H.M.  Heuristics A heuristic is a rule of thumb that may help solve a given problem. It serves as an aid to learning, discovery, or problem-solving by trial and error methods. Heuristics take problem knowledge into consideration to help guide the search within the domain. Artificial Intelligence Lecture 5: Informed search 4  Hill-Climbing Search STEEPES T ASCENT Hill-climbing algorithm (steepest ascent) is a loop that continually moves in the direction of increasing value— that is, uphill. It terminates when it reaches a “peak” where no local neighbour has a higher ES-Springvalue. 2018, H.M.  Drawbacks of Hill-Climbing Search Stuck at Local Maxima: Peak is not the highest point inn the space To solve the problem, we introduce RANDOMNES S ES-Spring 2018, H.M.  /Best-First Search In Best-First search, the search space is evaluated according to a heuristic function. Nodes yet to be evaluated are kept on an OPEN list and those that have already been evaluated are stored on a CLOSED list. The OPEN list is represented as a priority queue, such that unvisited nodes can be de-queued in order of their evaluation function. The evaluation function f(n) is made up of two parts, which are the heuristic function h(n) and the estimated cost g(n), where: f (n) = g(n)+h(n) ES-Spring 2018, H.M.