The usage of a "
hill climbing" algorithm is a quick and easy way to enhance blind searching algorithms. With hill climbing, a search
algorithm can become smarter and more efficient, which more than makes up for the check that must be performed on every step of the way through the search.
Here's the reason this idea is called hill climbing. Imagine you are on a foggy mountain range and you want to climb to the top of the tallest mountain. Since it's so foggy, you can't see where you're going, and can't find the best path to the top of that mountain by inspection. Being a good Boy Scout, however, you've got your trusty map and compass. You know where you are, and you see that the mountain is directly north of you. There are paths that lead east, west, and north from where you are. Following the tenets of common sense, you head north. But what if the north path leads to a dead end, or one of the other passages ends up being quicker? Most likely, the path that gets you closer to the goal will be the ideal one to take. However, this is not always the case, and you must remember where you've been, just in case you can't reach the top by going that way.
A computer program using a hill climbing search algorithm would analyze the situation in a similar manner. Hill climbing searches begin like regular depth-first searches, but they have an added heuristic that assigns a "goodness" to each of the new possibilities. The algorithm continues like a depth-first search would, but it goes down the "path" that was ranked best, keeping the others as a backup in case that possibility does not work (e.g. the "dead end" situation described above.) Hill climbing search algorithms are not guaranteed to produce the most efficient results, because of the uncertainty of the "goodness" ranking. They are, however, much more efficient than blind depth-first searches.