This article originated from personal public account: TechFlow, original is not easy, for attention
Today is the 31st article on algorithms and data structures, we will talk about binary graph matching and Hungarian algorithm.
In our last article, we introduced an interesting stable marriage problem, simulating a male-female pairing and studying the Gale-Shapley algorithm to make the match more stable. Those of you who missed this article can review the details of marital stability via the portal below.
Can learning algorithms also guide finding objects? Yes, this is the famous stable marriage algorithm
As we mentioned at the end of the last article, the marriage matching problem is essentially a binary graph matching problem. So what is binary graph matching? What algorithm should be used to solve the problem of binary graph matching? Let’s start with the most basic concepts.
Binary graph matching
The concept of a binary graph is simple: in an undirected graph, all points can be divided into two subsets. The points in these two subsets do not intersect each other, and all vertices associated with edges in the graph belong to two different sets. It is a little difficult to describe simply in language. In fact, we can understand it by looking at a picture.
In the figure above, it is clear that the three points on the left are one set and the three points on the right are another set. There is an edge between two sets, and the set is not connected internally.
Match and maximum match
In a binary graph, if we choose an edge we connect the corresponding two points. So this is a match, and we specify that a vertex can only be a match at most, which means that there are no common points between all matches.
For a binary graph, the number of matches can vary, and the case with the largest number of matches is called the maximum match. If all vertices match, the situation is called a perfect match.
The Hungarian algorithm we are going to introduce today is an algorithm used to achieve the maximum matching of binary graphs.
Hungarian algorithm
Hungary is the name of a country we all know, and it has to do with the inventor of the algorithm. Edmonds, the inventor of the Hungarian algorithm came up with the Hungarian algorithm in 1965, I don’t know why it’s called the Hungarian algorithm because the inventor of the Algorithm is Hungarian, I haven’t seen any other algorithm named after the country, is it because the Hungarians come up with so few algorithms?
The core principle of the Hungarian algorithm is very simple, which is to find the augmented path to achieve the maximum match.
Let’s explain what the algorithm means in plain English, and let’s use the diagram above as an example. We first match 1 on the left with a on the right, and 2 on the left with b on the right.
So when we try to match node 3 on the left, we find a problem, that is, the nodes a and B that can match node 3 are already occupied. So node 3 does not constitute a match, but if we look at the figure below, we can see that if nodes 1 and 2 adjust the match slightly, node 3 can actually be moved out of the position.
How do you do that?
We traverse all the nodes that node 3 can match, and first find node A, which is already occupied. So we find the node that a matches which is node 1, and we try to get it to find another match, and move node 3 out of the way. So we recursively arrange node 1, and we go to node B, and we find that node B is also occupied. So we recurse to node 2 that matches node B, and see if node 2 can find a new pit to make room for it.
Let’s look and see that node 2 can be matched with node C, making room for node 1, so node 1 can make room for node 3. So the final match looks like this:
The blue line is the result before adjustment and the red line is the result after adjustment.
Essentially, the Hungarian algorithm is a process of adjusting matches. Recursive calls are made to try to adjust matches that already occupy conflicting positions to make room for nodes on the right.
If we compare the principles of the Hungarian algorithm with the Gale-Shapley algorithm, what do we find? In fact, the core principle of these two algorithms is the same. In THE GS algorithm, we first initiate the pursuit by male students and try to form a match. The single man then repeated the offer, disconnecting the previous match if there was a better one. In the stable marriage problem we define good or bad matches, whereas in the original binary graph matching problem there is no good or bad matches. If we look at the process of a good guy taking over a bad guy’s girlfriend as a matching adjustment process, the core of the two algorithms is almost the same.
The only difference is that the GS algorithm iterates round after round until all nodes are matched. Because there must be a perfect match solution in the marriage matching problem, and in the binary graph matching problem, the perfect match may not exist. So instead of doing it iteratively, it’s better to do it recursively. In other words, Hungarian algorithm studies the general solution of binary graph matching, while GS algorithm is only a special case of binary graph algorithm.
Code implementation
Hungarian algorithm if you learn the idea, the code is actually very simple, is a simple recursive call.
def find_match(x):
for i in range(n):
if graph[x][i] and not tried[i]:
tried[i] = True
if match[i] == - 1 or find_match(match[i]):
match[i] = x
return True
return False
for i in range(n):
tried = [0 for _ in range(n)]
find_match(i)
Copy the codeLet’s try to use the Hungarian algorithm for the marriage stability problem, because in the marriage stability problem, every two people of the opposite sex can be matched, so we don’t need to judge the connectivity. And the matching of the composition has the difference of good or bad quality, so it is necessary to remove the judgment of whether it has been tried.
girls_matched = [- 1 for _ in range(n)]
boys_round = [0 for _ in range(n)]
boys_matched = [- 1 for _ in range(n)]
def find_match(x):
for i in range(n):
idx = girls[i].index(x)
mate = girls_matched[i]
mate_id = n+1 if mate == - 1 else girls[i].index(mate)
# If girl I has no object or object is weaker than boy X
if mate == - 1 or (idx < mate_id and find_match(girls_matched[i])):
girls_matched[i] = x
boys_matched[x] = i
return True
return False
for i in range(n):
# match I boy
find_match(i)
Copy the codeLet’s run this code:
It turns out to be correct, of course, but if we try to demonstrate it with GS we’ll see that the results of these two algorithms are different. Why is that? The reason is also very simple, because the order pursued by boys in GS algorithm is the order they like, while in Hungarian algorithm, the order is numbered, so the results are different.
conclusion
Here is the end of the principle and introduction of the Hungarian algorithm, for binary graph matching problem we have many algorithms can solve, but the Hungarian algorithm is one of the relatively simple and easy to understand and implement. If we compare it to the GS algorithm introduced earlier, we can see many commonalities and connected parts. The article only briefly introduced some, if the careful study will find many interesting points.
This is the end of today’s article, if you like this article, please invite a wave of quality sanlian, give me a little support (follow, forward, like).
– END –
