Specific Heuristic Examples

Question

What are some specific examples (e.g. alpha-beta cropping, for example: tic-tac-toe and how it applies there) heuristics. I have already seen the answer to the question of what heuristic is, but I still do not understand where it uses the estimate. Can you give me a concrete example of heuristics and how does it work?

Answer 1

Most indicative is the use of heuristics in informed search algorithms such as A-Star . For realistic problems, you usually have a large search space, making it impossible to check every part of it. To avoid this, that is, first try the most promising parts of the search space, you use heuristics. Heuristics give you an assessment of how good the next steps of the search are available. Choose the most promising next step, i.e. best-first . For example, if you want to find the path between two cities (that is, the peaks associated with a set of roads, that is, the edges that make up the graph), you can choose the straight distance to the target as a heuristic to determine which city to visit first (and see if whether he is the target city).

Heuristics should have similar properties to indicators for the search space, and they usually should be optimistic, but that's another story. The problem of providing heuristics that works efficiently and which is a side effect is another problem ...

To apply the various heuristics used to find a path through a given maze, also see this answer .

Answer 2

Warnsdorff's rule is heuristic, but the A* search algorithm is not. This, as the name suggests, is a search algorithm that is independent of the problem. Heuristic is. Example: you can use A* (if it is correctly implemented) to solve puzzle 15 and find the shortest way out of the maze, but the heuristics used will be different. With the Fifteen puzzle, your heuristic can consist of how many tiles are inappropriate: the number of moves needed to solve the puzzle will always be greater than or equal to the heuristic.

To exit the maze, you can use the Manhattan distance to the level that, as you know, is outside the maze as a heuristic. Manhattan Distance is widely used in gaming problems, as this is the number of “steps” in horizontal and vertical directions necessary to achieve the goal.

 Manhattan distance = abs(x2-x1) + abs(y2-y1) 

It is easy to see that in the best case (no walls) this will be the exact distance to the target, otherwise you will need more. This is important: your heuristic should be optimistic ( valid heuristic ) so that your search algorithm is optimal. It must also be consistent . However, in some applications (for example, in games with very large cards) you use invalid heuristics, because a rather suboptimal solution is enough.

Heuristics are simply an approximation to real value (always lower than real value, if acceptable). The better the approximation, the less state the search algorithm will have to explore. But better approximations usually mean more computational time, so you need to find a compromise solution.

Answer 3

Your question interests me, since I heard about heuristics too while studying, but I never saw an application for this, I searched a bit and found this: http://www.predictia.es/blog/aco-search

This code mimics the ant optimization algorithm to optimize colonies for searching through a website. "Ants" are employees who will search through the site, some will search randomly, some others will follow the "best path" defined by the previous ones.

Answer 4

A concrete example: I am making a solver for the JT Block game, which is roughly equivalent to the Same game . The algorithm performs a width search for all possible hits, saves the values ​​and performs them until the next layer. The problem is that the number of possible hits quickly gets out of hand (1030 estimated positions per game), so I need to crop the list of positions at each step and take only the "best" of them.

Now the definition of “best” positions is rather vague: these are positions that are expected to lead to better final points, but nothing is certain. And here comes the heuristic. I tried several of them:

• sort positions by the number of points received so far
• increase the score for the best result obtained using the depth search
• increase the score based on a complex formula, using the number of tiles, their color and proximity.
• improves the latest heuristic by adjusting its parameters and seeing how they perform
• etc...

The last of these heuristics can lead to optimization of ant -march: there are half a dozen parameters that can be adjusted from 0 to 1, and the optimizer can find the optimal combination of them. At the moment, I just improved some of them a little.

The second of these heuristics is interesting: it can lead to an optimal score through a full depth search, but such a goal is impossible, of course, because it will take too much time. In general, increasing X leads to better heuristics, but significantly increases the computation time.

So, here are some examples of heuristics. Everything can be heuristic as long as it helps your algorithm work better, and this is what makes them so hard to understand: they are not deterministic. Another point with heuristics: they should lead to fast and dirty results of real material, so there is trade between their lead time and accuracy.

Answer 5

Some concrete examples: to solve the Knight Tour problem, you can use the Warnsdorff rule - heuristic. Or to solve Fifteen puzzles , a possible heuristic is the A * search algorithm .

Answer 6

An original question asked specific examples of heuristics.

Some of these specific examples have already been given. Another would be the number of non-local plates in the 15 puzzle or its improvement, the Manhattan distance based on non-local plates.

One of the previous answers also claimed that heuristics are always problem-dependent, while algorithms are not task-dependent. Although, of course, there are also problem-dependent algorithms (for example, for each problem you can simply give an algorithm that immediately solves this problem, for example, the optimal strategy for any tower-hanoi problem is known) is a problem-independent heuristic!

Consequently, there are also various types of problem-independent heuristics. Thus, to a certain extent, each such heuristic can be considered as a concrete heuristic example, without being adapted to a specific problem, such as a 15-puzzle. (Examples of problem-independent heuristics taken from planning are the FF heuristic or the Add heuristic.)

These problem-independent heuristics are based on a common description language, and then they solve the problem. That is, the problem of relaxation is based only on the syntax (and, of course, on its underlying semantics) of the description of the problem without “knowing” what it represents. If this interests you, you should familiarize yourself with "planning" and, more specifically, "plan as a heuristic search." I also want to mention that these heuristics, being independent of problems, depend, of course, on the language describing the problem. (For example, my previous heuristics are specific to "planning tasks" and even for planning, there are different classes of subprocesses with different types of heuristics.)