need help with CS homework

Rawan ageeli

CS330_Module2_Part1.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

In order to understand how exactly problem solving contributes to intelligence,

we need to find out how intelligent species solve problems.

The classical approach to solving a problem is pretty simple. Given a problem at

hand use hit and trial method to check for various solutions to that problem.

This hit and trial approach usually works well for trivial problems and is referred

to as the classical approach to problem solving.

Technically we call this hit and trial approach the “Generate and Test” approach.

Classical Approach

www.funFruit.com CS330 By Fozia Noor

environment agent

sensors

actuators

www.funFruit.com CS330 By Fozia Noor

 A problem solving agent is a kind of goal-based agents that decide what to do by finding sequences of actions that lead to desirable goal.

 Many problems can be represented as a set of states and a set of rules of how one state is transformed to another. Each state is an abstract representation of the agent's environment.

 The agent must choose a sequence of actions to achieve the desired goal.

www.funFruit.com CS330 By Fozia Noor

environment

agent

sensors

actuators

 Formulate Goal  Formulate Problem

Set goals Initial state States Actions

 Find Solution

www.funFruit.com CS330 By Fozia Noor

 Initial state is the description of the starting configuration of the agent

 Action/ Operator takes the agent from one state to another state.

 They take state as input and give the set of actions which can be taken in this state .

(s) {a1,a2,a3,.....an}

 Result which takes state and action as input and return us a new state as result

 (s,a)s1

 A Goal state is a description of a desirable states of the world.

 Goal Test which takes state as input and return Boolean value as return

 (s)T/F

 Path cost is a positive number usually sum of step cost (step cost is (s,a,s1)n)

 (sss)n a a

www.funFruit.com CS330 By Fozia Noor

The search problem is to find a sequence of actions which transforms the agent from the initial state to a goal state g∈G. This sequence of actions is called a solution plan. It is a path from the initial state to a

goal state. .

Concept of a search problem

Formal description of search problem.

A search problem consists of the following:

 S: the full set of states

 s0 : the initial state

 A:S→S is a set of operators

 G is the set of final states. Note that G ⊆S

A search problem is represented by a 4-tuple {S, s0, A, G}.

www.funFruit.com CS330 By Fozia Noor

Representation of search problems

 A search problem is represented using a directed graph.

 The states are represented as nodes.

 The operators are represented as edges which takes us from one state to

other state.

www.funFruit.com CS330 By Fozia Noor

The generic searching process can be very simply described in terms of the following steps:

Do until a solution is found or the state space is exhausted.

1. Check the current state

2. Execute allowable actions to find the successor states.

3. Pick one of the new states.

4. Check if the new state is a solution state

5. If it is not, the new state becomes the current state and the process is repeated

www.funFruit.com CS330 By Fozia Noor

Toy Problem

8 Puzzle

Vacuum world

Real Word Problem

Route Finding

TSP

Robot Navigation

www.funFruit.com CS330 By Fozia Noor

Arad

Bucharest

Oradea Zerind

Faragas

Neamt

Iasi

Vaslui

Hirsova

Eforie

Urziceni

Giurgui

Pitesti

Sibiu

Dobreta

Craiova

Rimnicu

Mehadia

Timisoara

Lugoj

142

211

101

140 118

111

120

138

146

140

101

Sibiu

Rimnicu

Pitesti

www.funFruit.com CS330 By Fozia Noor

On holiday in Romania; Currently

in Arad.

Formulate Goal:

– Be in Bucharest

Formulate Problem:

– States: various cities

– Actions: drive between

cities

A problem is defined by four items: initial state e.g., "at Arad“ actions S(x) = set of action–state pairs e.g., S(Arad) = {<Arad  Zerind,} goal test x = "at Bucharest”, path cost (additive) e.g., sum of distances, number of actions executed, etc. A solution is a sequence of actions leading from the initial state to a goal state

www.funFruit.com CS330 By Fozia Noor

 States  8 possible states

 initial state  any

 Actions  Left, Right, Suck

 goal test  no dirt at all locations

 path cost  1 per action

www.funFruit.com CS330 By Fozia Noor

 Initial state: given

 Actions: move blank left, right,

up, down

 Goal test: goal state (given)

 Path cost: 1 per move

www.funFruit.com CS330 By Fozia Noor

Searching through a state space involves the following:

 A set of states

 Operators and their costs

 Start state

 A test to check for goal state

Exploration of state space by generating successors of already-explored states

Every generated state is evaluated: is it a goal state ?

www.funFruit.com CS330 By Fozia Noor

 Normally graphs are used to represent problems and their solution spaces.

 Every graph can be converted into a tree, by replicating the nodes.

Search tree for the state space graph

state space graph

www.funFruit.com CS330 By Fozia Noor

 Root Node: The node from which the search starts.

 Leaf Node: A node in the search tree having no

children.

 Ancestor/Descendant: X is an ancestor of Y is either X

is Y’s parent or X is an ancestor of the parent of Y. If X is

an ancestor of Y, Y is said to be a descendant of X.

 Branching factor: the maximum number of children of

a non-leaf node in the search tree

 Path: A path in the search tree is a complete path if it

begins with the start node and ends with a goal node.

Otherwise it is a partial path

www.funFruit.com CS330 By Fozia Noor

The search algorithm maintains a list of nodes called the fringe.

The fringe keeps track of the nodes that have been generated but are yet to be

explored.

www.funFruit.com CS330 By Fozia Noor 23

www.funFruit.com CS330 By Fozia Noor

 Strategies are evaluated along the following factors:

Evaluation Strategies

Completeness Is the strategy guaranteed to find a

solution if one exists?

Optimality Does the solution have low cost or

the minimal cost?

What is the search cost associated

required to find a solution?

Time complexity

Time taken (number of nodes expanded) to find a solution

Space complexity: Space used by the algorithm

measured in terms of the maximum size of fringe

www.funFruit.com CS330 By Fozia Noor

 Time and space complexity are measured by three quantities

 b: maximum branching factor of the search tree

 d: depth of the least-cost solution

 m: maximum depth of the state space (may be ∞)

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