Algorithms in the real world
In our blog, we pay attention to the topic of algorithms and have previously published material on the possibility of algorithmization of intelligence. There are more mundane applications of algorithms - today we decided to talk about this.
/ photo hackNY.org CC
Using algorithms to solve real-life problems is a very interesting exercise. The organizers of the HackMIT conference, held at the Massachusetts Institute of Technology, provide hackers who come to attend the event with accommodation on campus. Students who will let guests receive inflatable mattresses as a gift - the scheme works flawlessly.
')
To do without problems, you need to make sure that the requirements of guests coincide with what the owner can offer - and therefore, it is necessary in some way to make a selection. For example, a hacker arriving at a conference may need accommodation only at night from Friday to Saturday, or maybe for two nights, and the hosts may be able to accommodate different numbers of guests on Friday and Saturday.
The lodger may be allergic to domestic animals, the housing of some owners may, on the contrary, be adapted for cats. Some of the guests do not like smoking, but the owner can live in the building where smoking is allowed. There is still a different attitude towards living with people of the opposite or the same sex. A questionnaire collection form is sent to all guests and homeowners in order to increase the comfort of the conference participants and the people who accept them.
Initially, the organizers of the event picked up housing for the guests manually, but if there are several hundred conference participants, this is very difficult. When it comes to automating this process, then there is a bipartite selection problem. There are two sets of people, guests and hosts, whose representatives need to be combined with each other based on survey data. If one host can receive several guests, then a node duplication comes into play.
A simple algorithm for finding matches can traverse the list of hackers and associate them with the first available host that meets the requirements. This is a rather gluttonous algorithm in terms of resources, but it can be easily and quickly programmed. However, this does not mean that all possible matches are included here - if you work better, then more people could be reduced.
To achieve better results, you need a different algorithm. You can look at the problem of choice as the problem of maximum flow and use the Edmonds-Karp or Hopcroft-Karp algorithm. This path ensures the selection of the maximum possible number of matches.
Real data suggests that using a good algorithm allows you to achieve good results. In 2015, 359 hackers participated in the HackMIT conference, which were placed by unique 234 hosts. Some of the owners were able to accommodate guests for several days, in fact it resulted in the availability of 367 accommodation options for each day.
The first is not the most optimal algorithm found the maximum match for 95% of hackers. The optimal algorithm allowed to accommodate all the guests.
PS We try to share not only our own experience in the service of providing virtual infrastructure 1cloud , but also to talk about various research and news in related fields of knowledge.
Do not forget to subscribe to our blog on Habré, friends!
/ photo hackNY.org CC
Using algorithms to solve real-life problems is a very interesting exercise. The organizers of the HackMIT conference, held at the Massachusetts Institute of Technology, provide hackers who come to attend the event with accommodation on campus. Students who will let guests receive inflatable mattresses as a gift - the scheme works flawlessly.
')
To do without problems, you need to make sure that the requirements of guests coincide with what the owner can offer - and therefore, it is necessary in some way to make a selection. For example, a hacker arriving at a conference may need accommodation only at night from Friday to Saturday, or maybe for two nights, and the hosts may be able to accommodate different numbers of guests on Friday and Saturday.
The lodger may be allergic to domestic animals, the housing of some owners may, on the contrary, be adapted for cats. Some of the guests do not like smoking, but the owner can live in the building where smoking is allowed. There is still a different attitude towards living with people of the opposite or the same sex. A questionnaire collection form is sent to all guests and homeowners in order to increase the comfort of the conference participants and the people who accept them.
Initially, the organizers of the event picked up housing for the guests manually, but if there are several hundred conference participants, this is very difficult. When it comes to automating this process, then there is a bipartite selection problem. There are two sets of people, guests and hosts, whose representatives need to be combined with each other based on survey data. If one host can receive several guests, then a node duplication comes into play.
A simple algorithm for finding matches can traverse the list of hackers and associate them with the first available host that meets the requirements. This is a rather gluttonous algorithm in terms of resources, but it can be easily and quickly programmed. However, this does not mean that all possible matches are included here - if you work better, then more people could be reduced.
To achieve better results, you need a different algorithm. You can look at the problem of choice as the problem of maximum flow and use the Edmonds-Karp or Hopcroft-Karp algorithm. This path ensures the selection of the maximum possible number of matches.
Real data suggests that using a good algorithm allows you to achieve good results. In 2015, 359 hackers participated in the HackMIT conference, which were placed by unique 234 hosts. Some of the owners were able to accommodate guests for several days, in fact it resulted in the availability of 367 accommodation options for each day.
The first is not the most optimal algorithm found the maximum match for 95% of hackers. The optimal algorithm allowed to accommodate all the guests.
PS We try to share not only our own experience in the service of providing virtual infrastructure 1cloud , but also to talk about various research and news in related fields of knowledge.
Do not forget to subscribe to our blog on Habré, friends!
Source: https://habr.com/ru/post/267719/
All Articles