We have a set of Passengers and a set of Cars. We want to assign each Passenger to a Car in an optimal way. There is a scoring function: Score(car, passengers) which takes a subset of passengers as input, and the car. This function is complex and is a black box, i.e. you can’t see how it is implemented or modify it. We want to write an algorithm which will assign passengers to cars in an optimal way, where “optimal” means we minimise the sum of all the “Score(car, car.Passengers)”. Suppose you write such an algorithm, using a technique called “Hill-climbing” (making incremental changes and seeing if that improves or makes worse the overall score). You are happy with your algorithm except that it takes too long. During profiling, you find that the score calculation takes 95% of the CPU time. Can you think of a good way to speed up the algorithm?
Vijay Toorpaty asked 5 years ago
