Problem Solving by Intelligent Search

Introduction
Graph Theory
Structures for state space search
state space representation of problems
Strategies for state space search
Data-Driven and Goal-Driven Search
Implementing Graph Search
Depth-First and Breadth-First Search
Depth-First Search with Iterative Deepening
Using the State Space to Represent Reasoning with the Predicate Calculus
State Space Description of a Logical System
AND/OR graphs
Examples and Applications
Questions for designing search algorithms
Is the problem solver guaranteed to find a solution?
Will the problem solver always terminate?
When a solution is found, is it guaranteed to be optimal?
What is the complexity of the search process?
How can the interpreter most effectively reduce search complexity?
How can the interpreter effectively utilize a representation language?
State space search is the tool for answering these questions.
A graph consists of nodes and a set of arcs or links connecting pairs of nodes.
Nodes are used to represent discrete states.
A configuration of a game board. (tic-tac-toe)
Arcs are used to represent transitions between states.
Legal moves of a game
Leonhard Euler invented graph theory to solve the “bridge of K?nigsberg problem”
Is there a walk around the city that crosses each bridge exactly once.