Intro to AI Ch. 2 - Search Algorithms

Search Cost vs. Solution Cost

Search cost - The cost of finding a solution

Solution cost - The cost of using said solution

In general, high search cost = low solution cost

Solution Cost

The cost of using a solution

Time Complexity

How long will it take to find a solution?

Space Complexity

How much memory will be used while finding the solution?

Completeness

When success is possible, is it guaranteed?

Optimality

Will the best solution be found?

Complexity Factors

b - branching factor, max number of successors of any node

d - depth of shallowest goal node

m - maximum length of any path in the state space

Uninformed Search

No problem-specific knowledge, cannot prefer one node over another. Search through the state space in a systematic fashion.

“Blind” search strategy

Informed Search

Use additional problem-specific knowledge to influence the search. Try to focus on paths that seem to be getting nearer to the goal state. Need an evaluation function.

“Directed”/“Heuristic” strategies

Breadth-First Search

Traverses tree in a left-to-right, top-to-bottom fashion. Expands all nodes on a level before moving to the next level. Queues new paths at the end of the queue.

Time: O(b^d)

Space: O(b^d)

Completeness: Yes, when b is finite

Optimality: Yes, when all step costs are identical

Depth-First Search

Traverses tree in a top-to-bottom, left-to-right fashion. Expands the left-most open node and works downward until a leaf node is reached. Then search is continued from next lowest, left-most, unexpanded node. Queues new paths at the end of the queue.

Time: O(b^m)

Space: O(bm)

Completeness: No, it can get stuck in an infinite loop

Optimality: No

Random Queuing

Like BFS or DFS, but search tree nodes are randomly expanded. Queue new paths at random positions in the queue.

Non-deterministic search

Depth-Limited Search

Like DFS, but a depth limit is imposed.

Time: O(b^l)

Space: O(bl)

Completeness: Yes, if a goal node exists above the depth limit

Optimality: No

Iterative Deepening Search

Like depth-limited search, but the depth limit is increased each time until the allotted time has run out. When time is up, the program returns to its “best guess move”

Time: O(b^d)

Space: O(bd)

Completeness: Yes, when b is finite

Optimality: Yes, when all step costs are identical

Evaluation Function

Scores a node in a search tree according to how close the target/goal state seems to be.

Heuristic

A common sense rule intended to increase the probability of solving a problem

Heuristic Function

Function h(n) that takes a state n and returns an estimate of the distance from n to the goal.

h(n)=0 if n is a goal node.

Is problem specific, and there may be more than one possible heuristic function.

Greedy Best-First Search

Tries to expand the node that is closest to the goal, on the grounds that it is likely to lead to a solution quickly.

Uses h(n) to guide search - new paths are sorted by h(n) before they are added to the queue.

Optimal Search

A search that guarantees the best (most optimal) path to the goal.

“British Museum” procedure: an example of a useless optimal search method in which all possible solutions are found and then the one with the lowest solution cost is selected.

Branch & Bound Search

Always extend the least-cost partial path. If this is done until the goal is reached, it is likely to be the optimal path. To be certain, all remaining paths must be extended until their path cost is greater.

Similar to greedy search, but the entire queue is sorted, not just the newly added paths.A

A* Search

Recognizes and removes redundant paths from the search queue using the dynamic programming principle. Only optimal when consistent heuristics are used.

Dynamic Programming Principle

In searching for the best path from some state S to some state G, you can ignore all paths from S to any intermediate state I, other than the minimum-length path from S to I.

Admissible Heuristic

A heuristic that conservatively underestimates the “goodness” of a path. A non-admissible heuristic may cause search to wander away from the optimal path permanently.

Admissible heuristics are required for B&B and A* search methods to produce optimal results.

A heuristic h(n) is admissible if:

0 <= h(n) <= h*(n)

where h*(n) is the actual cost to the goal.

Consistent Heuristics

Estimated heuristic costs <= actual cost FOR EACH INDIVIDUAL ARC

“A heuristic h(n) is consistent (or "monotone") if, for any node n and its successor n′, the estimated cost from n to the goal is less than or equal to the cost of moving from n to n′ plus the estimated cost from n′ to the goal.”

Consistency implies admissibility. Not every admissible heuristic is consistent but all consistent heuristics are admissible.