前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >分配问题与匈牙利算法

分配问题与匈牙利算法

作者头像
用户1665735
发布2019-05-26 15:36:39
2.5K1
发布2019-05-26 15:36:39
举报
文章被收录于专栏:kevindroid

分配问题与匈牙利算法

例1

假如你是个玩具工厂的销售经理,你现在有三个销售人员要去不同城市见买家。你的销售人员分别在在奥斯丁,得克萨斯州;波士顿、马里兰州;和芝加哥,伊利诺伊州。你想让他们飞往其他三个城市:丹佛,埃德蒙顿,法戈。下面的表格显示了这些城市之间飞机票的费用.。

From \ To

Denver

Edmonton

Fargo

Austin

250

400

350

Boston

400

600

350

Chicago

200

400

250

你应该让你的销售人员前往哪个城市以获取最小的费用? 可以用一个花费矩阵来代表上图数据:

⎡⎣⎢250400200400600400350350250⎤⎦⎥(1)

\left[ \begin{matrix} 250 & 400 & 350 \\ 400 & 600 & 350 \\ 200 & 400 & 250 \end{matrix} \right] \tag{1} 让我们看一下可能的分配方案:

总共需要花费 250 + 600 + 250 = 1100. 以下是另一种分配方案:

总共需要花费 250 + 350 + 400 = 1000. 检查完所有六种可能的分配方案后我们得到最有的分配方案是:

总共需要花费 400 + 350 + 200 = 950. 即你的销售人员应该从奥斯汀飞往埃德蒙顿,从波斯顿飞往法戈,从芝加哥飞往丹佛。 遍历所有可能的情况对于此问题是可行的,但是如果是从十个城市飞往另外十个城市呢?那么便有n!种可能的情况,显然,遍历不可行。

定理

如果从成本矩阵的任一行或列的所有项中添加或减去数字,那么,所得矩阵的最优分配也是原始矩阵的最优分配。

匈牙利算法

下面的算法将上述定理应用到一个给定的n×n成本矩阵上求出最优分配。

  1. 每行的所有数字减去该行的最小项
  2. 每列的所有数字减去该列的最小项
  3. 使用横线或者竖线穿过矩阵中的所有0,并记录达成此目的所需的最少线路总数
  4. 如果线路总数等于矩阵的行数或者列数n,那么一种最优的分配是可能的,完成。如果总数小于n,执行下一步
  5. 找到线路未覆盖的地方的最小项,存在未覆盖的项的行减去该项,然后将该项添加到覆盖的列中

例2

题目同例1 解题方法: 第一步:第一行减去250,第二行减去350,第三行减去200

第二步:第一列减去0,第二列减去150,第三列减去0

第三步:划线以包含全部0

第四步:划线数等于行数,最优分配找到。每行每列选择一个0,对应的原矩阵数字相加即为最小分配。

例3

一家建筑公司有四个大型推土机位于四个不同的车库。推土机被转移到四个不同的建筑工地。推土机和建设用地之间的距离如下(单位:公里)。

推土机 \ 工地

A

B

C

D

1

90

75

75

80

2

35

85

55

65

3

125

95

90

105

4

45

110

95

115

我们应该怎么分配推土机使得推土机总共行驶的里程最小? 第一步:第一行减去75,第二行减去35,第三行减去90,第四行减去45

第二步:第一列减去0,第二列减去0,第三列减去0,第四列减去5。

第三步:划线以包含全部0

第四步:因为线路总数小于4,故执行第五步 第五步:注意到5是未覆盖区域的最小值,存在未覆盖区域的行每行减去5

然后被覆盖的列每列加5

然后再执行步骤3:划线以包含全部0

因为线路数量小于4,执行步骤5:注意到20是未覆盖区域的最小值,存在未覆盖区域的行每行减去20

然后覆盖的每列加20

跳转到步骤3:划线覆盖所有0

第四步:因为最小线路总数等于4,故存在最优分配

每行每列选择一个0,对应的原矩阵数字相加即为最小分配。

故推土机1去工地D,推土机2去工地C,推土机3去工地B,推土机4去工地A。

备注

最大分配问题只需将第一步的每行减去该行最小值改为该行的最大值减去此行每一项,其他步骤相同。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年01月17日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 分配问题与匈牙利算法
    • 例1
      • 定理
        • 匈牙利算法
          • 例2
            • 例3
              • 备注
              相关产品与服务
              图数据库 KonisGraph
              图数据库 KonisGraph(TencentDB for KonisGraph)是一种云端图数据库服务,基于腾讯在海量图数据上的实践经验,提供一站式海量图数据存储、管理、实时查询、计算、可视化分析能力;KonisGraph 支持属性图模型和 TinkerPop Gremlin 查询语言,能够帮助用户快速完成对图数据的建模、查询和可视化分析。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档