算法：给定P个偏好，最优地分配N个人到M个任务中。

Question

例子：10名应聘者对3个可用职位分别给出2个偏好（第一个比第二个更受欢迎），他们的老板必须根据他们的偏好进行最佳分配（并均匀分配），基于他们的偏好平等地分配。显然，不需要的工作将需要一些随机抽取。

我该如何编写一个算法来自动计算这个最优分配？

我找到了bipartite graphs，它可能会给我一些线索，但我很难理解它！

对于游戏的“运气”方面，我已经实现了一个简单的Fisher Yates Shuffle。 偏好权重： 如果有2个偏好，当分配给一名工人时，获得第一选择权重为+2，第二选择权重为+1，不想要的选择为-1（例如）。 “最优性”目标是最大化总体偏好。

- Andrea M

---

所有的偏好都是平等的吗？ - Mark Amery

你如何定义最优？可能不存在“最优分配”；参见：投票悖论。 - Simeon Visser

N、M和P的规模有多大？在这里进行全面搜索可能是可行的。 - Simeon Visser

这听起来像是一个约束问题，特别是一个软性约束优化问题。 - Lars Kotthoff

@nlucaroni，存在一种计划问题，标准的稳定概念不适用（因为只有一侧存在“偏好”）。 - Frank

Answer 1

你的问题很有挑战性，但我找到了一个可行的（也许不是最有效的）解决方案。我的示例是用PHP编写的，但你应该能够适应它。我将尝试解释代码背后的“思路”。

注意：看起来像是你后来添加了“10人，3个工作”的限制 - 或者我简单地忽略了它。然而，我的代码应该给你一个例子，你可能能够适应那个限制。我的代码目前假设有n个工作需要n个人去完成。（最容易适应10/3标准的方法是，在假设有10个工人时将3个工作分成10个相等的工作单位！）

首先，让我们创建一些基本架构。我们需要人员，工作和显然代表人对工作满意度的矩阵。以下代码片段正好做到了这一点：

<?php
class Person{
  var $name;
  var $prim;
  var $sec;

  function __construct($name, $prim, $sec){
    $this->name = $name;
    $this->prim = $prim;
    $this->sec = $sec;
  }

  function likes($job){
    if ($job->type == $this->prim) return 2;
    if ($job->type == $this->sec) return 1;
    else return -1;
  }
}

class Job{
  var $name;
  var $type;

  function __construct($name, $type){
    $this->name = $name;
    $this->type = $type;
  }
}


$persons = array(
  "Max" => new Person("Max", "programing", "testing"),
  "Peter" => new Person("Peter", "testing", "docu"),
  "Sam" => new Person("Sam", "designing", "testing")
);

$jobs = array(
  "New Classes" => new Job("New Classes", "programing"),
  "Theme change" => new Job("Theme change", "designing"),
  "Test Controller" => new Job("Test Controller", "testing")
);


// debug: draw it: 
echo "<h2>Happines with Jobs</h2> ";
echo "<table border=1>";
$p=0;
echo "<tr>";       
foreach ($jobs AS $job){
  $j=0;
  foreach ($persons as $person){
    if ($p++==0){
      echo "<tr><td></td>";
      foreach ($persons as $per) {
        echo "<td>".$per->name."</td>";
      }                             
      echo "</tr>";
    }


    if ($j++==0){
      echo "<td>".$job->name."</td>";
    }

    echo "<td>".$person->likes($job)."</td>";
  }
  echo "</tr>";
}
echo "</table>";

这将为您提供如下表格： 其次，我们需要创建所有工作和人员的排列组合。（实际上我们不需要这样做，但这样做会显示出我们为什么不需要！）

为了创建所有排列组合，我们只使用人或职位的名称。（稍后我们可以将名称解析回实际对象）

//build up all permutations
$personNames = array();
foreach ($persons AS $person){
  $personNames[] = $person->name;
}

$jobNames = array();
foreach ($jobs AS $job){
  $jobNames[] = $job->name;
}              

$personsPerms = array();
pc_permute($personNames,$personsPerms);

$jobsPerms = array();
pc_permute($jobNames,$jobsPerms);     

function pc_permute($items, &$result, $perms = array( )) {
    if (empty($items)) { 
      $result[] = join('/', $perms);
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems,$result, $newperms);
         }
    }
}

现在，我们有两个数组：所有工作排列和所有人员排列。对于上面给出的示例，这些数组将如下所示（每个数组都有3个元素，每个数组有6种排列组合）：

Array
(
    [0] => Max/Peter/Sam
    [1] => Peter/Max/Sam
    [2] => Max/Sam/Peter
    [3] => Sam/Max/Peter
    [4] => Peter/Sam/Max
    [5] => Sam/Peter/Max
)
Array
(
    [0] => New Classes/Theme change/Test Controller
    [1] => Theme change/New Classes/Test Controller
    [2] => New Classes/Test Controller/Theme change
    [3] => Test Controller/New Classes/Theme change
    [4] => Theme change/Test Controller/New Classes
    [5] => Test Controller/Theme change/New Classes
)

现在，我们可以创建一个nXn表格，其中包含所有可能的工作分配的总体满意度的所有值。

