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