Dynamic programming explained by shopping list optimization case.

Long story short: I decided to automatically sort my shopping list in such a way, that It helps me to follow the shortest path through the store by collecting groceries consequently as they appear in the list.

Surprisingly enough the project helped me truly understand the principle of dynamic programming. In this article, I want to tell you about my experience, I hope It will help someone to understand it better as well.

So, here’s the idea: first, let’s group all the groceries in the list according to their type (meat, milk, drinks, e.t.c.), then keeping in mind the departments to visit It’s possible to calculate the optimal path through the store, and sort the list accordingly.

I use a Telegram bot as an interface. In this article, I’ll describe the backend part of it.

Calculating the optimal route

Let’s create an adjacency matrix M representing distances between the sections of the store. So that M(i,j) tells the distance from department i to j. If there are no items in the list, that correspond to a certain section, it’s dropped from the matrix, so the matrix contains only departments I’m doing to visit.

The adjacency matrix. Squares on the main diagonal asr completely black, which means that distances from departments to themselves are zeros.

The first approach to calculate the route that comes to mind is the so-called “Greedy algorithm”, i.e. always going to the closest point. Unfortunately, greedy algorithms often do not return the optimal route. For example, the following picture illustrates the case, when such an algorithm fails.

To visit all the points starting from A, one needs to visit point B first, which isn’t closest.

So, dynamic programming is the answer. Dynamic programming allows solving some tasks easier than by brute force, by breaking the initial task into smaller tasks. Solutions of the smaller tasks are stored in a memory and used to construct solutions to more and more complicated tasks until one gets the solution to the initial task.

In this case, the smaller task is to find the shortest route through a given subset of points ending in a certain point. The easiest way to store intermediate results is to write them into a matrix A(i,j) and make “i” mean the endpoint of the intermediate route, while “j” will somehow encode the subset of points which the given route passes.

Here is the way I use no encode the subset of points: let’s create a bitmask the size equal to a total number of points. Now, 1 in the bitmask means the corresponding point is in the subset, and 0 means it’s not. For example, 01011 describes a subset of 2nd, 4th and 5th points of a set consisting of 5 points. This binary number can be converted to decimal and used as a matrix index.

Let me Clarify the idea with the following example. Say A(5,1105) = 10. 1105 is 10001010001 in binary, which means that the route visits points 1, 5, 7, and 11, corresponding to ones in the bitmask. 5, the number of the row, means that the route finishes in the point №5. To sum up, the length of the route through points 1,5,7, and 11 finishing in the point №5 is 10.

Here’s the algorithm. First, the columns containing only a single one in binary are filled — these are the routes through only one point. Then the columns containing two ones, three ones, and so on. The columns are filled in the order of increasing the number of ones in their bitmask because the values in later columns are based on the values in columns that were previously filled.

For example, let’s assume that all the columns containing 1 and 2 ones in their bitmasks are already filled, which allows us to calculate the value of the 1st row of the 15th column because 15 in binary is 1101, contains 3 ones. 1101 implies the route through points 1, 2, and 4, the row 5 implies that said route finishes at the point №5.

This route is the minimum of two values M(1,2) + A(2, 5) and M(1,4) + A(4, 5). We consider the 5th column because its bitmask is 0101, which corresponds to the route through all the points we need except the last one. Like this, all the cells are filled in. The cells corresponding to impossible states are filled with infinite values.

The solution matrix. Half of the cells represent impossible states.

Ultimately, we are interested in the last column, because it corresponds to the route through all the points. Now we just need to find the smallest value in the last row and construct the route using values in the matrix.

And one last thing, it would be reasonable to always finish at the “frozen products” section of it’s present in our shopping list, so the products you take will not melt.

The route containing the section of frozen products

The route through the same sections except for the frozen products is completely different

Interesting how the route changes completely depending on whether or not it contains the “frozen products” section.

Grouping the groceries

As an example I’ll use the following list:

- Cheese
- Bananas
- Hazelnuts
- Stakes
- Bread
- Tuna
- Eggs
- Beer
- Cereal
- Apples
- Pepper
- Ketchup
- Soda
- Icecream

Let’s begin by mapping the departments. I went to the closest grocery store and made the table such as:

A fragment of the table describing the store

The first column contains the name of the department, the second and the third ones — its’ coordinates, they will be used to create an adjacency matrix.

The fourth column contains anchors. Anchors are examples of what can be bought in the corresponding department. At first, I wanted to include in the “anchors” column everything I buy at the corresponding departments. That would make matching groceries to the departments a lot easier, it would be enough to just look for a certain anchor, that matches the item in the list. Unfortunately, the said approach has several disadvantages. Firstly, every time a new item emerges in the list it will be necessary to add it to the anchors. Secondly, every item could be mentioned in several different ways like eggplant could be mentioned as aubergine. Instead of filling all the possibilities into the “anchor” column, I decided to use word embeddings.

Word embeddings are a very useful instrument, it allows working with vectors instead of strings. Vectors represent the meaning of the word, for example, to see how close meanings of two words are to each other, one can simply calculate the distance between the vectors representing them. The distance between “Beer” and “Beverages” vectors is much smaller than the distance between “Beer” and “Bakery” vectors, which means that beer is much more likely to be found in the “Beverages” section.

I used the Russian Navec embeddings because I compose my shopping list in Russian, but there are a lot of embeddings available in English as well.

Now the algorithm looks like this: for each entry in the list we need to measure the distance to every anchor in the fourth column. The item belongs to the category, that has the closest anchor to it. The said approach resolves the problem with items, that never occurred before and a problem with different names for the same product because word embeddings for “eggplant” and “aubergine” are almost identical.

So, now the list looks like this:

{
'bakery': ['Bread'],
'breakfast': ['Cereal'],
'milk/cheese/eggs': ['Cheese', 'Eggs'],
'meat': ['Stakes'],
'Beverages': ['Beer', 'Soda'],
'Fruits':['Apples','Bananas'],
'Nuts':['Hazelnuts'],
'Canned food':['Tuna'],
'Spices':['Pepper', 'Ketchup'],
'Frozen products':['Icecream'],
}

I’d like to point out that hazelnuts ended up in the “nuts” group even though hazelnuts are not in anchors for that category.

We’re almost there, now what’s left is to sort the groups according to th optimal route.

- Apples
- Bananas
- Tuna
- Pepper 
- Ketchup
- Cereal
- Hazelnuts
- Cheese 
- Eggs
- Stakes
- Bread
- Beer 
- Soda
- Icecream

So, that’s the result. For those, who are interested here’s a link to GitHub.