Problem
Solving
What is the problem
What do I know about the problem
How hard is the problem
Reduction of information to Relevant information
Apply Inductive and Deductive reasoning
Problems of interest
What is the Problem
Define the goals or subgoals to be attained
- fixed vs. moving target
- separable vs. integrated
- absolute vs. relative
- predictable vs. random
See what is given
- specific vs. generalizeable facts
- perfect vs. imperfect information
- certainty vs. uncertainty
- existing knowledge base vs. new area
- axioms and proofs vs. target shooting
Extrapolate from the "natural language" of a problem to the "natural language of the machine
- need a specific (not vague) description
- need all of the rules (constraints)
- need to "quantify" the goals
- need to handle multiple objectives
What do I know about the problem
Determine the relevant body of information
- is there a literature (start with Wikipedia & Google)
- are there theorems
- is this similar to a solved problem
- what subject area is most appropriate
- is this problem separable or decomposible
Pattern recognition and feature selection
- are there solved patterns that can be applied
- are there features that are similar to solved problems
- are there analogies that are apt
e.g. Evan's analogy (Find a transformation, apply it, find the corresponding symbol)
Representation of data
- need a knowledge representation
- must choose a data structure
- how is new knowledge added?
- do we need to learn?
- how large can the data structure get
(both in the problem and in the computer)
How Hard is the Problem
Problem difficulty is measure in terms of “n”, the size of the problem, the number of inputs, the size of the “playing field”, etc.
For each problem, need to define how “n” is measured.
Problems are classified as “EASY” or “HARD”, with the following subclassifications:
EASY:
Trivial: Small, constant effort, independent of any “n”
Practical: Effort is o(log(n)), o(n), o(n*log(n)),
o(n*log(n)*log(n)), …
Polynomial: Effort is o(n*n) or greater, but bounded by a polynomial in “n”
HARD:
NP Hard/NP Complete: Can find no algorithm that works in polynomial time. But we can verify that something is a correct answer in polynomial time. A computer with infinite parallelism could solve the problem in polynomial time.
Exponential: Both computation of a result and verification of a result provably take exponential time
Impossible: Provably impossible, even with infinite speed, infinite parallelism, infinite memory, and infinite time.
References:
· Dreyfus, Hubert (1972), What Computers Can't Do, New York: MIT Press, ISBN 0-06-090613-8
· Dreyfus, Hubert (1979), What Computers Can't Do, New York: MIT Press, ISBN 0-06-090624-3
· Dreyfus, Hubert (1992), What Computers Still Can't Do, New York: MIT Press, ISBN 0-262-54067-3
Reduction of information to RELEVANT information
May need to develop a "heuristic" for hard problems
Defn: A heuristic is a trick, a rule of thumb, a stratagem, etc. which drastically limits the search for solutions in large spaces - ideally not throwing away any "good" answers - hopefully retaining at least one "good" answer.
Heuristic functions measure the "goodness" or a "figure of merit" of a particular choice, action, subgoal, goal, or proposed solution.
Heuristics MAY lead in the wrong direction. This is sometimes called "going down the primrose path" or "going down the garden path"
Examples:
In Othello, might think that the largest number of opponents pieces flipped in a move is a good heuristic (it is not). A better heuristic is number of your pieces that the opponent cannot ever flip.
In Chess, might think that the greatest material advantage after a move is a good heuristic (it is not). This heuristic opens up the player to "classic" sacrifices.
In Checkers, might think that the greatest number of pieces captured in a move is a good heuristic (it is not). This heuristic ignores what the opponent might be able to recapture
There needs to be both major (winning) and minor (positional/power/strategic/mobility) advantage
Apply inductive and deductive reasoning, as appropriate
Need to generate measurements
Need measurements to see how close we are to a solution
Can work from both ends
Need heuristic techniques
Sometimes a figure of merit can be derived in a heuristic to find a step that is "good enough" - especially in a game
Problems of interest:
Problems where “n” is the number of digits of accuracy:
Newton’s method
Successive approximations of Pi using pi/2 = 2/1 x 2/3 x 4/3
x 4/5 x 6/5 x 6/7 x 8/7 x 8/9
Golden ratio using Fibonacci starting at 0, 1
Golden ratio using Fibonacci starting anywhere
Problems where “n” is the number of entries in an array, table, or file:
Sorting
Searching
Statistical computation
Payroll
Missionaries and Cannibals (n of each, canoe for m)
Problems where a proof is desired for every integer or rational number or real value, “n” is the number of steps in the proof:
Collatz’s conjecture (3n +1 or divide by 2 problem)
Problems where “n” is the size of one side of a square:
Tic-Tac-Toe (on an n x n grid – not just 3 x 3)
Sudoku
Travelling Salesperson
Pairing people for a dance
Problem Solving 4 Copyright © 1971-2010 Thomas P. Sturm