DS161 Introduction to Data Science & Artificial Intelligence
Lecture 3
Problem Solving using State-Space Search II
Krishnendu Ghosh
Informed Search
This section shows how an informed search strategy—one that uses problem-specific knowledge beyond the definition of the problem itself—can find solutions more efficiently than can an uninformed strategy.
The general approach we consider is called best-first search. Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function, f(n). The evaluation function is construed as a cost estimate, so the node with the lowest evaluation is expanded first. The implementation of best-first graph search is identical to that for uniform-cost search, except for the use of f instead of g to order the priority queue.
Informed Search
The choice of f determines the search strategy. For example, best-first tree search includes depth-first search as a special case. Most best-first algorithms include as a component of f a heuristic function, denoted h(n):
h(n) = estimated cost of the cheapest path from the state at node n to a goal state.
Greedy Best-First Search
Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, f(n) = h(n).
Greedy Best-First Search
Let us see how this works for route-finding problems in Romania; we use the straight-line distance heuristic, which we will call hSLD. If the goal is Bucharest, we need to know the straight-line distances to Bucharest. For example, hSLD(In(Arad)) = 366. Notice that the values of hSLD cannot be computed from the problem description itself. Moreover, it takes a certain amount of experience to know that hSLD is correlated with actual road distances and is, therefore, a useful heuristic.
Greedy Best-First Search
Greedy Best-First Search
Greedy Best-First Search
Greedy Best-First Search
Completeness:
Greedy best-first tree search is incomplete even in a finite state space, much like depth-first search. Consider the problem of getting from Iasi to Fagaras. The heuristic suggests that Neamt be expanded first because it is closest to Fagaras, but it is a dead end. The solution is to go first to Vaslui—a step that is actually farther from the goal according to the heuristic—and then to continue to Urziceni, Bucharest, and Fagaras. The algorithm will never find this solution, however, because expanding Neamt puts Iasi back into the frontier, Iasi is closer to Fagaras than Vaslui is, and so Iasi will be expanded again, leading to an infinite loop.
The graph search version is complete in finite spaces, but not in infinite ones.
Greedy Best-First Search
Time and Space Complexity:
The worst-case time and space complexity for the tree version is O(b^m), where m is the maximum depth of the search space.
With a good heuristic function, however, the complexity can be reduced substantially. The amount of the reduction depends on the particular problem and on the quality of the heuristic.
A* Search
The most widely known form of best-first search is called A∗ search. It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:
f(n) = g(n) + h(n)
Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have
f(n) = estimated cost of the cheapest solution through n
A* Search
If we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions,
The algorithm is identical to UNIFORM-COST-SEARCH except that A∗ uses g + h instead of g.
A* Search
A* Search
A* Search
A* Search
Observations:
A* Search
Conditions for optimality: Admissibility
The first condition we require for optimality is that h(n) be an admissible heuristic. An admissible heuristic is one that never overestimates the cost to reach the goal. Because g(n) is the actual cost to reach n along the current path, and f(n) = g(n) + h(n), we have as an immediate consequence that f(n) never overestimates the true cost of a solution along the current path through n.
A* Search
Conditions for optimality: Admissibility
Let’s suppose, you are going to purchase shoes and shoes have a price of $1000. Before making the purchase, you estimated that the shoes will be worth $1200, When you went to the store, the shopkeeper informed you that the shoe’s actual price was $1, 000, which is less than your estimated value, indicating that you had overestimated their value by $200. so this is the case of Overestimation.
1200 > 1000
i.e. h(n) ≥ h*(n) ∴ Overestimation
A* Search
Conditions for optimality: Admissibility
Similar to the last situation, you are planning to buy a pair of shoes. This time, you estimate the shoe value to be $800. However, when you arrive at the store, the shopkeeper informs you that the shoes’ true price is $1000, which is higher than your estimate.indicating that you had underestimated their value by $200. In this situation, Underestimation has occurred.
800 < 1000
i.e. h(n) ≤ h*(n) ∴ Underestimation
A* Search
Conditions for optimality: Admissibility
where X is the start node and Y is the goal node in between these two nodes there are intermediate nodes A, B and all values which are in the following diagram are actual cost values means h*(n)
A* Search
Case 1: Overestimation
Let’s suppose, h(A)= 60 and h(B)= 50. So, using A* equation f(n) = g(n) + h(n) we get: f(A) = 100 + 60 = 160 and f(B) = 100 + 50 = 150. As f(A) > f(B), f(Y) = g(Y) + h(Y) = 140 + 0 = 140
The least cost to get from X to Y, as shown in the mentioned graph is 130, however, in Case 1, we took into consideration the expected costs h(n) of A & B, which were 60 & 50, respectively. As a result, 140 > 130 according to the Overestimation condition h(n) ≥ h*(n), and here, since the value of node f(A) is bigger than f(Y), we are unable to proceed along a different path which is from node A.
A* Search
Case 2: Underestimation
Let’s suppose, h(A) = 20 and h(B) = 10. So, using A* equation f(n) = g(n) + h(n) we get: f(A) = 100 + 20 = 120 and f(B) = 100 + 10 = 110. As f(A) > f(B), f(Y) = g(Y) + h(Y) = 140 + 0 = 140
Now, notice that f(Y) is the same in both circumstances but, in 2nd case by comparing the f(A) with f(Y) i.e. 120 < 140 as it means we can go from node A. Therefore A* will go with f(A).
f(Y) = g(Y) + h(Y) = 130 + 0 = 130
So, based on all of these calculations, we can say that this is the optimal value.
A* Search
Conditions for optimality: Consistency
A second, slightly stronger condition called consistency (or sometimes monotonicity) is required only for applications of A∗ to graph search. A heuristic h(n) is consistent if, for every node n and every successor n’ of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n:
h(n) ≤ c(n,a,n’) + h(n’)
A* Search
Conditions for optimality: Consistency
This is a form of the general triangle inequality, which stipulates that each side of a triangle cannot be longer than the sum of the other two sides. Here, the triangle is formed by n, n’ and the goal Gn closest to n.
For an admissible heuristic, the inequality makes perfect sense:
if there were a route from n to Gn via n’ that was cheaper than h(n), that would violate the property that h(n) is a lower bound on the cost to reach Gn.
So, every consistent heuristic is also admissible.
A* Search
Conditions for optimality: Consistency
If h(n) is consistent, then the values of f (n) along any path are nondecreasing.
The proof follows directly from the definition of consistency. Suppose n’ is a successor of n; then g(n’) = g(n) + c(n,a,n’) for some action a, and we have:
f(n’) = g(n’) + h(n’) = g(n) + c(n,a,n’) + h(n’) ≥ g(n) + h(n) = f(n)
A* Search
Advantages:
A* Search
Disadvantages:
A* Search
Applications:
A* Search
A∗ search is complete, optimal, and optimally efficient among all algorithms.
It does not mean that A∗ is the answer to all our searching needs.
For problems with constant step costs, the growth in run time as a function of the optimal solution depth d is analyzed in terms of the the absolute error or the relative error of the heuristic. The absolute error is defined as Δ ≡ h∗ − h, where h∗ is the actual cost of getting from the root to the goal, and the relative error is defined as ϵ ≡ (h∗ − h)/h∗.