在一个标准的线性分配问题中,我可以使用匈牙利算法来实现 O(n^3)。如果添加额外的约束怎么办?示例:
具有 4 个智能体的“常规”LAP 具有约束矩阵
结果向量 b = [1 1 1 1]。
匈牙利算法将按预期解决此类问题。但是,如果添加另一个约束会怎样,使得约束矩阵为
结果向量 b = [1 1 1 1 0] ??
也就是说,除了在标准线性和约束下最小化成本函数外,我还必须考虑像这样的约束
这个总和产生上面附加矩阵的最后一行。
显然,生成的约束矩阵不再是完全幺模的。当然,标准的 MILP 可以解决这个问题,但是 NP 很难。我的问题是:是否有类似匈牙利的算法可以在多项式时间内解决这个 LAP?
最佳答案
通常,具有边约束的网络流问题是 NP-Hard。例如,具有非负边成本的最短路径问题是多项式可解的。例如,您可以使用 Dijkstra 的最短路径算法。 (分配问题是网络流问题的特例。)
但是,如果您添加单个约束,规定使用的边数应小于某个常数,则随之而来的约束最短路径问题就是 NP-Hard。
因此,您的问题不太可能有多项式算法。
关于algorithm - 具有附加约束的线性分配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46892373/