Problem Solving By Search

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.
Euler focused on the degree of the nodes of the graph
?Even degree node has an even number of arcs joining it to neighboring nodes.
?Odd degree node has an odd number of arcs.
?Unless a graph contained either exactly zero or two nodes of odd degree, the walk was impossible.
?No odd degree node: the walk start at the first and end at the same node
?Two odd degree nodes: the walk could start at the first and end at the second