Hot-Link Menu in Right-Side Column

Shop Online → Store Pickup → Free Shipping:
Wal-Mart.com USA, LLC


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.

Breadth-First Search

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:

Function Breadth-First Search(problem)returns a solution or failure
  node ← a node with State= problem.Initial State, Path-Cost=0
  If problem.Goal-Test(node.State) then return Solution(node)
  frontier ← a FIFO queue with node as the only element
    i.e. frontier.Push(node)
  explored ← ∅
  loop do
    if frontier == ∅ then return failure
    CurrentNodefrontier.Pop
    exploredCurrentNode
  for each pointer in CurrentNode do
      childCurrentNode.pointer
      If child.Name ∉ explored then
        If child.Name ∉ frontier then
          If child.Name == Goal then return child. Name
            frontier.Push(child)

Figure BFS-1: Pseudocode for Breadth-First Search of Romania Map


Excellent Tech Support - Centurion Approved

Breadth-First Search Characteristics

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:

Breadth First Progress

Figure BFS-2: Progress of Breadth-First Search through subsequent levels.


C++ Breadth-First Search Code Development

We begin by developing a data stucture to contain the information in the following diagram:

Romania map

Figure BFS-3: Data Source for C++ Depth-First Code Example


Breadth-First Data Structure

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:

struct Neighbor
{
  string Name;
  int Distance;
  int ShortestDistance;
};

struct City
{
  string Name;
  vector<Neighbor> Neighbors;
};
vector<City> Cities;

Figure BFS-4: Romanian Map Data Structure


Doesn't look too bad, yet. Our Neighbor structure

  • struct Neighbor: represents any bordering City.
  • string Name: The name of the neighboring city (like Oradea)
  • int Distance: The distance between the neighbor and city we are in (like 71 between Oradea and Zerind).
  • int Shortest Distance: Straightline distance from our neighbor to Bucharest.

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:

  • struct City: A data representation of the city we are in.
  • string Name: The name of the city we are building (i.e. Oradea).
  • vector<Neighbor> Neighbors An array-like container holding all the information about the neighboring cities.

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> Cities

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.


In order to continue with this guide, and continue the discussion on Developing the Main() program for Breadth-First Search: Press the Button below:

Last Updated 7-27-2010

Home


Artificial Intelligence

Big O Notation

NP Completeness

Intelligent Agents


Problem Definition

Formulating Problems

Toy Problems

Vacuum World


8-Puzzle

8 Queens

The Knuth Sequence

Real World Problems

Route Finding Problems

Touring Problems

Traveling Salesperson Problem

VLSI Layout

Robot Navigation

Automatic Assembly Sequencing


Searching For Solutions


Frontier Node Expansion

Search Algorithm Infrastructure

Child Node Creation

Measuring Algorithm Performance


Uninformed Search Strategies

Breadth-First Search

Breadth-First Characteristics

C++ Breadth-First Search Code

Breadth-First Data Structure


Breadth-First Main Program

Breadth-First Make Map

Breadth-First Make Neighbor

Breadth-First Point of Origin


Breadth-First Print Cities

Breadth-First Initial Listing


Breadth-First Path Record

Breadth-First Get Child City

C++ Breadth-First Search Code


Breadth-First Print Goal Path

Uniform-Cost Search


Depth-First Search

Depth-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()

Depth-Limited Search


Iterative Depth Search

Bidirectional Search

Comparing Strategies


Informed Search Strategies

Greedy Best-First

A* Search


Conditions For Optimality

Optimality of A*


C++ A* Search Code

A* Search Data Structure

A* Search Data Entry


A* Search GetChildCity()

C++ Min Priority Queue


C++ A* Search Code Function

C++ A* Headers & Prototypes

C++ A* Search Main()


Normalized Information Distance