Heuristic search

In one sentence Heuristic search uses a useful estimate to explore promising possibilities before less promising ones. A simple real-life or nature example If you lose your keys, you probably check the coat you wore today before emptying every cupboard. That guess can save time, but it is not proof the keys are there. A heuristic does the same for search: it changes what you check first, while the search still needs to verify the answer. Why Early problem-solving programs faced an explosion of possible moves. Search methods made progress by using clues about a goal instead of treating every branch as equally promising. How Keep a list of possibilities. Score them using an estimate of promise, investigate a high-scoring option and add its successors. Stop according to the method's goal and resource rules. Example and benefit In a sliding-tile puzzle, the total grid distance of tiles from their target positions can guide exploration. Whether the estimate guarantees a shortest solution depends on the search algorithm. Where this leads Heuristics connect symbolic search to modern learned value estimates. A* makes a particular cost trade-off precise; game search adapts search to an opponent. Limitations A misleading estimate can focus effort on the wrong branch. A useful shortcut may sacrifice an optimality guarantee, so the trade-off must be explicit.