6

示例： 10 名候选人每人对 3 个可用工作给出 2 个偏好（第一个比第二个更偏好），然后他们的老板必须根据他们的偏好平均分配（并平均分配）它们。显然，不需要的工作将需要一些随机抽取。

我将如何编写一个自动计算此最佳分配的算法？

我环顾四周，发现了可能会给我一些线索的二分图，但是我很难理解它！

对于游戏的“运气”方面，我已经实现了一个简单的 Fisher Yates Shuffle。

偏好权重： 如果有 2 个偏好，当分配给工人时，获得第一个选择权重 +2，第二个选择权重 +1，不想要的选择权重 -1（例如）。“最优”目标是最大化总体偏好。

4

3 回答 3

2

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

注意：似乎您稍后添加了“10 人，3 个工作”约束——或者我只是过度阅读了它。但是，我的代码应该为您提供一个示例，您可能能够适应该约束。我的代码目前假设有人有n工作n。（将其调整为 10/3 标准的最简单方法是将 3 个工作分成 10 个相等的工作单元，假设有 10 个工人！）

首先，让我们创建一些基本架构的东西。我们需要person，job显然是一个矩阵，代表一个人对工作的满意度。以下片段正是这样做的：

<?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);
         }
    }
}

现在，我们有 2 个数组：所有工作排列和所有人员排列。对于上面给出的示例，数组将如下所示（每个 3 个元素，每个数组有 3*2*1=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”

该矩阵包含“很多”双重组合：(a/b) TO (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>";

输出：

在此处输入图像描述

你去吧！在这个例子（之一）中，最令人满意的解决方案是：

  • 最大 -> 新课程 (+2)
  • 彼得 -> 测试控制器 (+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）

在此处输入图像描述

于 2013-09-26T22:26:43.673 回答
1

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

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

于 2013-09-26T23:04:59.970 回答
-1

伪代码

for(n 到剩余的工作数量)
{
  工作 n = 随机候选人
  if(随机候选人第一偏好 == 工作 n)
    从列表中删除随机候选人并从列表中删除工作
}

如果（剩下的工作）
{
  for(n 到剩余的工作数量)
    for(i to number of Candidates)
      如果（候选人第一偏好 == 工作 n）
      {
          工作 n = 候选人 i
          从列表中删除候选人 i 并从列表中删除工作 n
      }
      else if(候选人第二偏好 == 工作 n)
      {
          工作 n = 候选人 i
      }
}
于 2013-09-26T18:05:45.003 回答