寻找高效的聚类算法
Searching for efficient clustering algorithm
在二维 NxN 矩阵中，每个点代表地图的一个区域。随机区域有M个客户，需要随机区域K个客服中心服务。每个客户服务中心最多可以服务 X 个职位。所有客户的数量必须小于或等于客户服务中心的总容量。必须将所有客户分配到任何一个服务中心，哈密尔顿距离就是成本（客户只能向上、向左、向下和向右移动到服务中心）。如何分配客户使总成本最小？如果它是一个众所周知的问题或至少是伪代码，我正在寻找一个方向。
问题的表述方式，你有一个constrained optimization problem, and not a clustering problem. It likely is convex, integer and linear。
聚类算法不满足容量限制。
关于这种优化的研究很多。有各种高度优化的求解器可用。
我认为你可以使用 MinCost/MaxFlow 算法来解决这个问题。创建图表如下：
- 创建
M + K + 2个节点； M customer-nodes, K customer-service-center-nodes (csc-nodes), 一个源和一个汇.
- 创建
K 从源到 K csc-nodes 的边，成本 0 和容量等于每个 CSC 可以服务的客户数量。
- 从
M customer-nodes 到汇点创建 M 条边，每条边将具有容量 1 和成本 0.
- 从
K csc-nodes 到 M customer-nodes 创建 K * M 条边，每条边的容量等于 1 并且成本等于CSC和客户之间的距离。
运行 MinCost/MaxFlow 网络上的算法 (V = M + K + 2, E = M + K + M*K)。如果 max-flow 值等于 M，那么您可以用由此产生的（最小）成本为所有客户提供服务。
这种情况的解决方案是23。
在二维 NxN 矩阵中，每个点代表地图的一个区域。随机区域有M个客户，需要随机区域K个客服中心服务。每个客户服务中心最多可以服务 X 个职位。所有客户的数量必须小于或等于客户服务中心的总容量。必须将所有客户分配到任何一个服务中心，哈密尔顿距离就是成本（客户只能向上、向左、向下和向右移动到服务中心）。如何分配客户使总成本最小？如果它是一个众所周知的问题或至少是伪代码，我正在寻找一个方向。
问题的表述方式，你有一个constrained optimization problem, and not a clustering problem. It likely is convex, integer and linear。
聚类算法不满足容量限制。
关于这种优化的研究很多。有各种高度优化的求解器可用。
我认为你可以使用 MinCost/MaxFlow 算法来解决这个问题。创建图表如下：
- 创建
M + K + 2个节点；Mcustomer-nodes,Kcustomer-service-center-nodes (csc-nodes), 一个源和一个汇. - 创建
K从源到Kcsc-nodes 的边，成本0和容量等于每个 CSC 可以服务的客户数量。 - 从
Mcustomer-nodes 到汇点创建M条边，每条边将具有容量1和成本0. - 从
Kcsc-nodes 到Mcustomer-nodes 创建K * M条边，每条边的容量等于1并且成本等于CSC和客户之间的距离。
运行 MinCost/MaxFlow 网络上的算法 (V = M + K + 2, E = M + K + M*K)。如果 max-flow 值等于 M，那么您可以用由此产生的（最小）成本为所有客户提供服务。
这种情况的解决方案是23。