Hot-Link Menu in Right-Side Column

Shop the Low Price Leader from Home
WM468X60_ko_static.gif


Frontier Node Expansion

In other cases, redundant paths are unavoidable. This includes all problems where the actions are reversible, such as route-finding problems and sliding-block puzzles. Route finding on a rectangular grid is particularly important in computer games. Initially, our unexplored grid appears as follows:

Unexplored Grid

Figure Agent-9: Unexplored Rectangular Grid - Frontier Only


In such a grid, each state has four successors, so when we initialize our first state it may look like:


Rect Grid 1

Figure Agent-10: Only Root explored - Explored Node In Black - 4 Frontier Nodes in White


Expanding the frontier node above the root node gives us:


Rect Grid 2

Figure Agent-11: One Frontier Node Expanded (White==>Black)


A search tree of depth 5 has 45 or 1024 leaves, but only 2 * 5 2 (50) distinct states within 5 steps of any given state. However, if we have a 20 x 20 grid, there may be a trillion nodes but only 800 distinct states. Thus, following redundant paths can cause a tractable problem to become intractable. This can be true, even if the algorithm knows how to avoid infinite loops.

As the saying goes, algorithms that forget their history are doomed to repeat it. The way to avoid exploring redundant paths is to remember where one has been. To do this, we augment the Tree-Search algorithm with a data structure called the explored set, which remembers every expanded node. Sometimes this is called a closed list or explored set = closed list. Newly generated nodes that match previously generated nodes - ones in the explored set or the frontier - can be discarded instead of potentially being added to the frontier. The new algorithm called Graph-Search is shown in the lower section of Figure Agent-7:

When the search tree is constructed by Graph-Search in the line:add the node to the explored set the algorithm contains at most one copy of each state(city) so we can think of it as growing a tree directly on the state-space graph, as shown in Figure Agent-12:

Rom Search 1

Figure Agent-12: Initial Search Tree starting at Arad

  1. Arad ==> Explored Set
  2. Expand Arad
    • Are Zerind, Sibiu or Timisoara in the explored set?
      • If no then:
      • Are Zerind, Sibiu or Timisoara in the Frontier?
        • If no then:
        • Zerind, Sibiu or Timisoara ==> Frontier
  3. If any of the nodes haven't been expanded yet, go back to step 1 with it.
Explored Frontier
Arad Zerind
Sibiu
Timisoara

In the next step we expand each of the frontier nodes starting with Zerind, then Sibiu, and finally Timisoara. Following the rules outlined above gives us the following expansion:

Rom Search 2

Figure Agent-13: Search Tree after Second Pass

Explored Frontier
Arad
Zerind
Sibiu
Timisoara
Oradea
Fagaras
Rimnicu Vilcea
Lugoj

On the third pass, we first find out the Oradea is a dead end since Zerind and Sibiu are both now in the explored category. As we start to expand Fagaras we first check to see if Bucharest is the goal state - it is, and the search algorithm terminates, as we have found our goal.

If your goal is to have a website without all of those annoying little ads and plugs for products that you really don't want to look at anyways, may we suggest that you look at Site-5 by clicking the link below. Site 5 has excellent technical support, unlimited disk storage and support for Python, C++, PHP and MySql:

Excellent Tech Support - Centurion Approved

Infrastructure for Search Algorithms

Search algorithms require a data structure to keep track of the search tree that is being constructed. For each node n of the tree, we have a structure that contains 4 components:

  1. n.State: The state in the state space to which the node corresponds.
  2. n.Parent: The node in the search tree that generated this node.
  3. n.Action: The action that was applied to the parent to generate the node.
  4. n.Path-Cost: The cost, traditionally denoted by g(n), of the path from the initial state to the goal, as indicated by parent pointers.

Child Node Creation

Given the components for a parent node, it is easy to see how to compute the necessary components for a child node. The function Child-Node takes a parent node and an action and returns the resulting child node:

Function Child-Node(problem, parent, action)returns a node
  return a node with
    State =problem.Result(parent. State, action),
    Parent =parent
    Action =action
    Path-Cost =parent.Path-Cost + problem.Step-Cost(parent. State, action)

Figure Agent-14: Pseudocode to Create a Child-Node


The node data structure is depicted in Figure Agent-15. Notice how the Parent pointers string the nodes together into a tree structure. These pointers also allow the solution path to be extracted when a goal node is found; we use the Solution function to return the sequence of actions obtained by following parent pointers back to the root.

By following the pointers in the link below, you can help yourself to low prices, great service and Top Name Brands in Computer Software like Adobe, Microsoft and Intuit:

