Blind Search in Graphs

Trees:
Consists of nodes connected by links (or edges).
every node has a single parent.
The root has no parents.
No cycles exist.
Graphs:
Consists of nodes connected by links (or edges).
Nodes have any number of parents.
Cycles may exists



Graphs are divided based on the type of edges they have:
Undirected graphs: are graphs where the edges between nodes have no direction.

Directed graphs: are graphs where the edges have a direction. In this case, we can move from a node to another only in the edge direction.
Input: State Space
Ouput: failure or path from a start state to a goal state.
Assumptions: L is a list of nodes that have not yet been examined.
The state space is a tree where each node has a single parent.

Set L to be a list of the initial nodes in the problem.
While L is not empty
Pick a node n from L.
If n is a goal node
stop and return it and the path from the initial node to n.
Else
remove n from L and add all of n’s children to L labelling each with its path from the initial node.
End while
Return failure
Input: State Space
Ouput: failure or path from a start state to a goal state.
Assumptions: Open is a list of nodes that have not yet been examined.
Closed is the list of states that have been examined.
Set Open to be a list of the initial nodes in the problem. At any given point in time.
While Open is not empty
Pick a node n from the front of Open.
If n is a goal node
stop and return it and the path from the initial node to n.
Else
remove n from Open
add n to Closed
get all n’s children
discard n’s children that are in the Closed or Open lists.
add the remaining children to the end of Open labelling each with its path from the initial node.
End while
return failure