What is a heuristic?

Question

Is it the same as artificial intelligence? What is the relationship between these things? Why does it matter to us programmers? Can you give an example to illustrate?

Answer 1

A heuristic is a technique that improves demand efficiency. The word originates from the Greek "Heuriskein" which means to discover, also originated from Eureka which comes from the expression "heurika" which became famous for Archimedes.

Heuristics will then be an adequate estimate of the cost or longitude of the pitch (in the search space) from a state to an objective. They say you underestimate the distance if your estimation to the goal is less than or equal to real distance.

Given the complexity of Heuristics, then, let’s talk about its relationship with Artificial Intelligence, used as a search technique for achieving goals in non-algorithmic problems that generate combinatorial "explosions".

One of the most famous examples is the following blocks:

Source:

http://www.ic.unicamp.br/~ffaria/ia1s2015/class04/class04a-Buscacominformacao_estrategias.pdf

http://cee.uma.pt/edu/iia/acetatos/iia-Procura%20Informada.pdf

Answer 2

There are problems in computation that are currently impossible to obtain an optimal solution in polynomial time, that is, we will not be alive when the processing is finished and this is due to the very high number of possibilities that are necessary to be analyzed that grow exponentially with the number of variables. These problems are known as NP-Complete. An example of this type of problem is the famous Traveler Salesman, where given several points in an area and several paths connecting these points, It is necessary to search for the smallest circuit going through all the points without repeating any path and returning to the point of origin obtaining the shortest distance possible. This problem solving is useful for example to optimize business delivery fleets.

To circumvent this problem, instead of analyzing all possible situations, are used Heuristics who may not be the best solution, but rather approach it. In the example of Traveling Salesman, instead of checking all possible paths, we can adopt the approach of a point x always choose the shortest distance to another point y until we return to the starting point. In this approach it is not guaranteed that the distance obtained at the end is the shortest possible distance, in view of the choice of a smaller path can force you to choose a very large path in the future. However, when the problem is approached in this way, the time to obtain the solution becomes polynomial.