The book “Theoretical minimum on Computer Science. All that a programmer and developer needs ”/ The company’s blog Publishing House“ Peter ”

Stop wasting time on boring academic tomes! Learning Computer Science can be fun and challenging.

Vladston Ferreira Filo introduces us to computational thinking, which allows us to solve any complex problems. Learning how to write code is simple - a couple of weeks in the courses, and you are a “programmer", but to become a pro who will be in demand anytime and anywhere, you need fundamental knowledge. Here you will find only the most important information that every developer and programmer needs every day.

3.5. Heuristic Algorithms

In ordinary chess, there are 32 pieces of six types and 64 cells on which they move. After some four first moves, the number of possible further positions reaches 288 billion. Even the strongest players in the world are not able to find the perfect move. They rely on intuition to find one that turns out to be good enough. We can do the same with algorithms. A heuristic method, or simply heuristic, is a method that leads to a solution without guaranteeing that it is the best or optimal. Heuristic algorithms will help when methods like exhaustive search or return search are too slow. There are many great heuristic approaches, but we will focus on the simplest: search without return.

Greedy algorithms

A very common heuristic approach to solving problems is the use of so-called "greedy" algorithms. Their main idea is to never roll back to previous options. This is the exact opposite of return search. In other words, at every step we try to make the best choice, and then we do not question it. Let's try this strategy in order to solve the backpack problem in a new way (from the section "Full Bust").

Greedy robber and a backpack. A burglar sneaks into your house to steal items that you wanted to sell. He decides to use your backpack to carry stolen items from him. What will he take? Keep in mind that the faster he leaves, the less likely he will be caught red-handed.

In essence, the optimal solution here should be exactly the same as in the backpack problem. However, the burglar does not have time to sort through all the combinations of backpack packing, he has no time to constantly roll back and take out things already packed in the backpack! The greedy will stick the most expensive items into the backpack until it fills it:

function greedy_knapsack(items, max_weight)
      bag_weight ← 0
      bag_items ← List.new
      for each item in sort_by_value(items)
           if max_weight ≤ bag_weight + item.weight
                 bag_weight ← bag_weight + item.weight
                 bag_items.append(item)
      return bag_items

Here we do not take into account how our current action will affect future choices. Such a “greedy” approach allows you to find a selection of items much faster than the exhaustive search method. However, he does not give any guarantee that the total cost of the selection will be maximum.

In computational thinking, greed is not only a mortal sin. As a respectable trader, you may also feel like pushing the largest amount in your backpack or heading out on a trip.

Salesman again. The salesman must visit n given cities and end the route at the point where he started it. What travel plan will minimize the total distance traveled?

As we saw in the Combinatorics section (see Chapter 1), the number of possible combinations in this task demonstrates explosive growth and reaches indecently large values, even if there are only a few cities. Finding the best solution to the traveling salesman problem with thousands of cities is extremely expensive (or even impossible).

Nevertheless, you need a route. Here is a simple “greedy” algorithm for this task:

1) visit the nearest city where you have not been;
2) repeat until you go around all the cities.


Can you come up with a better heuristic algorithm than the one that uses the greedy approach? Specialists in computer science are racking their brains over this issue.

When greed conquers power

Choosing a heuristic algorithm instead of the classical one, you compromise. How far can you go from the perfect solution so that the result still satisfies you? It depends on the specific situation.

However, even if you certainly need to find the perfect option, you should not discount heuristics. A heuristic approach sometimes leads to the best solution. For example, you can develop a “greedy” algorithm that can find the same solution as a full search algorithm. Let's see how this is done.

Electrical network. The villages in the remote area were not electrified, but in one of them they began to build power plants. Energy will go from town to town via power lines. How to connect all villages to the network using a minimum of wires?
This problem can be solved very simply.

1. Among the villages that are not yet connected to the network, select the one that is closest to the electrified village and connect them.
2. Repeat until all villages are connected.


At each step, we select a couple of villages for the connection, which currently looks the best. Despite the fact that we do not analyze how this option affects future choices, joining the nearest village without electricity is always the right choice. Here we are lucky: the structure of the problem is ideally suited for solving by the "greedy" algorithm. In the next section, we will see the structure of tasks for the solution of which we need the strategy of the great commanders.

»More information about the book can be found on the publisher’s website
» Table of Contents
» Excerpt

For Savingsbenders 20% off coupon - Computer Science