Cars and Drivers

[kevphp]

Suppose you have 20 cars (car_1, car_2...car_20). You also have 20 drivers (driver_1, driver_2...driver_20). Every driver has to be assigned to a car. Every driver gets to order the cars in his order of preference.

 

driver_1's first choice may be car_3, then car_14, car_2, and then any available car.

driver_2's first choice may be car_20, car_19, and then any available car.

driver_3's first choice may be car_3, then car_1, car_5, car_20, and then any available car.

 

A driver's first choice is worth 1 point, 2nd choice is 2 points, 3rd choice is 3 points.

 

After all drivers have made their favorite selections, I now need to determine how to assign drivers to cars so that drivers get a car assigned based on their chosen order. The goal will be to minimize the number of points. With 20 cars and 20 drivers, if every driver got his first choice car, then the minimum would be 20 points, but this is not likely.

 

I was considering creating a table with permutations of every driver and then assigning each driver his top choice which has not already been taken. This works fine for small scenarios (6 cars and 6 drivers), but for 20 cars and 20 drivers, there would be far too many table records to process.

 

Does anyone have any suggestions on how to get started on a task like this, or can you point me to something similar.

[xyph]

To limit the number of permutations, only calculate the ones where two or more drivers have the same preference.

 

It's going to be difficult to solve without actually determining most paths. Any shortcuts could remove potential lower paths

[SofWare]

A solution that finds the minimum number of points for all permutations is Kruskal's algorithm (which is based on the idea of removing potential lower paths). A sketch of the solution is below. Please look up Kruskal's algorithm to understand what I mean by a weighted graph and edge.

 

Create a weighted graph where:

* an edge of weight 1 is drawn between each of the drivers;

* an edge whose weight is the number of points is drawn between the cars and the drivers (so there is an edge of weight 2 between driver_1 and car_14 in the example you gave above);

* no edges are drawn between the cars.

Then Kruskal's algorithm finds the minimum spanning tree of this which graph gives you your solution - it finds the smallest weight that connects all the drivers to cars (the minimum number of points) minus the weight required to connect the drivers (which is always 19).

 

Please let me know if you would like php code for this.