Informed search

Informed search or heuristic search We have a heuristic function that we add to our cost so far to choose our next step. Best-first search is the idea of using an evaluation function f(n) for each node which estimates a "promisingness" of each node. We then expand the most promising of unexpanded nodes. We implement this idea by ordering the nodes in fringe in decreasing order of promisingness. We use a priority queue as our data structure, not a sorted array. Special cases of best-first search are greedy best-first search and A-star search. In greedy-best first search, the f of n is the same as the heuristic h of n. This means we expand the node that appears to be the closest to the goal. It is complete if we forbid duplicates and have a finite space. However, it does not guarantee that we will get the optimal result. Its complexity is b to the power of m for both time and space. A star improves upon this idea by avoiding expanding paths that are already expensive. We add a g of n which is the cost so far to reach our current node. We add this to the heuristic to get f of n. This means that our f of n knows about how far we've come so far.