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.
K?nigsberg Bridge System
?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
A graph consists of nodes and arcs
?A set of nodes N1, N2, …, Nn … need not be finite.
?A set of arcs connects pairs of nodes.
?A directed graph has an indicated direction for traversing each
?If a directed arc connects Nj and Nk, then Nj is called the parent of Nk and Nk is called the child of Nj.
?A rooted graph has a unique node Ns from which all paths in the graph originate
?A tip or leaf node is a node without children.
?An ordered sequence of nodes [N1, N2, N3, … Nn] is called a path of length n-1 in the graph