The book "Theoretical minimum in Computer Science. All the programmer and developer need is "

Stop wasting time on boring academic folios! Studying Computer Science can be fun and exciting.

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 always and everywhere, 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 figures of six types and 64 cells in which they walk. 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 a heuristic, is a method that leads to a solution, without guaranteeing that it is the best or the best. Heuristic algorithms will help when methods like brute force or search with return are too slow. There are many excellent heuristic approaches, but we will focus on the simplest one: on searching without a 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 the previous options. This is the exact opposite of search return. In other words, at every step we try to make the best choice, and then we don’t question it. Let's try this strategy in order to solve the backpack problem in a new way (from the “Brute force” section).

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

In fact, the optimal solution here should be exactly the same as in the backpack problem. However, the robber does not have time to go through all the combinations of a pack of a backpack, he has no time to constantly roll back and take out items already packed in a backpack! A greedy person will stick the most expensive items into his backpack until he 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 objects much faster than the method of complete enumeration. However, it does not give any guarantee that the total cost of the collection will be the maximum.

In computational thinking, greed is not only a mortal sin. As a respectable merchant, you may also feel like cramming a little more into your backpack or heading off on a trip.

A traveling salesman again. The traveling salesman must visit n specified cities and complete the route at the point from where he started it. What travel plan will minimize the total distance covered?

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

And yet you need a route. Here is a simple "greedy" algorithm for this problem:

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


Can you think of a better heuristic algorithm than the one that uses the “greedy” approach? Computer scientists are puzzled over this issue.

When greed conquers power

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

However, even if you absolutely need to find the perfect option, you should not discard heuristics from the accounts. The heuristic approach sometimes leads to the best solution. For example, you can develop a “greedy” algorithm that can find the same solution as a brute force algorithm. Let's see how this is done.

Electrical network. Villages in a remote area were not electrified, but in one of them began to build power plants. Energy will go from the village to the village along the power lines. How to include all the villages in the network using a minimum of wires?
This task can be solved very simply.

1. From 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 the villages are connected.


At each step, we choose to connect a couple of villages, 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 ideal for solving the "greedy" algorithm. In the next section, we will see the structure of the tasks, the solution of which requires the strategy of great commanders.

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

For Habrozhiteley 20% discount coupon - Computer Science