Problem solving Flashcards
What does the Problem Space theory claim?
We analyse problems in terms of search strategies
What are search strategies?
Strategies that involve searching within an abstract problem space
A problem is made up of 3 elements. What are they?
- A starting state (where you are)
- A goal state (where you want to be)
- A set of processes (operators) that transform one state into another
If all 3 elements of a problem can be identified, what type of problem is this?
A well-defined problem
What types of problems can you get?
- Well-defined vs. ill-defined
- Knowledge-rich vs. knowledge-lean
- Adversary vs. non-adversary
What is a well-defined problem?
The start state, goal state & operators in the problem are identifiable
What is a knowledge-rich problem?
The problem requires specific knowledge/skills to solve it
You must access info from LTM/production memory to solve it
The start state, goal state & operators are identifiable
What is a knowledge-lean problem?
The problem can be solved using instructions & general problem-solving skills
What is an adversary problem?
It matters what others do - someone is trying to stop you reaching the goal state
You must overcome the opposition to reach the goal state
Each step towards the goal state is the largest possible move towards the goal state from the current state space
What is a non-adversary problem?
It doesn’t matter what others do - you aren’t being stopped by anyone
Name 3 search strategies.
- Depth-first
- Breadth-first
- Best-first
What does the depth-first search strategy involve?
Going through all alternatives to a move before considering another move
What does the breadth-first search strategy involve?
Working out which move will most likely put you where you want to be
Can use cost analysis (how much it is costing you to do these things & how much you will get back)
What are the problems with using unguided search strategies?
X the n-tile puzzle is hard to solve by exhaustive search
X intelligence problem-solving requires SOME form of guided search
- AI researchers have suggested several forms, but some aren’t compatible with human cognition (e.g. best-first search; require too much memory/too-fast computation)
Why is the n-tile puzzle hard to solve by exhaustive search?
The problem space increases with the number of tiles
n=6x5x4x3x2x1 = 720 possible states for 6-tile puzzle n=9x8x720 = 51,840 possible states for 9-tile puzzle
Why is the n-tile puzzle a ‘limited state space’?
There is a limited number of states that the puzzle can be in
What is difference reduction & what does it involve?
It is a difference of local maxima
You must move away from the goal state to solve the problem
A chicken wants food (in another location) & they must reduce the difference between their current state & the goal state (food)
There is a barrier to the food (a fence) – the chicken pecks it
Who studied chickens in this study?
Why does this problem violate difference reduction?
Kohler (1927)
By pecking the fence, the chicken is only applying difference reduction
The chicken must move away from the goal (food) to get around the barrier –> violates difference reduction
What scenarios can difference reduction be applied to?
- If you are following difference reduction, you climb up the hill & reach the peak (= the goal), & then descend
- If you are following difference reduction, you climb up the hill & reach a peak but not the highest one –> you must go down the hill to go up again to reach the highest peak - this violates difference reduction
What does the Orc problem involve?
There are 3 orcs & 3 hobbits on one side of a river bank
A boat can only take 2 creatures at a time across the bank (one must steer the boat)
Goal = get all 6 creatures to the other side of the bank
Orcs must not outnumber hobbits on either side of the bank
How do you solve the Orc problem? Why do pps tend to make mistakes?
To solve the problem, you must move away from the other side of the bank (= the goal) to pick up more creatures –> this is a backwards step
This is where pps make a mistake - they keep wanting to do difference reduction but it doesn’t solve the puzzle
What does the 9-dot problem involve?
You must connect 9 dots using 4 straight lines, without taking your pen off the paper
Why do people have difficulties with the 9-dot problem?
The dots form a square - has boundaries, so people automatically add rules…
“I have to connect dots without taking my pen off the paper AND I must do it without going outside the confines of the square”
Difficulty to do the 9-dot problem is called…
…maximisation - you are trying to maximise what you get our of your limited number of moves
