ConceptTheory & Algos
Search problem
A computational problem where there can be multiple correct answers or no answer at all.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Function problem2Actions and costs1Basic algorithms1Decision problem1State representation1State space1Successor function1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Pieter Abbeel
A formalization of a problem consisting of a state space, a successor function, a start state, and a goal test.Ryan O'Donnell
A problem with a string input and a string output where there may be zero, one, or multiple correct answers.Erik Demaine
The problem of maintaining a set of objects subject to insert, delete, and query operations.
Lectures that assume it
8- Harvard CS50’s Artificial Intelligence with Python – Full University Course
- Markov Decision Processes (MDPs) Part 1/2
- Integer Lower Bounds
- Constraint Satisfaction Problems (CSPs) Part 1/2
- Quantum Query Complexity
- Constraint Satisfaction Problems (CSPs) Part 2/2
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Beyond Worst-Case Analysis
Connections
21The lectures that define it or assume it, and the concepts next to it.
Concepts8
- Function problem
- Decision problem
- State representation
- Constraint satisfaction problem
- Heuristics
- Search-to-decision reduction