Generate and Test Heuristic Search – Artificial Intelligence
The generate-and-test strategy is the simplest of all the approaches. It consists of the following steps:
Algorithm: Generate-and-Test
1. Generate a possible solution. For some problems. this means generating a particular point in the problem space. For others, it means generating a path from a start state.
2. Test to see if this is actually a solution by comparing the chosen point or the endpoint of the chosen path to the set of acceptable goal states.
3. If a solution has been found, quit. Otherwise, return to step 1.
The following diagram shows the Generate and Test Heuristic Search Algorithm
Generate-and-test, like depth-first search, requires that complete solutions be generated for testing.
In its most systematic form, it is only an exhaustive search of the problem space.
Solutions can also be generated randomly but the solution is not guaranteed.
This approach is what is known as the British Museum algorithm: finding an object in the British Museum by wandering randomly.
Example: coloured blocks
“Arrange four 6-sided cubes in a row, with each side of each cube painted one of four colors, such that on all four
sides of the row one block face of each color are showing.”
Heuristic: If there are more red faces than other colours then, when placing a block with several red faces, use few
of them as possible as outside faces.
Example – Traveling Salesman Problem (TSP)
A salesman has a list of cities, each of which he must visit exactly once. There are direct roads between each pair of cities on the list. Find the route the salesman should follow for the shortest possible round trip that both starts and finishes at any one of the cities.
- Traveler needs to visit n cities.
- Know the distance between each pair of cities.
- Want to know the shortest route that visits all the cities once.
Search flow with Generate and Test
| Search for | Path | Length of Path |
| 1 | ABCD | 19 |
| 2 | ABDC | 18 |
| 3 | ACBD | 12 |
| 4 | ACDB | 13 |
| 5 | ADBC | 16 |
| Continued |
Finally, select the path whose length is less.
Summary
This article discusses Generate and Test Heuristic Search – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.