Problem solving using search

1. Problem Solving using Search
The breadth-first algorithm spreads out in a uniform manner from the start node. From the start, it looks at each node one edge away. Then it moves out from those nodes to all nodes two edges away from the start. This continues until either the goal node is found or the entire tree is searched.
2. Characteristics of breadth-first algorithm
• Breadth-first search is complete; It will find a solution if one exists.
• But it is neither optimal in the general case (it won’t find the best solution, just the first one that matches the goal state),
• It doesn’t have good time or space complexity (it grows exponentially in time and memory consumption).
Example
A map like the one in Figure below can be naturally represented by a graph data structure, where the cities names are the nodes, and the major roadways between cities are the links or edges of the graph. So, from a programming perspective, our problem is to traverse a graph data structure in a systematic way until we either find the goal city or exhaust all possibilities. Hopefully having the entire state-space shown on a map will make understanding the operations of the search algorithms easier. In more complex problems, all we have is the single start state and a set of operators which are used to generate more and more new states. The search algorithms work the same way, but conceptually, we are growing or expanding the graph, instead of having it specified at the start. Map of midwestern U.S. cities is illustrated below:-
The breadth-first algorithm spreads out in a uniform manner from the start node. From the start, it looks at each node one edge away. Then it moves out from those nodes to all nodes two edges away from the start. This continues until either the goal node is found or the entire tree is searched.

Let’s walk through an example to see how breadth-first search could find a city on our map.
1- Our search begins in Rochester (Start State), and we want to know if we can get to Wausau (Goal State) from there.

2- The Rochester node is placed on the queue in step 1 in previous algorithm. Next we enter our search loop at step 2. Queue=[ Rochester]

3- We remove Rochester, the first node from the queue. Rochester does not contain our goal state (Wausau) so we expand it by taking each child node in Rochester, and adding them to the back of the queue. Queue= [ Sioux Falls, Minneapolis, LaCrosse, and Dubuque ].

4- We remove the first node from the queue (Sioux Falls) and test it to see if it is our goal state. It is not, so we expand it, adding Fargo and Rochester to the end of our queue, which now contains [Minneapolis, LaCrosse, Dubuque, Fargo, and Rochester].


5- We remove Minneapolis, the goal test fails, and we expand that node, adding St.Cloud, Wausau, Duluth, LaCrosse, and Rochester to the search queue, now holding [ LaCrosse, Dubuque, Fargo, Rochester, St.Cloud, Wausau, Duluth, LaCrosse, and Rochester

6- We test LaCrosse and then expand it, adding Minneapolis, GreenBay, Madison, Dubuque, and Rochester to the list, which has now grown to [ Dubuque, Fargo, Rochester, St.Cloud, Wausau, Duluth, LaCrosse, Rochester, Minneapolis, GreenBay, Madison, Dubuque, and Rochester]. We remove Dubuque and add Rochester, LaCrosse, and Rockford to the search queue.
7- At this point, we have tested every node which is one level in the tree away from the start node (Rochester). Our search queue contains the following nodes: [Fargo, Rochester, St.Cloud, Wausau, Duluth, LaCrosse, Rochester, Minneapolis, GreenBay, Madison, Dubuque, Rochester, Rochester, LaCrosse, and Rockford].
8- We remove Fargo, which is two levels away from Rochester, and add Grand Forks, St. Cloud, and Sioux Falls.
9- Then we test and expand Rochester (Rochester to Minneapolis to Rochester is two levels away from our start). Next is St. Cloud; again we expand that node.
10- Finally, we get to Wausau; our goal test succeeds and we declare success.
11- Our search order was Rochester, Sioux Falls, Minneapolis, LaCrosse, Dubuque, Fargo, Rochester, St. Cloud, and Wausau as shown below:-