Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
Exercise 11.2
If we were to simply apply a breadth first, left first search to the tree depicted in Figure 11.5 (without applying a heuristic function), how many nodes would we have to traverse before reaching the same solution state? What if we used a depth first, left first search? What if we used depth first, right first? As Exercise 11.2 demonstrates, this heuristic search is notably more e fficient – in terms of the number of nodes searched – than either of our blind search procedures. It is also the case, though, that it is more computationally expensive per node since as well as determining 118 whether each searched node represents a solution state, we are also applying a heuristic function. For any generation tree of even moderate complexity though, the computational cost per node of applying the heuristic function will be far outweighed by the overall computational savings conferred by the heuristic guide, since we typically massively decrease the number of nodes we need to examine. Unfortunately, however, heuristics are just that – heuristics. They are not decision procedures. In other words, while heuristic values provide us with some sort of indication of the closeness to solution of a given node, the assigned value may not be a good representation of the actual closeness to solution of the node. Better heuristics provide more accurate indications, but it is always the case that heuristic values can lead us astray. One way in which hill climbing search can lead us astray is if a par- ticular search path involves initially moving away from a solution state (according to the criteria measured by our heuristic) but then swings back and leads to a solution more quickly than other search paths. To make this clear, consider the following spatial analogy. Suppose I am in the rainforest at an elevation of roughly 100 metres and I want to get down to the beach which I know to be roughly to my east. There are two paths I can see, one of which seems to head north-east and the other of which leads south-east. I can’t see much of either path through the trees but what I can see is that the north-east path seems to lead gently 119 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