(7th-April-2020)
• Consider the problem of the delivery robot finding a path from location o103 to location r123 in the domain depicted in Figure 3.1. In this figure, the interesting locations are named. For simplicity, we consider only the locations written in bold and we initially limit the directions that the robot can 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={mail,ts,o103,b3,o109,...} and the arcs are A={⟨ts,mail⟩, ⟨o103,ts⟩, ⟨o103,b3⟩, ⟨o103,o109⟩, ...}. Node o125 has no neighbors. Node ts has one neighbor, namely mail. Node o103 has three neighbors, namely ts, b3, and o109.
There are three paths from o103 to r123:
⟨o103, o109, o119, o123, r123⟩
⟨o103, b3, b4, o109, o119, o123, r123⟩
⟨o103, b3, b1, b2, b4, o109, o119, o123, r123⟩
If o103 were a start node and r123 were a goal node, each of these three paths would be a solution to the graph-searching problem.
In many problems the search graph is not given explicitly; it is dynamically constructed as needed. All that is required for the search algorithms that follow 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 arcs leaving the node. The backward branching factor of a node is the number of arcs entering the node. These factors provide measures of the complexity of graphs. When we discuss the time and space complexity of the search algorithms, we assume that the branching factors are bounded from above by a constant.
Comments