Quiz 2: State Space Graph
- Due Mar 19 at 11:59pm
- Points 54
- Questions 16
- Available after Mar 5 at 9am
- Time Limit None
- Allowed Attempts 2
Instructions
State-Space Graph
- Many problems can be solved by a reduction to one of the standard graph problems.
- This is true, in particular, for a variety of puzzles and games.
- In these applications, vertices of a graph typically represent possible states of the problem in question, and edges indicate permitted transitions among such states.
- One of the graph’s vertices represents an initial state and another represents a goal state of the problem.
- (There might be several vertices of the latter kind.)
- Such a graph is called a state-space graph.
- Thus, the transformation just described reduces the problem to the question about a path from the initial-state vertex to a goal-state vertex.
Our success in solving this simple puzzle should not lead you to believe that generating and investigating state-space graphs is always a straightforward task. To get a better appreciation of them, consult books on artificial intelligence (AI), the branch of computer science in which state-space graphs are a principal subject.
Only registered, enrolled users can take graded quizzes