Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problem Solving by Searching :bulb: - Coggle Diagram
Problem Solving by Searching :bulb:
Problem-solving - having GOALS
First step: GOAL FORMULATION Based on current situation and performance measure
If environment is observable, discrete, known then solution to problem is a fixed sequence of actions
SEARCH The process of looking for a sequence of actions that reaches the goal is called search.
Well-defined problem
Initial state in(London).
Set of possible actions For state s, Actions(s) = { go(Norwich), go(Cardiff), go(Manchester) }.
Transition model
A description of what each action does; Result (s, a) - state that results from action a in state s Result( in(London), go(Norwich) ) = in(Norwich)
A Simple Problem
Initial State: Wolf, goat, cabbage and farmer are on the north side of the river.
• Goal State: Wolf, goat, cabbage and farmer are on the south side of the river.
• Operators: Farmer can go alone
Farmer can move one thing at a time across the river in the boat, or he can cross alone. But the goat cannot be left alone with the cabbage or with the wolf.
Solution:
Move to south {farmer, goat}
Move to north {farmer}
Move to south {farmer, cabbage}
Move to north {farmer, goat}
Move to south {farmer, wolf}
Move to north {farmer}
Move to south {farmer, goat}
Measuring Problem Solving algorithms’ / solution Performance
Completeness -the algorithm guarantees to find a solution when there is one?
Optimal - Does the strategy find the optimal solution(with minimum cost).
Time complexity – how much time is needed to perform the search
Space complexity – how much memory is needed to perform the search
Total cost=path cost+ search cost
Search Techniques for AI
Search is a central topic in Artificial Intelligence.
This is the general task of problem solving and is typically performed by searching through an internally modelled space of world states.
Rational agents need to perform sequences of actions in order to achieve goals.
A more general approach is for the agent, to have knowledge of the world and how its actions affect it and be able to simulate execution of actions in an internal model of the world in order to determine a sequence of actions that will accomplish its goals.