Introduction to Artificial Intelligence - Old Questions
4. What is heuristic information? Suppose that we run a greedy search algorithm with h(n) = – g(n) and h(n) = g(n). What sort of search will the greedy search follow in each case?
Answer
AI is thinking...
The information which is used to search the space more efficiently is called heuristic information.
Ways of using heuristic information:
• Deciding which node to expand next, instead of doing the expansion in a strictly breadth-first or depth-first order;
• In the course of expanding a node, deciding which successor or successors to generate, instead of blindly generating all possible successors at one time;
• Deciding that certain nodes should be discarded, or pruned, from the search space.
The function g(n) gives the cost of the path from initial state to the node n. Using h(n) = -g(n) for the heuristic function in a greedy search, then, will cause the algorithm to always select the node with the highest path cost so far (the largest g(n)) to expand next, since this will give us the smallest h(n) (i.e. the most negative value). If all operations have the same cost value associated with them, then the largest g(n) will always correspond to the longest path in the search tree and the greedy search will emulate depth-first search.
If we set h(n) = g(n) we get breadth first search.