Heuristic: Fundamentals and Applications

By Fouad Sabry

What Is Heuristic

In the fields of mathematical optimization and computer science, a heuristic is a strategy that is designed to solve a problem more rapidly in situations where traditional approaches are either too slow for finding an approximation answer or fail to find any accurate solution. In order to accomplish this, we must sacrifice optimality, completeness, accuracy, or precision in exchange for speed. It is possible to look at it as a short cut in some respects.

How You Will Benefit

(I) Insights, and validations about the following topics:

Chapter 1: Heuristics in Computer Science

Chapter 2: Greedy Algorithm

Chapter 3: Divide and Conquer Algorithm

Chapter 4: Dynamic Programming

Chapter 5: Branch and Bound

Chapter 6: Backtracking

Chapter 7: A* Search Algorithm

Chapter 8: Simulated Annealing

Chapter 9: Genetic Algorithm

Chapter 10: Swarm Intelligence

(II) Answering the public top questions about heuristic.

(III) Real world examples for the usage of heuristic in many fields.

(IV) 17 appendices to explain, briefly, 266 emerging technologies in each industry to have 360-degree full understanding of heuristic' technologies.

Who This Book Is For

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of heuristic.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jun 28, 2023

Book preview

Chapter 1: Heuristic (computer science)

In the fields of computer science and mathematical optimization, heuristic (from Greek εὑρίσκω I find, discover) is a strategy that was developed to help solve problems more rapidly in situations when traditional approaches are insufficient for finding an approximative solution, or when traditional procedures are unable to locate any specific remedy.

This is accomplished via the use of optimality trading, completeness, accuracy, or accuracy in exchange for velocity.

To some extent, It is possible to see it as a short cut.

A heuristic function, which is usually referred to as simply a heuristic, is a function that rates the many possibilities in search algorithms at each branching stage depending on the information that is available in order to choose which branch to follow. For instance, it might be a close approximation of the precise answer.

The purpose of a heuristic is to generate a solution in a fair amount of time that is adequate for resolving the issue that is currently being considered. This solution may not be the best out of all the possible answers to this issue; instead, it could only be a close approximation of the correct answer. However, despite this, it is still important since locating it will not take an insurmountable amount of time.

Heuristics have the potential to create outcomes on their own, or they may be used with optimization algorithms in order to boost such algorithms' overall effectiveness (e.g., they may be used to generate good seed values).

Heuristics are the only viable option for a variety of complex optimization problems that need to be routinely solved in real-world applications as a result of results about NP-hardness in theoretical computer science. This is because NP-hardness makes it extremely difficult to find optimal solutions.

Since heuristics may be used even in circumstances in which there are no known algorithms, they are an essential part of both the area of artificial intelligence and the process of simulating human thought on a computer.

The following is a list of the trade-off factors that may be used to decide whether or not to employ a heuristic for the solution of a certain problem::

Optimality: Does the heuristic ensure that the optimal solution will be discovered in situations when there are several possible solutions to a given problem? Is it really vital to locate the most effective solution?

Completeness refers to whether or not the heuristic can identify all of the possible solutions to a problem when there are more than one. Do we really need each and every solution? A great number of heuristics are designed to only locate one answer.

Regarding the accuracy and precision of the putative answer, can the heuristic offer a confidence interval for it? Is there an unacceptable amount of room for error on the solution?

Execution time: is this the most effective heuristic that is currently known for resolving problems of this kind? Some heuristics get closer to the correct answer more quickly than others. Some heuristics are just somewhat faster than traditional approaches, and in this instance, the 'overhead' on computing the heuristic could have a detrimental influence.

Because the theory that underpins heuristics is not very detailed, there are some scenarios in which it may be difficult to determine whether or not the answer that was identified by the heuristic is satisfactory.

One method for accomplishing the increase in computing efficiency that is anticipated from the use of a heuristic is to resolve an issue that is easier and whose solution is also a solution to the first problem.

Jon Bentley provides a description of an example of an approximation that may be used to solve the traveling salesman issue (TSP):

Given a list of cities and the distances between each pair of cities, what is the shortest feasible route that visits each city precisely once and then returns to the city from which it originated?

to allow for the selection of the drawing sequence using a pen plotter. Because TSP is known to be an NP-hard issue, finding an optimum solution to even a problem with a reasonable amount of data might be challenging. Instead, the greedy algorithm may be used to produce a decent solution, but not the optimum solution (it is an approximation to the ideal answer) in a reasonable period of time. This can be accomplished by increasing the quantity of resources that are taken into consideration by the algorithm. The greedy algorithm heuristic recommends selecting whatever the best feasible next step is at the time, regardless of whether or not doing so would prevent (or even make it impossible to take) excellent steps in the future. It is a heuristic in the sense that experience suggests that it is an adequate answer, while theory suggests that there are superior options (and even indicates how much better, in some cases).

