Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
Exercise 11.1
What determines whether the branching factor of a bottom- up tree for a system will be lower or higher than the branching factor of a top-down tree? 114 Figure 11.1 Top-down search. 11.2 BREADTH VERSUS DEPTH Having decided between a top-down search and a bottom-up search, we then have to further decide on a procedure for searching the tree. Keep in mind that any formal system of su fficient interest for artifi- cial intelligence researchers to be investigating will be considerably more complex than the toy examples we are looking at here. Consequently, choosing an appropriate search procedure can have a significant impact on the computational resources required to carry out the search. In fact, as we shall see, it can mean the di fference between a successful search and a search which never halts. A breadth first search involves exhaustively searching all the nodes at a given level before descending to the next level. Figure 11.3 shows the order in which we would search the nodes of a tree if we were con- ducting a breadth first, left first search. A clear advantage of breadth first search is that it is exhaustive. If there are solution states to be found anywhere on the tree, the search will find them. A downside of breadth first search, however, is that it can be much more computationally expensive than necessary. This is particularly the case if the solution state is a long way down one of the branches. 115 Figure 11.2 Bottom-up search. If we expect there to be numerous solution states a long way down the branches, it is more e fficient to conduct a depth first search. A depth first search involves searching all the way down the length of a branch until we either find a solution state or hit a terminal state. If we reach a terminal node, we backtrack only until we can descend an unsearched branch. Figure 11.4 shows the order in which we would search the same tree from Figure 11.3 if we were conducting a depth first, left first search. While depth first search can be notably more e fficient in situations where there are numerous solution states deep down the branches of 116 Download 1.05 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling