HotLink Menu in RightSide Column 
Shop Online → Store Pickup → Free Shipping: 


Uninformed Search StrategiesThis section covers several search strategies that come under the heading of uninformed search also called blind search. The term means that the strategies have no additional information about states beyond that provided in the problem definition. All they can do is generate successors and distinguish a goal state from the nongoal state. All search strategies are distinguished by the order in which the nodes are expanded. Strategies that know whether one nongoal state is "more promising" than another are call informed search or heuristic search strategies. But, we really don't care about those right now since the heading on this section is: Uninformed Search Strategies. BreadthFirst SearchThe setup for this problem is explained in the section: Problem Solving Agents referring to the section on the Romanian map problem. BreadthFirst Search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. In general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded. Breadthfirst search is an instance of the general graph search algorithm (refer to Figure Agent7) in which the shallowest unexpanded node is chosen for expansion. This is achieved very simply by using a FIFO queue for the frontier. Thus, new nodes (which are always deeper than their parents) go to the back of the queue and old nodes, which are shallower than the new nodes, get expanded first. There is one slight tweak on the general graph search algorithm, which is that the goal test is applied to each node when it is generated, rather than when it is selected for expansion. This decision is explained below, where we discuss time complexity. Note also that the algorithm, following the general template for graph search, discards any new path to a state already in the frontier or explored set; it is easy to see that any such path must be at least as deep as the one already found. Thus, breadthfirst search always has the shallowest path to every node on the frontier. Figure BFS1 shows the pseudocode for the breadthfirst search:
BreadthFirst Search CharacteristicsThe breadthfirst search strategy is complete  that is, if the shallowest goal node is at some finite depth d, breadthfirst search will eventually find it after generating all shallower nodes, provided the branching factor is finite. Note that as soon as a goal is generated, we know that it is the shallowest goal node because all shallower nodes must have been generated already and failed the goal test. Now, the shallowest goal node is not necessarily the optimal one. The breadthfirst search is optimal only if the path cost is a nondecreasing function of the depth of the node. The most common such scenario is that all actions have the same cost. The following diagram, BFS2, shows the progress of the BreadthFirst Search. The arrow points to the node that is to be expanded. The explored nodes are in gray, the nodes in the frontier are in light blue, and unexplored nodes are in white:
C++ BreadthFirst Search Code DevelopmentWe begin by developing a data stucture to contain the information in the following diagram:
BreadthFirst Data StructureThe first thing we will need is a data representation of the Romanian Map in Figure BFS3. For this example we will use C/C++. Following is the code for the C++ breadthfirst search:
Doesn't look too bad, yet. Our Neighbor structure
We don't really need the Shortest distance yet, but it comes in handy for the A* search, so we are going to include it now. The City structure represents the City we are in:
The city we are in has a name (like Oradea), and it has some neighboring Cities (like Zerind and Sibiu). I am going to call the neighboring cities 'Neighbors', but you can call them 'GuysNextDoor' when you write the code, or have your own webpage. We don't know how many neighboring cities we will have. Could be 1, could be a hundred. We need to put each Neighbor in its own box, so I decided to use the 'vector' data container, because it kind of acts like an array, but better, since it adjusts to the size of our data set. So, we have an array of neighbors for each city, and the vector will keep track of all the bookkeeping for us. And finally, we need to consider all the cities as a group, so I am going to make an array(vector) of all the cities: i.e. Oradea=first city, Zerind=2nd city, and so on giving us our last data element: vector<City> CitiesCities, which is a collection of all the cities on our map. Since we don't have collections of countries, it is not necessary to make a 'Cities' structure. In order to continue with this guide, and continue the discussion on Developing the Main() program for BreadthFirst Search: Press the Button below: 
Last Updated 7272010Big O Notation NP Completeness Intelligent Agents Formulating Problems Toy Problems Vacuum World 8 Queens The Knuth Sequence Real World Problems Route Finding Problems Touring Problems Traveling Salesperson Problem VLSI Layout Robot Navigation Automatic Assembly Sequencing Search Algorithm Infrastructure Child Node Creation Measuring Algorithm Performance BreadthFirst Search BreadthFirst Characteristics C++ BreadthFirst Search Code BreadthFirst Data Structure BreadthFirst Make Map BreadthFirst Make Neighbor BreadthFirst Point of Origin BreadthFirst Initial Listing BreadthFirst Get Child City C++ BreadthFirst Search Code UniformCost Search DepthFirst C++ Solution DepthFirst Data Structure DepthFirst Display Data DepthFirst Initial Listing DepthFirst Path Record DepthFirst Main() DepthLimited Search Bidirectional Search Comparing Strategies Greedy BestFirst A* Search Optimality of A* A* Search Data Structure A* Search Data Entry C++ Min Priority Queue C++ A* Headers & Prototypes C++ A* Search Main() 