Psychological studies of Problem Solving

In order to investigate what approach to problem solving individuals use, psychologists developed the method of protocol analysis

This requires people of verbalise their thought processes during problem solving

DFS and BFS strategies don't match human behavior:People show greater difficulty at some points during solving than others - not necessarily those with more choices.For complex tasks (e.g., chess), both methods can require very large memory capacity.People learn better strategies with experience: Novices may not find the best solution, but experts may outperform computers. 

People appear to use rules of thumb, or heuristics, to help guide the search.One simple heuristic is hill-climbing. This heuristic is applicable when there is some measure of "distance" between states. In M&C, distance between any state and the end state may be the number of cannibals remaining on left bank of river.

Problem-solving research has revealed several distinct heuristics that appear to be employed in certain situations (beyond simple hill-climbing, used when attempting to solve Missionaries and Cannibals), including backward chaining: working backwards from a desired state towards the initial-state Means-End Analysis or operator subgoaling (setting intermediate milestones, such as identifying an essential state or move and working towards that, instead of the true desired state) Progressive deepening (exploring paths in the state space of a given length, ruling out some of those paths as dead-ends, and then repeating this process but considering progressively longer paths)

Many of the empirical findings concerning knowledge-learn problem solving have been explored and replicated within computational models of the problem solving process: Logic Theorist (LT) General Problem Solver (GPS) by Ernst and Newell (1969) Universal Weak Method

Problems with hill-climbing: can lead to dead-ends: states which are not a desired state but for which each move appears to lead further away from a desired state. Thus, heuristics are not infallible!

Protocol analysis

Results of using Protocol Analysis