Problem Solving: Problem Spaces and Operators

Problem Solving, Problem Spaces, and Operators

Key Concepts

  • Problem Space: A representation of a problem by its solver. It consists of:
    • Initial State: The starting point of the problem.
    • Goal State: The desired solution or outcome.
    • Search Space: Possible paths or processes to move from the initial state to the goal state.
  • Operators: Rules or procedures that dictate actions to move from one state to another. They are akin to conditional action rules:
    • If condition is X, then perform action Y to reach a goal or sub-goal.

Types of Problems

Well-Defined Problems
  • Fully specified problem spaces.
  • **Examples:

  1. Problems of Arrangement:**

    • Solver reorders elements.
    • Example: Jigsaw puzzles.
      • Initial State: Scattered puzzle pieces.
      • Goal State: Completed picture as per cover illustration.
      • Operators used: Each move towards matching pieces.
    • Other examples include anagrams and cryptoarithmetic.
      • Anagrams: Rearranging scrambled letters to form words.
      • Cryptoarithmetic: Assigning numbers to letters to solve arithmetic problems.

  2. Problems of Inducing Structure:

    • Identify a structural relationship.
    • Example: Series extrapolation to find the next item in a pattern.
      • Given: A B C B B C C B C D B ____
    1. Problems of Transformation:
    • Change one arrangement of elements into another.
    • Example: Tower of Hanoi.
      • Decomposing the problem into smaller problems.
    1. Problems of Transformation of Arrangement:
    • Involves strategic games like chess.
    • Requires significant practice for pattern recognition (10,000-50,000 hours).
Ill-Defined Problems

  • Parts of the problem space are not fully specified.

  • Types of Ill-Defined Problems:

    1. Insight Problems:
    • Critical aspects of the initial state are recognized for solutions.
    • Example: Connect all dots with four lines.
    1. Hypothesis Testing:
    • Requires proving or disproving a hypothesis.
    • Example: Checking the hypothesis using cards.
    • Hypothesis: If there's a smiley face on the front of the card, then there's a sun on the back.
    1. Behavioral Modification:
    • Initially, we start with a certain behavior we seek to modify.
    • Use of positive/negative reinforcers.

Algorithms and Heuristics

  • Heuristic: A strategy to approach problems.
  • Algorithm: A guaranteed procedure or method for solving a problem.
  • Use a heuristic to explore ill-defined problems and discover algorithms that can provide solutions.