Problem and Instance

  • Basic idea from algorithms

  • An instance is

    • Some specific description of a situation

    • Some description of what is wanted in that situation

  • A problem is a collection of related instances

  • A class is a collection of related problems

Example: Sorting

  • Instance of natural-number sorting

    Given: 1 3 2
    Produce: The three numbers arranged in increasing order
    
  • Natural Number Sorting Problem

    Given: A sequence of natural numbers
    Produce: The sequence arranged in increasing order
    
  • Class of sorting problems includes natural-number sorting, floating-point number sorting, string sorting, 2D sorting, nD sorting, etc

Computational Complexity

  • Nearly all sorting problems have algorithms with worst-case asymptotic running time O(n log n) where n is the length of the sequence

  • If the previous sentence looks unfamiliar or confusing to you, you probably aren't ready for this course yet. Get out, go take a good Algorithms class (our CS 350), and then come back in a future quarter

AI Problems

  • In AI, a problem is likely to be

    • Fuzzily specified: want a "smart answer" that is "good enough"

    • Hard: No efficient algorithm is known to exist for large / hard instances

    • Human-tractable: Humans demonstrably do a reasonable job on real-world instances

  • "AI Complete" problems are those for which a good solution will require general intelligence

  • (Conversely, a general intelligence would handle standard algorithms problems)

Problem: Pathfinding

  • Instance: A map

  • Solution: A good route through that map

  • Issues:

    • How much detail is in the map? Like a Google map? A treasure map? A photo?

    • Similar: How is the map represented? A graph? An image? Something else?

    • What is a "good" route? Short? Low-effort? Safe?

  • Dijkstra's Algorithm or similar search is good for small instances of simple problems

  • Super-fancy AI techniques are used on some kinds of real-world problem

Abstraction

  • Abstract away "irrelevant" details

  • For example, take image to Google Map (fancy graph), Google Map to simple graph

  • Hard to tell what is irrelevant

Last modified: Monday, 28 September 2020, 12:51 AM