3.3 Graph Searching

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

3.3.1 Formalizing Graph Searching

A directed graph consists of

  • •

    a set N of nodes and

  • •

    a set A of arcs, where an arc is an ordered pair of nodes.

In this definition, a node could be anything. There may be infinitely many nodes and arcs. We do not assume that a graph is represented explicitly; we require only a procedure to generate nodes and arcs as needed.

The arc ⟨n1,n2⟩ is an outgoing arc from n1 and an incoming arc to n2.

A node n2 is a neighbor of n1 if there is an arc from n1 to n2; that is, if ⟨n1,n2⟩∈A. Note that being a neighbor does not imply symmetry; just because n2 is a neighbor of n1 does not mean that n1 is necessarily a neighbor of n2. Arcs may be labeled, for example, with the action that will take the agent from one node to another or with the cost of an action or both.

A path from node s to node g is a sequence of nodes ⟨n0,n1,…,nk⟩ such that s=n0, g=nk, and ⟨ni-1,ni⟩∈A; that is, there is an arc from ni-1 to ni for each i. Sometimes it is useful to view a path as the sequence of arcs, ⟨n0,n1⟩, ⟨n1,n2⟩,…, ⟨nk-1,nk⟩, or a sequence of labels of these arcs. Path ⟨n0,n1,…,ni⟩ is an initial part of ⟨n0,n1,…,nk⟩, when i≤k.

A goal is a Boolean function on nodes. If goal⁢(n) is true, we say that node n satisfies the goal, and n is a goal node.

To encode problems as graphs, one node is identified as the start node. A solution is a path from the start node to a node that satisfies the goal.

Sometimes there is a cost – a non-negative number – associated with arcs. We write the cost of arc ⟨ni,nj⟩ as cost⁢(⟨ni,nj⟩).

The costs of arcs induce a cost of paths. Given a path p=⟨n0,n1,…,nk⟩, the cost of path p is the sum of the costs of the arcs in the path:

cost⁢(p)=∑i=1kcost⁢(⟨ni-1,ni⟩)=cost⁢(⟨n0,n1⟩)+…+cost⁢(⟨nk-1,nk⟩)

An optimal solution is one of the solutions that has the lowest cost. That is, an optimal solution is a path p from the start node to a goal node such that there is no path p′ from the start node to a goal node where cost⁢(p′)<cost⁢(p).

Figure 3.2: A graph with arc costs for the delivery robot domain
Example 3.5.

Consider the problem of the delivery robot finding a path from location o⁢103 to location r⁢123 in the domain shown in Figure 3.1. In that figure, the interesting locations are named. For simplicity, we consider only the locations shown in bold and we initially limit the directions that the robot is able to travel. Figure 3.2 shows the resulting graph where the nodes represent locations and the arcs represent possible single steps between locations. In this figure, each arc is shown with the associated cost of getting from one location to the next.

In this graph, the nodes are N={𝑚𝑎𝑖𝑙,𝑡𝑠,o⁢103,b⁢3,o⁢109,…} and the arcs are A={⟨𝑡𝑠,𝑚𝑎𝑖𝑙⟩,⟨o⁢103,𝑡𝑠⟩,⟨o⁢103,b⁢3⟩,⟨o⁢103,o⁢109⟩,…}. Node o⁢125 has no neighbors. Node ts has one neighbor, namely mail. Node o⁢103 has three neighbors, namely ts, b⁢3, and o⁢109.

There are three paths from o⁢103 to r⁢123:

⟨o⁢103,o⁢109,o⁢119,o⁢123,r⁢123⟩⟨o⁢103,b⁢3,b⁢4,o⁢109,o⁢119,o⁢123,r⁢123⟩⟨o⁢103,b⁢3,b⁢1,b⁢2,b⁢4,o⁢109,o⁢119,o⁢123,r⁢123⟩

If o⁢103 were the start node and r⁢123 were the unique goal node, each of these three paths would be a solution to the graph-searching problem. The first of these is an optimal solution, with a solution cost of 12+16+9+4=41.

A cycle is a nonempty path where the end node is the same as the start node – that is, ⟨n0,n1,…,nk⟩ such that n0=nk. A directed graph without any cycles is called a directed acyclic graph (DAG). Note that this should be called an acyclic directed graph, because it is a directed graph that happens to be acyclic, not an acyclic graph that happens to be directed, but DAG sounds better than ADG!

A tree is a DAG where there is one node with no incoming arcs and every other node has exactly one incoming arc. The node with no incoming arcs is called the root of the tree. A node with no outgoing arcs is called a leaf. In a tree, neighbors are often called children, and we use the family-tree metaphor, with grandparents, siblings, and so on.

In many problems the search graph is not given explicitly, but is dynamically constructed as needed. For the search algorithms, all that is required is a way to generate the neighbors of a node and to determine if a node is a goal node.

The forward branching factor of a node is the number of outgoing arcs from the node. The backward branching factor of a node is the number of incoming arcs to the node. These factors provide measures for the complexity of graph algorithms. When we discuss the time and space complexity of the search algorithms, we assume that the branching factors are bounded, meaning they are all less than some postive integer.

Example 3.6.

In the graph of Figure 3.2, the forward branching factor of node o⁢103 is three because there are three outgoing arcs from node o⁢103. The backward branching factor of node o⁢103 is zero; there are no incoming arcs to node o⁢103. The forward branching factor of mail is zero and the backward branching factor of mail is one. The forward branching factor of node b⁢3 is two and the backward branching factor of b⁢3 is one.

The branching factor is an important key component in the size of the graph. If the forward branching factor for each node is b, and the graph is a tree, there are bn nodes that are n arcs away from the start node.