How Practical Is It to Let a Computer Professor Use a Greedy Algorithm to Recover a Hijacked Vehicle?
By Super Neuro
During the Christmas holiday last year, Shi Yiyu, a tenured associate professor and doctoral supervisor in the Department of Computer Science at the University of Notre Dame, and also a tenured associate professor in the Department of Electronics, experienced a Hollywood-style car search.
Within 24 hours of the car being hijacked, Professor Shi used the fuzzy positioning function provided by the vehicle itself to greedy approach, quickly and accurately located the vehicle, and got his car back.
Case Review
|
Day 1 12:00 AM Carjacking  Professor Shi stopped at a gas station to add pressure to the tires. While Professor Shi was checking the condition of the car, two gangsters took the opportunity to hijack the car. In a panic, Professor Shi secretly put his mobile phone in the pocket behind the seat. |
 |
|
|
Day 1 17:00 PM Start tracking After calling the police to no avail, Professor Shi decided to find the car as soon as possible. He returned to school to track it, but the mobile phone positioning was no longer effective. |
|
Day 2 5:00 AM Fuzzy positioning Professor Shi used the car's built-in Mazda Mobile Start (MMS) to find the car's vague location, which was more than 80 kilometers away from him, with a system error of 6-7 meters. |
 |
|
 |
Day 2 7:00AM 60 meters apart! Professor Shi made a quick inference through the greedy algorithm:When it is found that the relative distance is no longer decreasing, stop in time and continue searching in the vertical direction. Using this method, Professor Shi once reduced the distance to just 60 meters and finally accurately located it in a garage. |
|
Day 2 9:00 AM Police helpless While waiting for the police to arrive, Professor Shi and Xiao Wang discovered that the robbers might have noticed something unusual and drove away. Professor Shi handed his phone to the police and continued to track the vehicle, but the police failed to search according to Professor Shi's algorithm prompts. |
 |
|
 |
Day 2 10:00 AM Get your car back! After Professor Shi regained his mobile phone, he continued to use his car-finding algorithm and finally found the stolen car in a parking lot. The police successfully returned the car to Professor Shi. |
Professor Shi’s ultimate car-chasing trick: Greedy algorithm
This tense carjacking incident was solved within just 24 hours, all thanks to Professor Shi's execution and accurate algorithm deduction.
Even the police were amazed at how quickly Professor Shi was able to resolve the matter:
"They shouldn't have messed up with computer science professors! Are they stupid? How could they rob computer science professors?"
Professor Shi explained that the key technology for positioning vehicles is actually the most direct greedy approach in computer algorithms.
Greedy Algorithm,Also known as the greedy algorithm, it is one of the most famous and classic algorithms in mathematics and computer science.
When solving a problem, it does not care what happened before or after, it is only related to the current state, and only obtains the optimal solution for the current sub-problem. However, as long as the local optimal solution obtained each time can be used, the global optimal solution or optimal goal can be derived.
Professor Shi applied the greedy algorithm to the technique of finding a car:
When driving, if you find that the relative distance between you and the car is no longer decreasing, stop driving immediately.
Then continue searching in the vertical direction.
This is a spiral search structure that ensures that it can always converge in a monotonous search in the direction of decreasing distance.
So in the end, with only two people in a car, Professor Shi quickly located the stolen vehicle with the guidance of navigation software with an error of 3 kilometers. The greedy algorithm was the most accurate tool.
Other classic applications of greedy algorithms
As one of the classic algorithms, the greedy algorithm is not widely used.
Because the greedy algorithm can only achieve the global optimum by solving the local optimal solution strategy. Therefore, it is important to pay attention to whether the problem is suitable for the greedy algorithm strategy and whether the solution found is definitely the optimal solution to the problem.
For example, the knapsack problem and the path problem, the following classic algorithms are used to explain the beauty of greed:
Dijkstra's algorithmIt is an algorithm for computing the single-source shortest path (SSSP) in a weighted directed graph, conceived by computer scientist Edsger Dijkstra in 1956 and published in 1959.
The problems it solves are:
Given a graph G and a source vertex v, find the shortest path from v to all vertices in the graph.
The Dijkstra algorithm is designed using the Greedy Algorithm paradigm:
Generate the shortest path for each vertex one by one in the order of increasing path length.During the algorithm, a vertex set SS needs to be maintained, which stores the vertices for which the shortest path has been found. A distance array dist needs to be maintained, where dist[i] represents the distance between the i-th vertex and the source node s.
- S is initialized to include only the source node s; dist[]dist[] is initialized to: dist[i]= arc[s][i], arc is the adjacency matrix of the graph. V−SV−S represents the set of vertices for which the shortest path has not been found;
- Put distdist in increasing order, select a shortest path, add the corresponding vertices from V−SV−S to S, and each time a new vertex u is added to S, distdist needs to be updated, that is, whether s can reach other vertices closer through vertex u.
That is, if dist[u] + arc[u][v] < dist[v], then update dist[v]=dist[u]+arc[u][v]
- Repeat the above steps until S=VS=V
Easter egg: New question type of greedy algorithm
It was the National Day of Country H, and the king invited n ministers to play a prize game. First, he asked each minister to write an integer on his left and right hands, and the king also wrote an integer on his left and right hands.
Then, let these n ministers line up in a row, with the king standing at the front of the line. After lining up, all ministers will receive a number of gold coins as rewards from the king. The number of gold coins each minister receives is:The result is the product of the numbers on the left hands of all the people in front of the minister, divided by the number on his own right hand, and then rounded down.
The king does not want any one minister to receive particularly large rewards, so he would like you to help him rearrange the order of the team so that the minister who receives the most rewards will receive as little reward as possible.
(Note that the king is always at the front of the line.)