Heuristic Search

Heuristic Search
The Traveling Salesman Problem (TSP), where a salesman makes a complete tour of the cities on his route, visiting each city exactly once, while traveling the shortest possible distance, is an example of a problem which has a combinatorial explosion. As such, it cannot be solved using breadth-first or depth-first search for problems of any realistic size. Unfortunately, there are many problems which have this form and which are essentially intractable (they can’t be solved). In these cases, finding the best possible answer is not computationally feasible, and so we have to settle for a good answer. In this section we discuss several heuristic search methods which attempt to provide a practical means for approaching these kinds of search problems.
What is the Heuristic Search ?
Heuristic search methods are characterized by this sense that we have limited time and space in which to find an answer to complex problems and so we are willing to accept a good solution. As such, we apply heuristics or rules of thumb as we are searching the tree to try to determine the likelihood (احتمال) that following one path or another is more likely to lead to a solution. Note this is in stark contrast to brute-force methods which chug along merrily regardless of whether a solution is anywhere in sight.
Heuristic search methods use objective functions called heuristic functions to try to gauge the value of a particular node in the search tree and to estimate the value of following down any of the paths from the node.
Generate and Test Algorithm
The generate and test algorithm is the most basic heuristic search function. The steps are:
1. Generate a possible solution, either a new state or a path through the problem space.
2. Test to see if the new state or path is a solution by comparing it to a set of goal states.
3. If a solution has been found, return success; else return to step 1.

Example:-

Figure (1): Example of Generate and Test Algorithm
Question for Students: what is the different between this algorithm and depth first search algorithm?

Disadvantage of this algorithm
• It may take an extremely long time. For small problems, generate and test can be an effective algorithm, but for large problems, the undirected search strategy leads to lengthy run times and is impractical.
• The major weakness of generate and test is that we get no feedback on which direction to search. We can greatly improve this algorithm by providing feedback through the use of heuristic functions.
Hill climbing Algorithm
It is an improved generate-and-test algorithm, where feedback from the tests are used to help direct the generation (and evaluation) of new candidate states. When a node state is evaluated by the goal test function, a measure or estimate of the distance to the goal state is also computed.