Another scenario in which heuristics make an algorithm run more quickly is when applied to certain search tasks. At first, the heuristic operates similarly to the full-space search method in that it considers every alternative at each stage. However, it has the ability to halt the search at any point if it determines that the current option is already inferior than the best answer that has been identified. A heuristic may be used in these kinds of search issues to ensure that favorable options are tried first, allowing for the early elimination of undesirable alternatives (see alpha-beta pruning). In the case of algorithms that do best-first searches, such as A* search, the heuristic increases the algorithm's convergence while preserving its correctness, provided that the heuristic is acceptable. This is true so long as the method continues to be implemented correctly.

In the speech that Allen Newell and Herbert A. Simon gave in acceptance of the Turing Award, they discussed the heuristic search hypothesis. According to this hypothesis, a physical symbol system will repeatedly generate and modify known symbol structures until the created structure matches the solution structure. Because each subsequent step is dependent upon the one that came before it, the heuristic search is able to choose which potential paths to explore and which ones to ignore by gauging how near the currently performing step is to the actual answer. Since of this, certain alternatives will never be created because it is determined that they have a lower chance of successfully completing the task.

Using search trees allows a heuristic technique to successfully complete its assigned work. A heuristic, on the other hand, chooses branches that are more likely to yield outcomes than other branches in the tree, rather than creating all of the potential solution branches. At each fork in the road, it makes judicious choices, opting for avenues that are more likely to lead to successful outcomes.

When searching for viruses and other types of malicious software, antivirus software will often make use of heuristic rules. Heuristic scanning examines a virus in search of coding and/or behavioral patterns that are shared by a class or family of viruses. There are distinct sets of guidelines for each kind of virus. The scanner will infer that a file is infected if it discovers that a file or running process has code patterns that match those being searched for, or if it discovers that the file or process is doing the same set of behaviors. The most innovative aspect of behavior-based heuristic scanning is that it is able to combat highly randomized self-modifying and mutating (polymorphic) viruses, which are notoriously difficult to identify using conventional string scanning techniques due to their complex nature. Heuristic scanning has the potential to detect future viruses without the need for the virus to first be found somewhere else, then sent to the developer of the virus scanner, analyzed, and a detection update for the scanner provided to the users of the scanner. This is because heuristic scanning is based on patterns that have been observed in the past.

Some heuristics are supported by a robust theory; they are either developed in a top-down fashion from the theory, or they are arrived at based on either experimental data or data taken from the actual world. The others are just rules of thumb derived from direct observation or experience in the actual world, with no theoretical underpinnings whatsoever. These latter are vulnerable to a greater variety of potential problems.

It is possible that the current data set does not necessarily represent future data sets (see: overfitting), and that purported solutions turn out to be akin to noise when a heuristic is reused in various contexts because it has been seen to work in one context, without having been mathematically proven to meet a given set of requirements. This occurs when a heuristic is reused because it has been seen to work in one context.

When heuristics are used to assess the likelihood of wrong outcomes, statistical analysis may be carried out.

To make use of a heuristic in order to solve an issue involving searching or knapsacking, It is essential to confirm if the heuristic in question is acceptable.

Given a heuristic function h(v_{i},v_{g}) meant to approximate the true optimal distance d^{\star }(v_{i},v_{g}) to the goal node v_{g} in a directed graph G containing n total nodes or vertices labeled v_{0},v_{1},\cdots ,v_{n} , admissible means roughly that the heuristic underestimates the cost to the goal or formally that h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g}) for all (v_{i},v_{g}) where {i,g}\in [0,1,...,n] .

In the event that a heuristic does not pass muster, It's possible that it'll never get there, either by ending up in a dead end of graph G or by skipping back and forth between two nodes v_{i} and v_{j} where {i,j}\neq g .

Search for heuristic in the unabridged version of Wiktionary, the online dictionary.

At the beginning of the 19th century, people started using the term heuristic. It derives in an unorthodox manner from the Greek word heuriskein, which may be translated as to discover..

{End Chapter 2}

{End Chapter 1}

Chapter 2: Greedy algorithm

Any algorithm that adheres to the problem-solving heuristic of selecting the option that is locally optimum at each step may be referred to as a greedy algorithm. However, a greedy heuristic may create locally optimum solutions that approach a globally optimal solution in an acceptable period of time. This is possible even when a greedy method does not offer an ideal solution, which is the case with many issues.

For instance, the following heuristic might be considered a greedy approach for solving the traveling salesman issue, which involves a high level of computing complexity: At each leg of the trip, visit the next unvisited city. This heuristic isn't