need help with CS homework

Rawan ageeli

CS330_Module2_Part2.pdf

Home >Computer Science homework help >need help with CS homework

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

Search strategies and algorithms are primarily of four types,

 blind/uninformed,

 informed/heuristic,

 any path/non-optimal

 optimal path

www.funFruit.com CS330 By Fozia Noor

www.funFruit.com CS330 By Fozia Noor 6

Blind strategies

Breadth-first search

Depth-first search

Depth Limited search

Uniform-cost search

Iterative deepening search

Bidirectional search

You have no clue whether one non- goal state is better than any other. Your search is blind. You don’t know if your current exploration is likely to be fruitful.

www.funFruit.com CS330 By Fozia Noor

• Expand shallowest unexpanded node

• Fringe = first-in-first-out (FIFO).

• The newly generated nodes are put at the

front of fringe.

• Expand deepest unexpanded node

• Fringe= Last In First Out (LIFO)

• The newly generated nodes are put at the

back of fringe.

Breadth First Search

Depth First Search

www.funFruit.com CS330 By Fozia Noor

Initial State : A Goal State: G

www.funFruit.com CS330 By Fozia Noor

The algorithm returns the path A C G The algorithm returns the path A B D C G

www.funFruit.com CS330 By Fozia Noor

Choose the algorithm

(BFS or DFS)

for the problem given

Suppose you have a tree representing some command structure:

This tree is meant to represent who is in charge of lower-ranking officers. Suppose a fierce battle with an enemy ensues. If officers start dropping like flies, we need to know who is the next person to take over command.

www.funFruit.com CS330 By Fozia Noor

Animal

Bird Mammal

Elephant whales

charlie

small Large

sparrow crow

Is charlie an animal?

Answer: Traverse the tree If charlie node present then answer is YES otherwise NO

Is charlie a mammal? Is charlie a Bird?

www.funFruit.com CS330 By Fozia Noor

Initial State

Goal State

www.funFruit.com CS330 By Fozia Noor

Initial State

Goal State

www.funFruit.com CS330 By Fozia Noor

Arad

Bucharest

Oradea Zerind

Faragas

Neamt

Iasi

Vaslui

Hirsova

Eforie

Urziceni

Giurgui

Pitesti

Dobreta

Craiova

Rimnicu

Mehadia

Timisoara

Lugoj

142

211

101

140 118

111

120

138

146

140

101

Sibiu

Rimnicu

www.funFruit.com CS330 By Fozia Noor

Draw tree and solve Using BFS & DFS

a b

Initial State

Goal State

www.funFruit.com CS330 By Fozia Noor

 Introduce a depth limit on branches to be expanded.

 Don’t expand a branch below this depth.

www.funFruit.com CS330 By Fozia Noor

 DFS may never terminate as it could follow a path that has no

solution on it

 DLS solves this by imposing a depth limit, at which point the

search terminates that particular branch

 DLS Will find solution if there is one in the depth bound

www.funFruit.com CS330 By Fozia Noor

 Depth limit of 2 would mean that

children of E are ignored.

 Goal can never be reached in this

case.

J B C