## 5 Algorithm Analysis
### Number of Trips Using the Required Number of Steps: General Case  
In the general case, the interest is to visit several nodes repeatedly in order to obtain valuable nodes, contrary to the goal in the best case. Therefore, the focus is to obtain the average number of trips to explore the DFG considering the heuristics of our proposal. In order to calculate the average number of trips, the environment is divided into rows and columns. The rows correspond to the levels in the graph while the columns are represented by the width of the graph. This division is shown in Figure 9. The columns correspond to the blue nodes, and the levels start at the base station. Only the blue nodes are considered because if a blue node is visited, there is a chance to visit all the nodes in the column due to the heuristics of the proposed solution. For example, if the current node is 3, the MDF will choose 4 over 14 and 2 because the distance from 4 to the base station is greater than all the adjacent nodes of the current node. Since there are many possibilities to travel in the blue nodes, it is necessary to calculate the number of trips on average to stamp every node in the column. Table 2 shows the average ways we need  
Figure 8: The best way to explore a graph with the required number of steps is by having each trip visits both a line and its adjacent line. Since there are \(p_{h}\) lines, that is the minimum number of trips to explore the whole graph. In this particular example, \(p_{h}\) is equal to five. Figure 9: Lines divide the environment in rows and columns. to pass by each blue node in order to stamp every node in that column. The first column of Table 2 contains each blue node, and the second column presents the average number of ways a particular blue node can have all its siblings visited based on the DFORE algorithm. The number of average trips is the number of edges the MDF can take from a blue node using the heuristics of the algorithm. For example, for the blue node 2, there are four possible edges. The first edge is in the line that consists of nodes [14; 15; 6]; the second edge is from node 2 to 3; the third edge is from 14 to 4; and the last edge is from 15 to 5. There is not an edge between 6 and 5 since it is impossible to get from 6 to 5 with the required number of steps. Therefore, the number of edges of all blue nodes is the average number of trips required to explore the graph. We show the equation of the expected number of trips for any given DFG. **Definition 3**. : _Given a DFG \(G_{h}\) with depth \(p_{h}\) (see Equation (1)). The expected average number of trips \(T_{h}\) is:_  
\[T_{h}=2p_{h}+2\sum_{j=1}^{h-2}(p_{h}-j)+1. \tag{10}\]  
However, there is a simpler way to calculate the expected average number of trips for any given DFG. To obtain the expression, a table for each environment is built. Table 3 shows each DFG \(G_{h}\) with the correspondent variables. In the first column, the size of each DFG is shown. The second column contains the number of nodes in each DFG. The third column shows the depth of the graphs. Finally, the difference between the number of nodes of DFG of size \(h\) and \(h-1\) is presented in the last column. We note that each successive environment grows by a fixed amount of six as shown in the last row of the table. For example, with the DFG \(G_{3}\), the number of nodes is 19, while for the DFG it is 7, and their difference is 19 - 7, which is equal to 12. Taking into consideration the growth of each successive Hextille, the number of regions for any Hextille is given by the following expression: \(n_{h}=3h^{2}-3h+1\) (see Appendix B). Finally, the expected average number of trips is \(T_{h}=3h^{2}-3h+1\) (see Appendix A). Therefore, \(T_{h}=n_{h}\). Furthermore, to get the computational cost of the general case, consider that the number of nodes visited by each trip is \(2\epsilon_{h}\). Therefore, if there are \(T_{h}\) trips, the total number of nodes is \(2T_{h}\epsilon_{h}\). Since