在将单个目标映射到多个源的情况下，找到最接近源的目标并解决冲突的算法 [英] Algorithm for locating the closest destination(s) to source(s) and resolving conflicts in case a single destination is mapped to multiple sources

问题描述

问题陈述:给定一个由人(用小写字母表示)和自行车(用大写字母表示)的矩阵，请找到与给定人员最近的自行车.如果必须为一群人找到自行车，您将如何更改解决方案?(假设多辆自行车可以与1个人保持相同的距离)?

Problem Statement: Given a matrix of people(denoted by small alphabets) and bikes(denoted by capital alphabets), find the nearest bike for a given person. How will you change your solution if you have to find bikes for a set of people? (assuming multiple bikes can be at the same distance from 1 person)?

我知道 Dijkstra的算法和 BFS(宽度优先搜索)解决?

I know Dijkstra's algorithm and Bellman Ford's algorithm, but curious about the implementation here. Or can it be solved by BFS(Breadth First Search)?

推荐答案

补充@jrook的答案，请注意最小权重完全二部匹配"(完全"或完美"，因为否则，最佳解决方案是空匹配)也被称为 线性分配问题 再提供一些关键字以帮助您入门.

Supplementing @jrook's answer, note that the "minimum weight full bipartite matching" ("full" or "perfect" because otherwise the optimal solution is the empty matching) also goes under the name of the linear assignment problem, just to give some more keywords to get you started.

虽然将问题表述为线性编程问题确实可以解决问题，但确实有很多算法可以为这种特殊情况提供解决方案.

While it's certainly true that phrasing the problem as a linear programming problem does the job, indeed there are plenty of algorithms that provide solutions for this particular case.

如果您熟悉最短路径和扩展路径搜索算法(例如可以用于最大二分匹配或最大流量)，那么也许是最容易理解的算法是您首先意识到手头的问题是最小成本流问题的特例可以通过用最短路径搜索替换Edmonds-Karp算法的BFS步骤来解决.匈牙利算法.

If you're familiar with shortest path and augmenting path search algorithms (such as those that can be used to maximum bipartite matching or maximum flow), then perhaps the simplest algorithm to understand is what you first get by realizing that the problem at hand is a special case of the minimum cost flow problem which can be solved by replacing the BFS step of the Edmonds--Karp algorithm by a shortest path search. More common in introductory texts is the Hungarian algorithm.

如果您关心性能，那么这里有更高效的算法；确实很容易找到.

If you care about performance, there are more efficient algorithms out there; indeed it is easy to find solutions that are orders of magnitude faster than what you get by just throwing a commercial solver after the linear programming formulation.

这篇关于在将单个目标映射到多个源的情况下，找到最接近源的目标并解决冲突的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！