2

作为一个过于简单的例子，我有一个出席人数最多的活动列表：

 event    | places
===================
 event_A  |   1
 event_B  |   2
 event_C  |   1

以及与活动距离的与会者名单：

 attendee    | event_A dist | event_B dist | event_C dist
==========================================================
 attendee_1  |      12      |      15      |      12      
 attendee_2  |      11      |      15      |      11
 attendee_3  |      10      |      11      |      12

谁能建议一种简单的方法来生成一组选项，根据最短的总距离和最短的平均距离提供最佳案例分配？

我目前将数据保存在 Oracle Spatial 数据库中，但我愿意接受建议。

4

1 回答 1

0

我目前对您的问题的理解如下：

  • 每个与会者都应该被分配到一个事件
  • 每个事件都有分配给它的参加者人数的限制
  • 未满甚至是空的事件都没有问题
  • 事件和参加者之间的每个分配对应于给定的距离
  • 您希望最小化所有作业的总距离
  • 您可能希望不使用总和而是使用均值来打印结果

基于这种解释，我建议以下算法：

  1. 创建一个完整的二分图，分区A中的节点代表参加者，分区B中的节点代表事件中的地点。所以每个参加者对应一个节点，每个事件对应的节点与它的位置一样多。所有参加者都连接到所有事件节点，距离作为边缘成本。

    此时，您的问题对应于一般分配问题，“代理”对应于您的活动地点，“任务”对应于您的参加者。必须覆盖每个与会者，但并非必须使用每个活动场所。

  2. 添加虚拟与会者以实现完美匹配。简单地总结所有地方，从中减去实际参加者的数量。对于差异，创建尽可能多的参加者节点，到所有事件节点的距离为零。

    通过使两个分区的大小相等，您现在处于更常见的线性分配问题的域中。

  3. 使用匈牙利算法计算最小成本分配。也许您可以考虑一些简化，利用您有许多等效节点的事实，即同一事件的地点和所有那些虚拟参加者。

所有这些可能都应该在应用程序代码中完成，而不是在数据库中。所以我宁愿标记这个。您需要从数据库中提取完整的成本矩阵来为您的边缘提供成本。

于 2013-02-21T10:16:53.660 回答