(12th-April-2020)
Algorithms (including search algorithms) can be compared on
The time taken,
The space used, and
The quality or accuracy of the results.
The time taken, space used, and accuracy of an algorithm are a function of the inputs to the algorithm. Computer scientists talk about the asymptotic complexity of algorithms, which specifies how the time or space grows with the input size of the algorithm. An algorithm has time (or space) complexity O(f(n)) - read "big-oh of f(n)" - for input size n, where f(n) is some function of n, if there exist constants n0 and k such that the time, or space, of the algorithm is less than k×f(n) for all n>n0. The most common types of functions are exponential functions such as 2n, 3n, or 1.015n; polynomial functions such as n5, n2, n, or n1/2; and logarithmic functions, log n. In general, exponential algorithms get worse more quickly than polynomial algorithms which, in turn, are worse than logarithmic algorithms.
This algorithm does not specify the order in which the neighbors are added to the stack that represents the frontier. The efficiency of the algorithm is sensitive to this ordering.
Consider a modification of the delivery graph, in which the agent has much more freedom in moving between locations. The new graph is presented in Figure 3.6. An infinite path leads from ts to mail, back to ts, back to mail, and so forth. As presented, depth-first search follows this path forever, never considering alternative paths from b3 or o109. The frontiers for the first five iterations of the path-finding search algorithm using depth-first search are
[⟨o103⟩]
[⟨o103,ts⟩, ⟨o103,b3⟩, ⟨o103,o109⟩]
[⟨o103,ts,mail⟩, ⟨o103,ts,o103⟩, ⟨o103,b3⟩, ⟨o103,o109⟩]
[⟨o103,ts,mail,ts⟩, ⟨o103,ts,o103⟩, ⟨o103,b3⟩, ⟨o103,o109⟩]
[⟨o103,ts,mail,ts,mail⟩, ⟨o103,ts,mail,ts,o103⟩, ⟨o103,ts,o103⟩,
⟨o103,b3⟩, ⟨o103,o109⟩]
Depth-first search can be improved by not considering paths with cycles.
Because depth-first search is sensitive to the order in which the neighbors are added to the frontier, care must be taken to do it sensibly. This ordering can be done statically (so that the order of the neighbors is fixed) or dynamically (where the ordering of the neighbors depends on the goal).
Comments