ADdV
2021-01-24 07:30:50
两者都可以多项式求解
我将快速介绍定义最佳分配的两种方法，如问题中所述。请注意，我不会对旅行时间做出任何假设，例如三角不等式。当然，这样的性质在实践中很可能成立，并且可能有使用这些性质的更好的算法。
最小化总距离
对于这个例子，我们认为经理和商店是一个加权的完整二部图。然后我们想要一个最小化权重总和的匹配。
这称为平衡分配问题，它是最小/最大匹配的一种特殊情况。由于图是二部图，因此可以通过多项式求解。维基百科列出了解决这个问题的几种算法，最著名的是匈牙利算法。
最小化最大距离
如果我们希望最小化最大距离，我们可以通过二分搜索找到一个解决方案。具体来说，我们对最大距离进行二分搜索，并尝试找到不违反该最大距离的匹配项。
对于任何给定的最大距离 x，当且仅当 d(M, S) < x 时，我们创建二部图，该图在管理器 M 和存储 S 之间具有边。然后我们尝试使用任何二部匹配算法在这个二部图上创建一个完整的匹配，并通过成功和失败完成对允许匹配的最小 x 的二分搜索，从而最小化最大距离。
热门帖子
热门github
1
2
3
5
6
7
8
11
13
14
15
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.
(翻译：Mamba 是一种新的状态空间模型架构，在信息密集型数据（例如语言建模）上显示出良好的性能，而之前的二次模型在 Transformers 方面存在不足。它基于结构化状态空间模型的进展，并本着FlashAttention的精神进行高效的硬件感知设计和实现。)
二分查找的复杂度是多少？
@AbhinavMathur这将是
O(log(x))其中x是经理和商店之间的最大距离，和常数取决于期望的精度。使用例如 Ford-Fulkerson 来查找匹配项，O(n^2 log(x))总共给出。