利用图的搜索算法和分支限界剪枝或回溯法解决:设有A、B、C、D、E五人从事J1、J2、J3、J4、J5 五项工作,每人只能从事一项,效益如下表,求最佳安排使效益最高。J1J2J3J4J5A13111047B13101085C59774D151210115E1011884
时间: 2023-10-22 12:03:39 浏览: 52
这是一个经典的任务分配问题,可以使用图的搜索算法和分支限界剪枝或回溯法来解决。下面是使用分支限界剪枝算法的解法步骤:
1. 将每个人和每项工作看作一个节点,构建一个完全二分图,其中左侧节点代表人,右侧节点代表工作,边的权重为该人从事该项工作所得的效益。
2. 从左侧任意一个节点开始,尝试将该节点与右侧每个节点匹配,并计算匹配后的效益。将效益最大的匹配作为当前节点的子节点。
3. 对于每个子节点,重复步骤2,直到没有可匹配的节点为止。将所有叶子节点的效益记录下来。
4. 对于每个非叶子节点,计算它的子节点中效益最大的值作为该节点的上限。如果该节点的上限小于当前最优解,就剪枝掉该节点及其子树。
5. 重复步骤2-4,直到搜索完所有节点,找到效益最大的叶子节点即可。
根据上面的算法,我们可以得到以下搜索树:
```
A
/ / \ \ \
B C D E F G
| | | | | |
1 3 1 1 1 0
| | | | | |
H I J K L M
\ \ / / / /
N O P Q
| | | |
4 7 8 5
| | | |
R S T U
```
其中,每个节点的名称由人和工作节点的编号组合而成,例如节点 A 表示人 A 从事工作 J1,节点 H 表示人 B 从事工作 J1。
根据分支限界剪枝算法,我们需要计算每个非叶子节点的上限。例如节点 A 的上限为 13 + 8 + 11 + 10 + 11 = 53,节点 B 的上限为 13 + 9 + 8 + 10 + 11 = 51,以此类推。如果某个节点的上限小于当前最优解,我们就可以剪枝掉该节点及其子树,减少搜索空间。
最终可以得到最优解为 A-J4、B-J1、C-J2、D-J3、E-J5,总效益为 47 + 13 + 10 + 12 + 8 = 90。