Hot-Link Menu in Right-Side Column
Shop Online → Store Pickup → Free Shipping:
Uninformed Search Strategies
This 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 non-goal state. All search strategies are distinguished by the order in which the nodes are expanded. Strategies that know whether one non-goal 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.
The setup for this problem is explained in the section: Problem Solving Agents referring to the section on the Romanian map problem.
Breadth-First 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.
Breadth-first search is an instance of the general graph search algorithm (refer to Figure Agent-7) 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, breadth-first search always has the shallowest path to every node on the frontier. Figure BFS-1 shows the pseudocode for the breadth-first search:
The breadth-first search strategy is complete - that is, if the shallowest goal node is at some finite depth d, breadth-first 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 breadth-first 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, BFS-2, shows the progress of the Breadth-First 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:
We begin by developing a data stucture to contain the information in the following diagram:
The first thing we will need is a data representation of the Romanian Map in Figure BFS-3. For this example we will use C/C++. Following is the code for the C++ breadth-first 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:
Cities, 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.
Last Updated 7-27-2010
Artificial IntelligenceBig O Notation
Problem DefinitionFormulating Problems
The Knuth Sequence
Real World Problems
Route Finding Problems
Traveling Salesperson Problem
Automatic Assembly Sequencing
Searching For Solutions
Frontier Node ExpansionSearch Algorithm Infrastructure
Child Node Creation
Measuring Algorithm Performance
Uninformed Search StrategiesBreadth-First Search
C++ Breadth-First Search Code
Breadth-First Data Structure
Breadth-First Main ProgramBreadth-First Make Map
Breadth-First Make Neighbor
Breadth-First Point of Origin
Breadth-First Print CitiesBreadth-First Initial Listing
Breadth-First Path RecordBreadth-First Get Child City
C++ Breadth-First Search Code
Breadth-First Print Goal PathUniform-Cost Search
Depth-First SearchDepth-First C++ Solution
Depth-First Data Structure
Depth-First MakeMap()Depth-First Display Data
Depth-First Initial Listing
Depth-First GetChildCity()Depth-First Path Record
Depth-First Search Function
Depth-First PrintGoalPath()Depth-First Main()
Iterative Depth SearchBidirectional Search
Informed Search StrategiesGreedy Best-First
Conditions For OptimalityOptimality of A*
C++ A* Search CodeA* Search Data Structure
A* Search Data Entry
A* Search GetChildCity()C++ Min Priority Queue
C++ A* Search Code FunctionC++ A* Headers & Prototypes
C++ A* Search Main()
Normalized Information Distance