// debug: draw it:            
echo "<h2>Total Happines of Combination (full join)</h2> ";
echo "<table border=1>";
$p=0;
echo "<tr>";
$row = 0;
$calculated = array();       
foreach ($jobsPerms AS $jobComb){
  $j=0;
  $jobs_t = explode("/", $jobComb);
  foreach ($personsPerms as $personComb){

    if ($p++==0){
      echo "<tr><td></td>";
      foreach ($personsPerms as $n) {
        echo "<td>".$n."</td>";
      }                             
      echo "</tr>";
    }


    if ($j++==0){
      echo "<td>".$jobComb."</td>";
    }

    $persons_t = explode("/", $personComb);
    $h = 0;


    echo "<td>";
    for ($i=0; $i< count($persons_t); $i++){      
      $h += $persons[$persons_t[$i]]->likes($jobs[$jobs_t[$i]]);
    }
    echo $h;
    echo "</td>";

  }
  $col=0;
  $row++;
  echo "</tr>";
}
echo "</table>";

我们称这个矩阵为"M"

矩阵"M"中包含很多双重组合：(a/b)到(1/2)等于(b/a)到(2/1)等等...

最终结果是：我们可以简单地忽略：

• 每一行 > 1
• 或每一列 > 1

忽略所有列 > 1：

echo "<h2>Total Happines of Combination (ignoring columns)</h2> ";
echo "<table border=1>";
$p=0;
echo "<tr>";
$row = 0;
$calculated = array();       
foreach ($jobsPerms AS $jobComb){
  $j=0;
  $jobs_t = explode("/", $jobComb);
  $col = 0;
  $personComb = $personsPerms[0];

  if ($p++==0){
    echo "<tr><td></td>";
    echo "<td>".$personsPerms[0]."</td>";        
    echo "</tr>";
  }


  if ($j++==0){
    echo "<td>".$jobComb."</td>";
  }

  $persons_t = explode("/", $personComb);
  $h = 0;


  echo "<td>";
  for ($i=0; $i< count($persons_t); $i++){      
    $h += $persons[$persons_t[$i]]->likes($jobs[$jobs_t[$i]]);
  }
  echo $h;
  echo "</td>";

  $col=0;
  $row++;
  echo "</tr>";
}
echo "</table>";

输出:

就是这样！在这个例子中，最令人满意的解决方案之一是：

• Max -> 新班级（+2）
• Peter -> 测试控制器（+2）
• Sam -> 主题更改（+2）

-> 幸福感：6。

还有其他相等的分配方式。

例如：6个人/6个工作：

$persons = array(
  "Max" => new Person("Max", "programing", "testing"),
  "Peter" => new Person("Peter", "testing", "docu"),
  "Sam" => new Person("Sam", "designing", "testing"),
  "Jeff" => new Person("Jeff", "docu", "programing"),
  "Fred" => new Person("Fred", "programing", "designing"),
  "Daniel" => new Person("Daniel", "designing", "docu") 
);

$jobs = array(
  "New Classes" => new Job("New Classes", "programing"),
  "Theme change" => new Job("Theme change", "designing"),
  "Test Controller" => new Job("Test Controller", "testing"),
  "Create Manual" => new Job("Create Manual", "docu"),
  "Program more!" => new Job("Program more!", "programing"),
  "Style the frontend" => new Job("Style the frontend", "designing")
);

导致结果为（人员：Max / Peter / Sam / Jeff / Fred / Daniel）

- dognose

---

谢谢您的回答。所以，在N个工人和M个工作的情况下，其中M > N，您建议对M进行细分。如果情况并非总是如此，而工人应该尽可能均匀地分配怎么办？（在10/3的情况下，一个工人将成为一组中的第四个。这个被孤立的奇数只应该基于他的首选项被选择，因为他有权进入任何组）。 - Andrea M

Answer 2

假设“平均分配”意味着您知道必须分配给每个项目的人数，这就是加权匹配问题（又称“最大基数二分图匹配”）。只需将每个空缺职位（而不是每个工作）视为一个节点 - 因此，具有3个职位的工作将有三个节点。

维基百科文章提供了几种解决方案。

- BlueRaja - Danny Pflughoeft

Answer 3

伪代码

对于剩余工作的数量n
{
  工作n = 随机候选人
  如果随机候选人的第一选择 == 工作n
    从列表中删除随机候选人和工作
}
如果还有剩余工作
{
  对于剩余工作的数量n
    对于候选人的数量i
      如果候选人的第一选择 == 工作n
      {
          工作n = 候选人i
          从列表中删除候选人i和工作n
      }
      否则如果候选人的第二选择 == 工作n
      {
          工作n = 候选人i
      }
}

- EricLeaf

---

即使没有详细阅读代码，一旦将候选人与他们的首选工作匹配，立即从列表中删除候选人和工作显然是错误的，因为存在易于构造的情况，最优解涉及某些候选人未能获得他们的首选项。 - Mark Amery

您可能应该更仔细地阅读代码，因为只有当工作和候选人与他们的第一选择相匹配时，才会将其移除。第一部分仅填充所有职位，并有时会幸运地找到第一选择的匹配项。这样，所有工作都可以得到候选人。 - EricLeaf