need help with CS homework

www.funFruit.com CS330 By Fozia Noor

www.funFruit.com CS330 By Fozia Noor

Chapter Outline

Problem Solving agent

Definition of Problems and their Solution

Search Algorithms

Performance Measure of each algorithm

www.funFruit.com CS330 By Fozia Noor

 Uninformed search strategies look for solutions by using a strategy, generating new states and checking each of them against the goal.

 This approach is very inefficient in most cases.

.

3

Most successor states are “obviously” a bad choice.

But Such strategies do not know that because they have minimal

problem-specific knowledge

www.funFruit.com CS330 By Fozia Noor

Informed Searches

www.funFruit.com CS330 By Fozia Noor

A strategy that uses problem-specific knowledge beyond the definition of the problem itself - can find solutions more

efficiently than an uninformed strategy.

 An informed search is about where the goals might be by using a heuristic so that we can find optimal solutions while exploring less of the search tree.

5

www.funFruit.com CS330 By Fozia Noor

 The key ingredient of informed search is the idea of a heuristics, or rules- of-thumb to help decide which parts of a tree to examine.

 A heuristic is a rule or method that almost always improves the decision process.

6

www.funFruit.com CS330 By Fozia Noor

Greedy Best First Search

www.funFruit.com CS330 By Fozia Noor

Greedy Best-First search tries to expand the node that is closest to the goal assuming it will lead to a solution quickly

f(n) = h(n)

Implementation

 Expands the node that appears to be the closest one to the goal

8

www.funFruit.com CS330 By Fozia Noor

 Initial State: S

 Goal State: G

Heuristics

www.funFruit.com CS330 By Fozia Noor

Initial State: S

Goal State: G

www.funFruit.com CS330 By Fozia Noor

• Initial state: S

• Goal State: G

www.funFruit.com CS330 By Fozia Noor

 Uniform-cost orders by path cost,

 backward cost g(n)

 Greedy orders by goal proximity,

 forward cost h(n)

www.funFruit.com CS330 By Fozia Noor

A* Search

www.funFruit.com CS330 By Fozia Noor

 A* search is similar to Greedy best-first search with the

difference that:

 A* search includes in its evaluation function the cost from the

start node to the current node, in addition to the estimated

cost from the current node to the goal.

www.funFruit.com CS330 By Fozia Noor

 Evaluation function: f(n) = g(n) + h(n), where:

 g(n): Cost so far to reach n (Uniform cost search minimizes it)

 h(n): Estimated cost to goal from n (best-first search minimizes it)

 f(n): Estimated total cost of path from the starting node n0 through n to the goal

(best estimated cost for complete solution)

 Using current cost and estimated cost give this algorithm completeness(if

the solution exists, it will be found) and optimality(it will find the best

solution).

 All these advantages made A* algorithm the most popular search algorithm in

AI applications.

www.funFruit.com CS330 By Fozia Noor

• Initial state: S

• Goal State: G

www.funFruit.com CS330 By Fozia Noor

Initial State: S

Goal State: G

www.funFruit.com CS330 By Fozia Noor

 Initial State: S

 Goal State: G

Heuristics

www.funFruit.com CS330 By Fozia Noor

• Solve using A*