可能的最低总距离停车场算法

Question

今天，我参加了最后一轮的三次算法编码面试，被问到的最后一个问题难住了。我真的想看看解决方案是什么样子，而不是顺其自然，继续我的生活。我会尽力描述它：

你有一套汽车和停车场。

你知道每辆车到每个停车场的距离和停车场的容量。

你如何确保每辆车都能到达一个有空位的停车场，这样所有的车都能行驶尽可能短的总距离？

一个小例子可能是：

distance_car1_to_lot1 = 1
distance_car1_to_lot2 = 10
distance_car2_to_lot1 = 2
distance_car2_to_lot2 = 100
lot1_capacity = 1
lot2_capacity = 1

你可以在这里看到，如果你把car1放入lot1，把car2放入lot2，那么所有汽车的行驶距离都是101。

而不是这样做，取car1到lot2和car2到lot1将导致12的总行进距离。

假设有比上面列出的更多的汽车和停车场，你该如何解决这个问题。

我在整个面试过程中选择的语言是Javascript，但我想你可以做最适合你的。

Answer 1

你可以把这个问题写成一个图，其中顶点是汽车和停车场，边权重是行驶距离。这个图是一个完全的二部加权图。您可以使用匈牙利算法(Kuhn Munkres(找到汽车到停车场的最佳分配，如本视频所述：https://www.youtube.com/watch?v=FCaD34z--bY

若要处理停车场容量，可以将停车场节点拆分为容量为1的多个节点。例如，如果停车场2的容量为3，则可以将其替换为停车场2a、2b和2c。您可能还需要添加虚拟节点来平衡汽车和停车场的数量。例如，如果有3个汽车节点和4个停车场节点，则可以将1个边权重为0的虚拟汽车节点添加到所有停车场节点。

Answer 2

这就是我现在想做的全部。祝你好运

function distance(lat1, lng1, lat2, lng2, feet = false){
let p = 0.017453292519943295, c = Math.cos;
let r = 12742000*Math.asin(Math.sqrt(0.5-c((lat1-lat2)*p)/2+c(lat2*p)*c(lat1*p)*(1-c((lng1-lng2)*p))/2));
if(feet)r *= 1/0.3048;
return r
}
function Vehicle(color, year, make, model, lat = null, lng = null){
this.color = color; this.year = year; this.make = make; this.model = model; this.lat = lat; this.lng = lng;
this.distanceTo = (latLng, feet = false)=>{
return distance(this.lat, this.lng, latLng.lat, latLng.lng, feet);
}
}
function Lot(lat, lng, capacity){
this.lat = lat; this.lng = lng; this.capacity = capacity;
this.vehicles = [];
this.addVehicle = vehicle=>{
if(this.vehicles.length < this.capacity){
vehicle.lat = this.lat; vehicle.lng = this.lng; this.vehicles.push(vehicle);
}
return this;
}
this.removeVehicle = vehicle=>{
const v = this.vehicles, x = v.indexOf(vehicle);
if(x !== -1)v.splice(x, 1);
return this;
}
this.distanceTo = (latLng, feet = false)=>{
return distance(this.lat, this.lng, latLng.lat, latLng.lng, feet);
}
}
function sortDistances(distances, feet = false){
const d = [...distances], r = [], sortIt = (a, b)=>Object.values(a)[0]-Object.values(b)[0];
let n, a;
for(let lot of d){
n = -1; a = [];
for(let l of d){
n++;
if(l !== lot)a.push({[n]:lot.distanceTo(l, feet)});
}
a.sort(sortIt); r.push(a);
}
return r;
}
const lot1 = new Lot(47.581148063351534, -122.24032639373426, 1);
const lot2 = new Lot(47.583444521820496, -122.2447443008423, 1);
const lot3 = new Lot(47.583544521820333, -122.2447543008222, 35);
const vehicle1 = new Vehicle('yellow', 1979, 'Ford', 'Pinto');
const vehicle2 = new Vehicle('red', 2020, 'Ferrari', '812 Superfast');
lot1.addVehicle(vehicle1); lot2.addVehicle(vehicle2);
const lots = [lot1, lot2, lot3]; // so you can get the lots by index later
const d = sortDistances(lots);
console.log(d); // an Array of Arrays of Objects with lots indexes as keys and meters as values