Centurion Online → Software → Programming Software

Node Example

Figure Agent-15: Node Example

Nodes are the data structures from which teh search tree is constructed. Each has a parent, a state, and various bookkeeping fields. Arrows point from child to parent.


Up to now, we haven't been very careful to distinguish between nodes and states, but in writing detailed algorithms it's important to make that distinction. A node is a bookkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world. Thus, nodes are on particular paths, as defined by Parent pointers, whereas states are not. Furthermore, two different nodes can contain the same world state if that state is generated via two different search paths.

Now that we have nodes, we need somewhere to put them. The frontier needs to be stored in such a way that the search algorithm can easily choose the next node to expand according to its preferred strategy. The appropriate data structure for this is a queue. The operations on a queue are as follows:

  • Empty? (queue) returns true only if there are no more elements in the queue.
  • Pop (queue) removes the first element of the queue and returns it.
  • Insert (element, queue) inserts an element and returns the resulting queue.

Queues are characterized by the order in which they store the inserted nodes. Three common variants are the first-in, first-out or FIFO queue, which pops the oldest element of the queue; the last-in, first-out or LIFO queue (also known as a Stack), which pops the newest element of the queue; and the priority queue, which pops the element of the queue with the highest priority according to some ordering function.

The explored set can be implemented with a hash table to allow efficient checking for repeated states. With a good implementation, insertion and lookup can be done in roughly constant time, independent of the number of states stored. One must take care to implement the hash table with the right notion of equality of states stored. One must take care to implement the hash table with the right notion of equality between states. For example, in the traveling salesperson problem, the hash table needs to know that the set of visited cities: {Bucharest, Urziceni, Vaslui} is the same as {Urziceni, Vaslui, Bucharest}. Sometimes this can be achieved most easily by insisting that the data structures for states be in some canonical form; that is, logically equivalent states should map to the same data structure. In the case of states described by sets, for example, a bit-vector representation or a sorted list without repetition would be canonical, whereas an unsorted list would not.

Measuring Problem Solving Performance

Before we get into the design of specific search algorithms, we need to consider the criteria that might be used to choose among them. We will evaluate an algorithm's performance in 4 ways:

  1. Completeness: Is the algorithm guaranteed to find a solution when there is one? Hopefully it doesn't get tired and give up.
  2. Optimality: Does the strategy find the optimal solution? i.e. lowest cost possible.
  3. Time Complexity: How long does it take to find a solution? Just a little short of never.
  4. Space Complexity: How much memory is needed to perform the search? Memory conservation is not as important as it once was.

Time and space complexity are always considered with respect to some measure of the problem difficulty. In theoretical computer science, the typical measure is the size of the state space graph, |V| + |E|, where V is the set of vertices (nodes) of the graph and E is the set of edges (links). This is appropriate when the graph is an explicit data structure that is input to the search program. (The map of Romania is an example of this.) In Artificial Intelligence, the graph is often represented implicitly by the initial state, actions and transition model and is frequently infinite. For these reasons, complexity is expressed in terms of three quantities:

  1. Branching factor: Maximum number of successors of any node.
  2. Depth: How many levels deep from the root node the tree branches go.
  3. Maximum Length: The maximum length (cost) of any of the paths in the state space.

Time is often measured in terms of the number of nodes generated during the search, and space in terms of the maximum number of nodes stored in memory. For the most part, we will describe time and space complexity for search on a tree; for a graph, the answer will depend on how "redundant" the paths in state space are.

To assess the effectiveness of a search algorithm, we can consider just the search cost - which typically depends on the time complexity but can also include a term for memory usage - or we can use the total cost, which combines the search cost and the path cost of the solution found. For the problem of finding a route from Arad to Bucharest, the search cost is the amount of time taken by the search and the solution cost is the total length of the path in kilometers. Thus, to compute the total cost, we have to add milliseconds and kilometers. There is no "official exchange rate" between the two, but, in this case, it might be reasonable to convert kilometers into milliseconds by using an estimate of the car's average speed (because time is what the agent cares about). This enables the agent to find an optimal tradeoff point at which further computation to find a shorter path becomes counterproductive.

Holding on to an antiquated computer system can also be counterproductive. Determining your optimal tradeoff point has just gotten a little easier by checking out the vast selection, great prices and awesome technical support available on brand name products such as Intel, HP, Samsung, ASUS and Apple when you follow the links to:

Centurion Online → Computers → Desktops

In order to continue with this guide, and continue the discussion on Uninformed Search Strategies (Breadth and Depth 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